Сколько компонент связности в изображенных графах

Подсчет количества компонент связности у неориентированных графов

связным, если для любых двух различных вершин У( и у₂ существует простая незамкнутая цепь из V] в у₂. Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами или компонентами связности графа (7. Внутри каждой компоненты будет выполняться определение связности графа. Таким образом, несвязный граф имеет более одной (две или больше) компоненты. Связный граф всегда, по определению, состоит из одной компоненты.

где (/] — К₉, у которого удалили восемь ребер, имеющих одну общую вершину; (7₂ — К₇, у которого удалили три ребра, образующих цикл; (7₃ — Р_ь, к которому добавили три попарно несмежных ребра. Черта наверху обозначает дополнение указанного графа.

Решение такого рода задач удобнее всего демонстрировать в виде таблиц, так как заполнение каждой отдельной клетки, по сути, является очевидным. Для заданий а), б), в), г) решения и ответы даны в табл. 2.5—2.8.

Задача 2.23. Чему равно число компонент связности у графа, полученного в результате сложения полного графа на шести вершинах и простого цикла на восьми вершинах (общих вершин нет)?

Задача 2.24. Чему равно число компонент связности у графа, полученного в результате сложения регулярного графа на шести вершинах и простого цикла на десяти вершинах (общих вершин нет)?

Задача 2.25. Чему равно число компонент связности у графа, полученного в результате сложения пустого графа на пяти вершинах и пустого графа на десяти вершинах (общих вершин нет)?

Научный форум dxdy

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

Последний раз редактировалось gogoshik 26.07.2018, 20:14, всего редактировалось 5 раз(а).

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

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

Определение . Компонентой связности называется класс эквивалентности относительно связности.

Определение . Рассмотрим подграфы графа , порожденные множествами , т.е. для выполняется . Так как любые две вершины из связаны путем в , то этот путь будет связывать их и в . Следовательно, — связный граф. Нетрудно проверить, что множества образуют разбиение множества (возможен случай для некоторых , в этом случае — тривиальный) и для графа будет выполняться — дизъюнктное объединение графов . При этом подграфы называются компонентами связности графа .

Перечитал много раз и понял, что у данного графа будет одна компонента связности. Правильно?

Почему то сначала мне захотелось разбить граф на подмножества попарных вершин и соответствующих ребер. Получилось три ребра и три отдельные вершины. Я это принял за компоненты.

Поиск компонент связности

Компонентой связности неориентированного графа называется подмножество вершин, достижимых из какой-то заданной вершины. Как следствие неориентированности, все вершины компоненты связности достижимы друг из друга.

Граф с двумя компонентами связности

Дан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами. Требуется найти в нём все компоненты связности, то есть разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами путей не существует.

Для решения задачи модифицируем обход в глубину так, чтобы запустившись от вершины какой-то компоненты, от пометил все вершины этой компоненты — то есть все достижимые вершины — заданным номером этой компоненты. Для этого можно массив used заменить массивом номеров компонент для каждой вершины, изначально заполненный нулями:

Теперь проведем серию обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл, образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности. И так далее, пока все вершины не станут помеченными.

Записывается это очень компактно:

После этого переменная num будет хранить число компонент связности, а массив component — номер компоненты для каждой вершины, который, например, можно использовать, чтобы быстро проверять, существует ли путь между заданной парой вершин.

Итоговая асимптотика составит $O(n + m)$, потому что такой алгоритм не будет запускаться от одной и той же вершины дважды, и каждое ребро будет просмотрено ровно два раза (с одного конца и с другого).

§2.3. Связность

Определение. Граф называется связным , если любые две несовпадающие вершины в нем соединены маршрутом.

Очевидно, для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины и и каждой другой вершины v существовал ( u , v )-путь.

Пусть задан граф G . Введем на множестве его вершин V ( G ) бинарное

отношение. Будем говорить, что v i

v j , если существует путь из v i в

v j . При этом будет считать, что v i

v i , их соединяет путь нулевой

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

классы эквивалентности: V ( G ) = V 1 V 2 . V k . Обозначим через G i подграф графа G , порожденный множеством вершин V i . При этом

V ( G ) = V ( G 1 ) V ( G 2 ) . V ( G k ) ,

E ( G ) = E ( G 1 ) E ( G 2 ) . E ( G k ) , G = G 1 G 2 . G k .

Графы G 1 , G 2 , . G k называются компонентами связности графа G .

Теорема. Для любого графа либо он сам, либо его дополнение является связным.

Доказательство. Пусть G – несвязный граф. А – одна из его компонент связности. Положим В = VG \ VA . Возьмем произвольную вершину и графа А . Тогда для любой вершины v из из множества вершин В в

дополнительном графе G есть ребро uv . Следовательно, произвольная вершина из В соединена с и . Если и 1 – отличная от и вершина графа А , то для любой вершины v из множества вершин В в дополнительном

графе G также найдется ребро u 1 v . Таким образом найдется путь из вершины и в вершину u 1 (через вершину v ). Следовательно, из вершины

и в графе G достижима любая вершина, а значит, граф G является связным. Утверждение доказано.

Утверждение. Пусть G – связный граф, e EG . Тогда:

1) если ребро е принадлежит какому-либо циклу графа G , то граф G \ e связен;

2) если ребро е не входит ни в какой цикл, то граф G \ e имеет

ровно две компоненты связности.

Доказательство. 1). Пусть ребро e = uv принадлежит циклу Z

графа G . Заменив в каждой ( x , y ) -цепи, содержащей е , ребро е на цепь

Z \ e , получим путь, соединяющий вершины х и у , не содержащий ребра е . Следовательно, для любых двух несовпадающих вершин в графе G найдется ( x , y ) -путь, не включающий ребро е . Но тогда и граф

2) Пусть ребро е не входит ни в какой цикл графа G. Тогда, очевидно, вершины и и v входят в разные компоненты связности графа G \ e . Обозначим их через G u и G v соответственно. Для произвольной

вершины x ≠ u в G найдется ( x , u ) -путь. Если ребро е в этот путь не входит, то x G u . В противном случае x G v . Утверждение доказано.

Обозначим через Р количество ребер графа, В – количество вершин, K – количество компонент связности.

Определение. Число ν ( G ) = P − B + K называется цикломатическим

Теорема . Для любого графа G выполняется неравенство ν ( G ) ≥ 0.

Доказательство проведем индукцией по числу вершин п . При п = 1 получаем граф, состоящий из одной вершины, соответственно без ребер: P = 0, B = 1, K = 1, ν ( G ) = 0 . Неравенство ν ( G ) ≥ 0 выполнено.

Предположим, что при любом количестве вершин, меньшем п , утверждение верно и докажем его для графа с п вершинами. Обозначим их v 1 , v 2 , . v n . Обозначим через G ‘ подграф графа G , порожденный

вершинами v 1 , v 2 , . v n − 1 . Тогда ν ( G ‘ ) ≥ 0 по предположению индукции. Пусть P , B , K – количество ребер, вершин, компонент связности графа G ; P ‘, B ‘, K ‘ – графа G ‘ ; k – количество ребер графа G , не являющихся ребрами графа G ‘ , т.е. степень вершины v n . Тогда P = P ‘ + k , B = B ‘ + 1 . Возможны два случая.

а) k = 0 , следовательно, вершина v n – изолированная. При этом

P = P ‘, B = B ‘ + 1, K = K ‘ + 1 . Следовательно, P − B + K = P ‘ − B ‘ + K ‘ ,

ν ( G ‘ ) = ν ( G ) ≥ 0 .

б) k > 0 . Если при этом все k ребер, инцидентных вершине v n , соединяют ее с различными компонентами связности графа G ‘ , то K = K ‘ + 1 − k , в остальных случаях K > K ‘ + 1 − k . Таким образом, K ≥ K ‘ + 1 − k . В итоге получаем

P − B + K ≥ P ‘ + k − B ‘ − 1 + K ‘ + 1 − k = P ‘ − B ‘ + K ‘ , ν ( G ) ≥ ν ( G ‘ ) ≥ 0 .

Следствие . Для связного графа выполняется неравенство B ≤ P + 1 .

Определение. Связный граф без циклов называется деревом . Любой

граф без циклов называется

ациклическим (или лесом ). Таким образом, компонентами связности леса являются деревья. На рис. 2.31

изображен лес, каждая компонента связности его является деревом. Теорема . Связный граф является деревом тогда и только тогда, когда число его вершин на единицу больше числа его ребер, т.е. B = P + 1 . Доказательство . Необходимость. Заметим, что если граф G – дерево, то он имеет хотя бы одну вершину степени 1 (висячую вершину).

Действительно, предположим, что все вершины имеют степень, не меньшую 2. Возьмем произвольную вершину, обозначим ее v 1 . Из нее

выходит по крайней мере два ребра. Найдется вершина v 2 такая, что e 1 = ( v 1 , v 2 ) EG . Так как степень вершины v 2 не меньше 2, то найдется вершина v 3 , отличная от v 1 , такая, что e 2 = ( v 2 , v 3 ) EG , и так далее.

Так как число вершин конечно, то в этой последовательности вершин найдутся совпадающие, и мы получим цикл, что противоречит определению дерева. Следовательно, висячая вершина существует. Далее доказательство проведем индукцией по числу вершин п . При п = 1 число ребер равно 0 и утверждение верно. Предположим оно верно при любом количестве вершин, меньшем п . Рассмотрим граф G с п вершинами. Среди них есть висячая. Рассмотрим подграф G ‘, порожденный множеством остальных вершин. Для него по индукционному предположению P ‘ = B ‘ − 1 . Кроме того,

P = P ‘ + 1, B = B ‘ + 1 . Следовательно, P = B − 1 . Необходимость доказана.

Достаточность. Пусть для связного графа G выполняется условие P = B − 1 . Для того, чтобы доказать, что G является деревом, нужно показать лишь отсутствие циклов. Предположим, что циклы есть, тогда удаление одного ребра е из цикла не нарушает связности, граф

тоже связный. Следовательно, для него выполняется неравенство P ‘ ≥ B ‘ − 1. Но P ‘ = P − 1, B ‘ = B , следовательно, P ≥ B и значит,

P > B − 1 , что противоречит условию. Следовательно, G является связным графом без циклов, т.е. деревом. Теорема доказана.

1. Любые две вершины дерева можно соединить путем. Если это простой путь, то он единственный.

2. Если для некоторого дерева G V ( G ) ≥ 2, то оно имеет не менее двух висячих вершин.

Существуют способы задания деревьев, более экономичные, чем с помощью матриц смежности и инцидентности, которые в компьютере

занимают много памяти.

Первый способ кодирования. Пусть Т – дерево,

n = | E ( T ) | = | V ( T ) | − 1 . Поставим в соответствие

дереву Т с п ребрами слово, состоящее из 0 и 1

длиной 2 п следующим образом. Выберем

произвольно вершину и начнем обход дерева по

произвольному ребру так, чтобы ребра все время

оставались справа, поворачивая в висячих

вершинах. Если ребро встретилось в первый раз,

записываем 0, во второй – 1. Код дерева,

представленного на рис.2.32 – (010010101101)

(обход начат с вершины 1).

Заметим, что дереву с одним ребром сопоставляется код (01). Если

деревьям Т 1 и Т 2 (рис.2.33, а) сопоставлены коды α

и β соответственно, то дереву С (рис. 2.33, б) сопоставляется код (0 α

C T 1

деревьям D и E (рис. 2.33, в) – коды αβ

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

Построение дерева по коду

Для того чтобы восстановить дерево по коду, нужно разбить последовательность на пары из нулей и единиц, соответствующие одному и тому же дереву. Первая попавшаяся в коде единица образует пару с предшествующим нулем. Каждая следующая образует пару с ближайшим слева неиспользованным нулем. Пометим пары снизу дугами, которые соответствуют ребрам графа, занумеровав их. Например, если дан код (010010010111010011), поступим так (см. рис. 2.34а). Дерево, соответствующее этому коду, изображено на рис. 2.34б.

Второй способ кодирования

Перенумеруем вершины дерева произвольным образом (рис.2.35). Найдем висячую вершину с наименьшим номером. Запишем номер единственной смежной с ней вершины и удалим висячую вершину вместе с ребром. Для получившегося дерева снова найдем висячую вершину с наименьшим номером и т. д., пока не останется одно ребро. Длина кода при этом равна | E | – 1 = | V | – 2.

Пример. Построить код дерева, изображенного на рис. 2.35. Висячая вершина с наименьшим номером – 1, смежная с ней – 2.

Удаляем вершину 1 вместе с ребром и записываем в код 2. В оставшемся дереве висячая вершина с наименьшим номером – 5, смежная с ней – 4. Удаляем вершину 5 вместе с ребром и записываем в код 4. В оставшемся дереве висячая вершина с наименьшим номером – 6, смежная с ней – 4. Удаляем вершину 6 вместе с ребром и снова записываем в код 4. В оставшемся дереве висячая вершина с наименьшим номером – 7, смежная с ней – 4. Удаляем вершину 7 вместе с ребром и снова записываем в код 4. В оставшемся дереве

висячая вершина с наименьшим номером – 4, смежная с ней – 2. Удаляем вершину 4 вместе с ребром и записываем в код 2. В оставшемся дереве висячая вершина с наименьшим номером – 2, смежная с ней – 3. Удаляем вершину 2 вместе с ребром и записываем в код 3. Осталось одно ребро. Получили код дерева [244423].

Восстановление дерева по коду рассмотрим на примере кода

[2557389]. Вместо первого числа в коде пишем наименьшее, не встречающееся в коде: 1557389. Вместо второго числа в новой последовательности пишем наименьшее, не встречающееся в ней: 1257389 и т.д. Получаем последовательность 1245637. Расположив ее под кодом, получим список ребер: (2,1), (5, 2), (5, 4), (7, 5), (3,6), (8,3),

числа 8 и 9. Соединяем

вершины 8 и 9 ребром и

получаем граф (рис.

Можно показать, что между помеченными деревьями (т.е. деревьями с пронумерованными вершинами) и последовательностями

ε 1 , ε 2 , . ε n − 2 , где 1 ≤ ε i ≤ n , существует взаимно однозначное

соответствие. Поэтому количество помеченных деревьев равно n n − 2

Эйлеровы пути. Эйлеровы циклы

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

Теорема. Пусть дан связный граф. В нем существует э йлеров путь тогда и только тогда, когда две вершины графа имеют нечетную степень, а все остальные – четную. Эйлеров цикл существует тогда и только тогда, когда все вершины графа имеют четную степень.

Доказательство. Доказательство обеих частей теоремы проведем одновременно.

Необходимость . Пусть в графе G существует эйлеров

путь из а в b . Тогда d ( a ) –

нечетное число. Действительно,

из а выходит по крайней мере

одно ребро, обозначим его е 1 .

Если путь возвращается в а по

ребру е 2 , то он должен и

выходить из него по ребру е 3 , и так далее (рис. 2.38,а). Степень вершины а – нечетная. Аналогично для

вершины b . Если путь из а в а – эйлеров цикл, то первое и последнее ребро цикла инцидентны а . Если вершина а встречается внутри цикла, то вместе с ребром ( v i , a ) он содержит и ребро ( a , v k ) . Степень

вершины а – четная. Остальные вершины являются внутренними и для эйлерова пути, и для эйлерова цикла, поэтому, если путь или цикл содержит ребро ( v i , v j ) , то он содержит и ребро ( v j , v k ) , если v j ≠ b .

Так как все ребра в пути и цикле встречаются ровно один раз, то степень вершины v j – четная (рис.2.38,б).

Достаточность . Доказательство проведем индукцией по количеству ребер. Пусть d ( a ) , d ( b ) – нечетные. Наименьшее

количество ребер равно 1. При этом граф G состоит из двух вершин а и b и соединяющего их ребра, который и будет

являться эйлеровым путем. Если степени всех вершин четные, то наименьшее количество ребер равно трем (при отсутствии кратных

ребер). Если степени всех вершин четные, возможен только граф, изображенный на рис.

2.39. Эйлеров цикл существует. Предположим, для графа с количеством ребер, меньшим п , утверждение истинно. Докажем утверждение

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

вершины. Для нового графа рассмотрим эйлеров цикл из b в b . Присоединив к нему ребро ( а , b ) (если нужно, вместе с вершиной а ), получим эйлеров путь из b в а в исходном графе.

Если произвольное ребро, выходящее из а , – это ребро ( а , с ),

c ≠ b , то, удалив его, получим, что степень вершины а стала четной, а степень вершины с – нечетной, число ребер уменьшилось на 1. Если удаление ребра нарушает связность, то удалим вместе с ребром и вершину а . В новом графе G’ также две вершины с четными степенями ( b и с ), остальные – с нечетными степенями. По предположению индукции в G’ существует эйлеров путь из с в b . Добавив к нему ребро ( а , с ), получим эйлеров путь из а в b .

Докажем теперь утверждение для эйлерова цикла с п ребрами. Пусть связный граф G имеет вершины только с четными степенями. Удалив из него одно ребро, например, ( а , b ) , получим граф G’ , у которого степени двух вершин нечетны, остальные – четны. Предположим, что удаление ребра нарушило связность графа, т.е. у графа G’ две компоненты связности G 1 и G 2 , при этом вершины с нечетными степенями а и b находятся в разных компонентах связности. Тогда сумма степеней вершин для каждого из графов G 1 и G 2 нечетна, чего не может быть. Следовательно, граф G’ – связный, и по индукционному предположению в нем существует эйлеров путь из а в b . Добавив к эйлерову пути ребро ( а , b ), получим эйлеров цикл. Теорема доказана.

Теорема о цикломатическом числе

Напомним, что цикломатическим числом графа G называется число ν ( G ) = P − B + K , где P – число ребер, B – число вершин, K – число

компонент связности графа G . Было доказано, что для любого графа ν ( G ) ≥ 0 , для дерева ν ( G ) = 0 .

Теорема. Если граф G состоит из нескольких компонент связности

G 1 , G 2 , . G k , то ν ( G ) = ν ( G 1 ) + ν ( G 2 ) + . + ν ( G k ) .

Доказательство. Так как графы G 1 , G 2 , . G k – связные графы, то

ν ( G 1 ) = P 1 − B 1 + 1 , ν ( G 2 ) = P 2 − B 2 + 1 , …, ν ( G k ) = P k − B k + 1 .

Сложив почленно эти равенства, получим

∑ ν ( G i ) = P − B + K = ν ( G ) . теорема доказана.

Введем определение суммы циклов произвольного графа. Пусть С 1 и С 2

– произвольные циклы графа G , содержащие общие участки пути, соединяющие вершины