Читать «Математический аппарат инженера» онлайн - страница 33

Рис. 11. Граф и его части:

а - граф; б - часть графа; в - подграф; г – суграф.

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу - сверхграфом. Совокупность всех ребер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа. Говорят, что подграфы G' = (V', Е') и G" = (V", Е") разделены ребрами, если они не имеют общих ребер (Е' ∩ Е" =∅) и разделены вершинами, если у них нет общих вершин (V' ∩ V" =∅).

10. Связность. Две вершины графа называют связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называют связным графом. Очевидно, в связном графе между любыми двумя вершинами существует простая цепь, так как из связывающего их маршрута всегда можно удалить циклический участок, проходящий через некоторую вершину более одного раза (Рис. 12, где маршрут между вершинами v_i и v_j, изображен жирными линиями).

Если граф не связный, то множество его вершин можно единственным образом разделить на непересекающиеся подмножества, каждое из которых содержит все связанные между собой вершины и вместе с инцидентными им ребрами образует связный подграф.

- 53 -

Таким образом, несвязный граф представляет собой совокупность отдельных частей (подграфов), называемых компонентами. На Рис. 13 показан подграф, состоящий из трех компонент (изолированная вершина считается компонентой).

Часто отношение связности усложняется дополнительными условиями. Граф называют циклически связным, если любые две различные вершины содержатся в цикле (например, граф на Рис. 11, а циклически связный, а граф на Рис. 12 - нет, так как вершина и, не содержится ни в каком цикле с другими вершинами). Граф называют R - связным, если любая пара различных вершин связана, по крайней мере R цепями, которые не имеют общих вершин (кроме начальной и конечной). Так, граф на Рис. 11, а двусвязный, а на Рис. 12 - односвязный.

Рис. 12. Связный граф.

Рис. 13. Несвязный граф, состоящий из трех компонент (G₁, G₂, G₃

Связность ориентированных графов определяется так же, как и для неориентированных (без учета направлений дуг). Специфичным для орграфа (или смешанного графа) является понятие сильной связности. Орграф называют сильно связным, если для любой пары его вершин v_i и v_j существует путь из v_i в v_j и из v_j в v_i , (например, граф на Рис. 8, а сильно связный). Граф, представляющий план города с односторонним движением по некоторым улицам, должен быть сильно связным, так как в противном случае нашлись бы вершины (площади и перекрестки), между которыми нельзя было бы проехать по городу без нарушения правил движения.

11. Разделимость. Связный граф может быть разделен на несвязные подграфы удалением из него некоторых вершин и ребер (при удалении вершин исключаются и все инцидентные им ребра, а при удалении ребер вершины сохраняются). Если существует такая вершина, удаление которой превращает связный граф (или компоненту несвязного графа) в несвязный, то она называется точкой сочленения (Рис. 14, а). Ребро с такими же свойствами называется мостом (Рис. 14, б). Ясно, что при наличии моста в графе имеется, по крайней мере, две точки сочленения.