Определение 3.6. Максимальный связный подграф G’ графа G называется компонентой связности (или просто компонентой) графа G

Подграфы. Компоненты связности.

Определение 3.1. Граф G’ = (V’,U’) называется подграфом графа G = (V,U) (обозначается G’ ⥹ G), если V’ ⊆ V и U’ ⊆ U. Таким образом, каждая вершина в G’ являетсявершиной в G и каждое ребро (дуга) в G’ являетсяребром (дугой) в G. Еслихотя бы одно из отмеченных выше включений V’ ⊆ V или U’ ⊆ U строгое, то подграф G’ называется собственным подграфом графа G. Если V’ = V, то G’ называется остовным подграфом графа G.

Пример 3.1. Для орграфа

v₂ v₅

G:

v₁ v₃ v₄ v₆

граф

v₂

G₁:

v₁ v₃ v₄ v₆

является собственным подграфом орграфа G.

Определение 3.2. Подграф G’ = (V’,U’) графа G = (V,U) называется вершиннопорожденным, если V’ ⊆ V и его множество ребер U’ содержит все те ребра графа G, оба конца которых содержатся в V’.

Пример 3.2. Выберем во множестве вершин V орграфа G примера 3.1 произвольным образом некоторое подмножество V₂ = {v₁, v₂, v₄, v₅}. Тогда подграф

v₂ v₅

G₂:

v₁ v₄

графа G является вершиннопорожденным (заданным подмножеством вершин V₂).

Определение 3.3. Подграф G’ = (V’,U’) графа G = (V,U) называется ребернопорожденным, если U’ ⊆ U и его множество вершин V’ состоит из всех тех вершин графа G, которые являются концевыми для ребер из U’.

Пример 3.3. Выберем во множестве ребер U орграфа G примера 3.1 произвольным образом некоторое подмножество U₃ = {(v₂,v₁), (v₃,v₁), (v₂,v₄), (v₅,v₆)}. Тогда подграф

v₂ v₅

G₃:

v₁ v₃ v₄ v₆

является ребернопорожденным подграфом орграфа G.

Определение 3.4. Граф (орграф) называется связным, если для любой пары вершин графа одна из них достижима из другой.

Например, граф G’ примера 2.4 является связным, а граф G₃ примера 3.3 связным не является (например, не существует пути между вершинами v₁ и v₅).

Определение 3.5. Подграф G’ графа G называется максимальным, если для любого графа G’’ такого, что G’ ⥹ G’’ ⥹ G следует, что либо G’ = G’’ либо G’’ = G (иными словами, подграф G’ - максимальный подграф в графе G, если не существует собственного подграфа G’’ графа G, для которого подграф G’, в свою очередь, был бы собственным подграфом).

Пример 3..4. Пусть нам задан граф (псевдограф)

v₁ v₂ v₃ v₄ v₅

G:

v₆ v₇ v₈ v₉ v₁₀

Тогда, например, подграф

v₁ v₂ v₅

G₁:

v₆ v₇ v₁₀

не является компонентой графа G (поскольку не является связным). Подграф

v₁ v₂

G₂:

v₆ v₇

связный, но не является компонентой графа G (поскольку не является максимальным связным подграфом – он является собственным подграфом для связного подграфа G₃). Подграф

v₁ v₂

G₃:

v₆ v₇

является компонентой графа G (он не является собственным подграфом ни одного связного подграфа графа G). Подграф G₄ графа G не является компонентой графа G (почему?), но является максимальным (и остовным) подграфом G. Здесь G₄ – следующий подграф графа G:

v₁ v₂ v₃ v₄ v₅

G₄:

v₆ v₇ v₈ v₉ v₁₀

Исходный граф G имеет три компоненты связности (компоненты) – G₃, G₅, G₆, где G₃ отмечен раньше, а G₅ и G₆ - следующие подграфы:

v₃ v₄ v₅

G₅: G₆:

v₈ v₉ v₁₀

Дата добавления: 2014-12-16