1.3. Связность графов

Важным понятием в теории графов является связность. С решением вопроса о связности в графах связано решение ряда прикладных задач, в частности, задача кодирования состояний цифрового автомата.

Для неографа и орграфа понятия связности несколько отличаются.

Две вершины неографа считаются связанными, если существует маршрут, соединяющий эти вершины.

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

Компонентой связности неографа G называется его подграф G’, удовлетворяющий следующим условиям:

1. G’- связный граф

2. Добавление в G’ любой вершины v_i из графа G с рёбрами, инцидентными v_i, нарушает условие связности неографа G’.

Связный неограф всегда имеет только одну компоненту связности. Ею является сам неограф. Несвязный неограф состоит из нескольких компонент связности. На рис. 1.12 показан связный неограф, а на рис 1.13 – несвязный, содержащий две компоненты связности: G₁ и G₂.

Орграф называется сильно связным, если для любых его двух вершин v_i и v_j найдётся путь из v_i в v_j и путь из v_j в v_i.

Рис. 1.14 Рис. 1.15 Рис. 1.16

Орграф называется несильно связным, если для любых двух вершин v_i и v_j найдётся путь либо из v_i в v_j, либо из v_j в v_i. В остальных случаях граф называется несвязным.

Граф на рис. 1.14 - сильно связный, на рис. 1.15 – несильно связный, а на рис. 1.16 – несвязный.

Компонентой сильной связности орграфа G называется его подграф G’, удовлетворяющий следующим условиям:

1. G’ – сильно связный граф;

2. Добавление в G’ любой вершины v_i из G с дугами, инцидентными v_i, нарушает условие сильной связности подграфа G’.

Сильно связный орграф всегда имеет только одну компоненту сильной связности, которой является сам граф.

Если граф G = <V, U> имеет p компонент связности: G₁ = <V₁, U₁>, … , G_p = <V_p, U_p>, то очевидно, что

1) V=V₁ V₂  ….  V_p; U= U₁  U₂  …..  U_p; то есть G= G₁  …  G_p;

2) V_i  V_j = , U_i  U_j =  при i  j;

3) N₁ + N₂ + ….+ N_p=N; R₁ + R₂ +....+R_p=R.

Ребро, при удалении которого граф превращается в несвязный, называют мостом. На рис. 1.17 - R – мост.

Рис 1.17

Вершина, при удалении которой вместе с инцидентными ей рёбрами, граф

становится несвязным, называется сочленением.

Граф, не имеющий мостов и сочленений, называется неразделимым.

Если G’ получен из G удалением некоторых вершин, то S(G’) может быть получена из S(G) вычеркиванием строк и столбцов, соответствующих удаленным вершинам.

При проектировании сетей ЭВМ часто возникает задача следующего вида: имеется сеть, состоящая из центров хранения и передачи информации. Некоторые центры попарно соединены каналами, обмен информацией между центрами происходит либо непосредственно по каналу, если он есть, либо через другие центры и каналы.

Сеть считается исправной, если каждая пара центров может обмениваться информацией. Такой сети, естественно, можно поставить в соответствие граф, вершины которого – центры, а рёбра – каналы. Исправной сети будет соответствовать тогда связный граф.

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

Числом вершинной связности графа () называется наименьшее число вершин, удаление которых делает граф несвязным или одновершинным.

Рис 1.20

Например, для полного графа 1-ого порядка (G₁)=0, (G _n)=N-1, для простого цикла  (C _n)=2 (см. рис 1.20).

Числом рёберной связности графа () называется минимальное число рёбер, удаление которых превращает граф в несвязный. Если граф одновершинный, (G)=0.

 (G)  (G)

Для рассматриваемого примера сети ЭВМ числа (G) и (G) отражают чувствительность сети к разрушению центров и каналов, а точки сочленения и мосты оказываются наиболее уязвимыми местами сети.

Если deg(G) – минималь­ная степень вершин графа G, то очевидно, что (G)deg(G), поскольку удаление всех рёбер, инцидентных данной вершине, приводит к увеличению числа компонент графа. Почти для всех графов (G)=(G).

Если граф G несвязный или имеет мост, очевидно, что (G) =(G), а для любого графа верно неравенство:

(G)  (G)  (G)

Граф G называется k-связным, если (G)  k, и ребёрно k-связным, если (G)  k (рис. 1.21, 1.22).

Таким образом, граф односвязен тогда и только тогда, когда он связен, а двусвязные графы (2 –связные) –это графы без точек соединения и мостов.

Максимальный k-связный подграф называется k-компонентой графа или k-связной компонентой.

Особую роль в теории графов играют случаи, когда k=2 и k=3, поскольку, во-первых, такие графы встречаются в большинстве теоретических и практических задач, во-вторых, при таком числе связности удается дать обозримое описание графа.

Свойства двусвязных графов:

1. Степени вершин 2-связного графа больше 1.

2. Если G₁ и G₂ двусвязные и имеют не менее двух общих вершин, то граф G₁G₂ тоже двусвязный (рис. 1.24).

3. Если G-двусвязный граф, P- цепь, соединяющая две его вершины, то граф G  P тоже двусвязный.

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

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

Теорема Менгера: Наименьшее число вершин, разделяющих две несмежные вершины графа a и b, равно наибольшему числу попарно непересекающихся простых (a, b)-цепей этого графа.

Из теоремы Менгера непосредственно следует:

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