27. Подграфы

Граф 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

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

K=C1m+C2m+...+Cm-1m=2m-1

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

< Предыдущая		Следующая >