2.2 Подграфы

Граф G'(V, E') называется подграфом графа G(V, Е) (обозначается G' ⊂G), если V' ⊂V и/или Е' ⊂ Е.

Если V' = V, то G' называется остовным подграфом G.

Если V' ⊂V& Е' ⊂E&(V' ≠ V∨ Е' ≠ Е) то граф G' называется собственным подграфом графа G.

Подграф G'(V',E') называется правильным подграфом графа G(V,E), если G'содержит все возможные ребра G:

∀u, v∈V' (u,v) ∈E⟹ (u,v) ∈ Е'.

Правильный подграф G'(V', Е') графа G(V, Е) определяется подмножеством вершин V'.

Виды подграфов (рис 10): а – исходный граф; б – подграфы; в – остовные подграфы; г – порожденные подграфы

Рисунок 10

Остовным подграфом G_p = (V, E_p) графа G называется граф, для которого E_p⊂A. Таким образом, остовный подграф имеет то же самое множество вершин, что и исходный граф G, но множество дуг подграфа G_p является подмножеством множества дуг исходного графа. Примеры остовных подграфов приведены на рис. 10,в. Для графа, имеющего m дуг, можно построить k остовных подграфов

k=C¹_m+C²_m+...+C^m-1_m=2^m-1

Порожденным подграфом G_s =(V_s, Г_s) называется граф, для которого V_s⊂V и для каждой вершины v_i∈V_s прямое отображение Г_s(v_i) = Г(v_i)∩V_s . Таким образом, порожденный подграф состоит из подмножества вершин V_s множества вершин исходного графа и всех таких дуг графа G, у которого конечные и начальные вершины принадлежат подмножеству V_s . Примеры порожденных подграфов приведены на рис. 10,г.