§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 α ~ 1), а
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 , содержащие общие участки пути, соединяющие вершины
Теорема о цикломатическом числе
Напомним, что цикломатическим числом графа G называется число , где – число ребер, – число вершин, – число компонент связности графа G.
Было доказано, что для любого графа , для дерева .
Теорема. Если граф состоит из нескольких компонент связности , то .
Доказательство. Так как графы – связные графы, то , …, . Сложив почленно эти равенства, получим . Теорема доказана.
Введем определение суммы циклов произвольного графа. Пусть С1 и С2 – произвольные циклы графа G, содержащие общие участки пути, соединяющие вершины и , и и так далее. Тогда суммой циклов С1 и С2 будем называть граф, вершинами которого являются все вершины циклов С1 и С2, за исключением внутренних вершин их общих участков, а ребрами – все их ребра, за исключением ребер, составляющих их общие участки (рис.
2.40). Если циклы С1 и С2 не имеют общих участков, то их суммой называется объединение циклов С1 + С2 = С1 È С2. Вообще говоря, сумма двух циклов, даже и имеющих общие ребра, может не являться сама циклом, но является объединение простых циклов. Далее под циклом везде подразумевается либо простой цикл, либо объединение простых циклов. Очевидно, что , . По сложению циклы образуют абелеву группу.
Если граф G имеет т ребер е1, е1, … ет, то любому циклу С графа G можно поставить в соответствие двоичный код длины т: ,
Если циклу С1 соответствует код , а циклу С2 – код , то циклу С1+С2 соответствует код , где сложение производится по модулю 2. Таким образом, множество циклов графа G можно рассматривать, как подгруппу группы . Циклы образуют линейное пространство над полем .
Теорема. Пусть дан произвольный граф G (без петель, без кратных ребер, с конечным числом вершин) и . Тогда:
1) Из графа G можно удалить k ребер так, что оставшийся граф будет без циклов и будет иметь столько же компонент связности, что и G.
2) Размерность пространства циклов графа G равна k.
Доказательство. . Докажем, что тогда только тогда, когда в графе G нет циклов.
Действительно, если , а – компоненты связности графа G, то . Так как , то при всяком . Имеем , следовательно, – дерево, а значит, в нет циклов. Таким образом, в графе G тоже нет циклов.
Докажем, что если в графе G нет циклов, то . Действительно, тогда G – лес, , где , – компоненты связности графа G, т.е. деревья. Так как для дерева , то .
Таким образом, мы доказали, что если для графа G , то в нем нет циклов.
Пусть теперь . Тогда в G есть циклы. Возьмем произвольно цикл С1, е1 – произвольное ребро этого цикла. Тогда граф имеет то же количество компонент связности, что и G. .
Если , то полученный граф будет без циклов. Если , то аналогично берем цикл С2 и ребро е2 и т.д. Этот процесс состоит ровно из шагов. На каждом шаге количество компонент связности не меняется. Граф является лесом, количество компонент связности у него такое же, как и у G.
. Занумеруем остальные ребра графа G: . Тогда циклам С1, …,Сk соответствуют коды
Строки кодов линейно независимы. Осталось доказать, что любой цикл графа G можно линейно выразить через циклы С1, С2, …, Сk.. Возьмем произвольный цикл С с соответствующим ему кодом . Строки
линейно независимы, следовательно, образуют базис в пространстве размерности k. Поэтому
при некоторых . Рассмотрим цикл
Учитывая, что , получаем
Таким образом, – цикл в графе . Но по построению, – граф без циклов.
Следовательно, и , значит,
Если G – связный граф и , то по только что доказанной теореме из G можно удалить некоторые k ребер так, чтобы получилось дерево Т. Назовем его остовным деревом графа G. Аналогично, если G – несвязный граф, то из G можно удалить некоторые k ребер так, чтобы получился граф без циклов, т.е. лес, называемый остовным лесом графа G. Решение типовых задач
1. Существует ли Эйлеров цикл у графа, изображенного на рис. 2.41? Если существует, построить его.
Решение. Так как степени всех вершин четны, тот эйлеров цикл существует. Возьмем произвольный цикл, например, (1, 5, 3, 1). Этот цикл не содержит все ребра графа. Рассмотрим граф, полученный из исходного удалением этого цикла. Удаленный граф и оставшийся, в силу связности исходного графа всегда имеют общую вершину, в данном случае – 5. Рассмотрим теперь произвольный цикл нового графа, начинающийся в вершине 5, например, (5, 4, 6, 5). Присоединим его к первому циклу: (1, 5, 4, 6, 5, 3, 1). Остается единственный цикл (4, 1, 2, 4), присоединив который, получим эйлеров цикл (1, 5, 4, 1, 2, 4, 6, 5, 3, 1).
2. Найти число компонент связности леса, который имеет 40 вершин и 23 ребра.
Решение. Так как для леса , получаем , .
3. Чему может равняться число ребер графа, имеющего 20 вершин и 4 компоненты связности?
Решение. Так как , имеем , следовательно, . Покажем, что найдется граф, для которого , , .
Пусть 3 компоненты связности – изолированные вершины, четвертая – простая цепь С17 с 16 ребрами. Таким образом, минимальное число ребер равно 16. Выясним, каким может быть максимальное число ребер.
Докажем, что наибольшее количество ребер у графа, три компоненты связности которого представляют собой изолированные вершины, четвертая – полны граф К17 с числом ребер, равным 136. Действительно, рассмотрим граф с 20 вершинами и 4 компонентами связности , из которых по крайней мере 2 содержат не менее двух вершин. Предположим, что . Возьмем произвольно вершину из , удалим все ребра, инцидентные ей, и соединим ее ребрами со всеми вершинами из . Новый граф будет иметь то же количество вершин и компонент связности, но больше ребер. Таким образом, количество ребер может быть от 16 до 136.
4. Чему может равняться число компонент связности графа, имеющего 12 вершин и 27 ребер?
Решение. Так как простая цепь С12 имеет 11 ребер, а полный граф К12 – 66 ребер, то существует связный граф, имеющий 12 вершин и 27 ребер. Минимальное число компонент связности равно 1. Для того, чтобы определить максимально возможное число компонент связности, найдем наименьший полный граф, число ребер которого не меньше 27: . Рассмотрим граф, 4 компоненты связности представляют собой изолированные вершины, а пятая имеет 8 вершин и 27 ребер. Докажем, что 6 компонент связности быть уже не может. Действительно, по предыдущей задаче, граф, имеющий 12 вершин и 6 компонент связности, может иметь не более 21 ребра. Таким образом Таким образом, количество компонент связности может быть от 1 до 5.
5. Для графа, изображенного на рис.2.42(а) найти цикломатическое число, укзать базис циклов, построить остовное дерево.
Для данного графа , , . Следовательно, и из надо удалить три ребра, чтобы получилось дерево. Базис циклов также состоит из трех циклов. Выберем произвольно цикл, например, . Удалим из графа ребро е2. В получившемся графе возьмем цикл . Удалим из графа ребро е5. В получившемся графе возьмем цикл . Удалим из графа ребро е10. Получим остовное дерево графа , изображенное на рис. 2.42б). Циклы С1, С2, С3 образуют базис. Разложим какой-нибудь цикл, например, , по этому базису. Запишем коды циклов:
Так как были удалены ребра е2, е5, е10, то в матрице, составленной из кодов циклов С1, С2, С3, С4, базисным будет минор, составленный из столбцов под номерами 2, 5, 10: .
Отсюда получаем . Задачи для самостоятельного решения
1. Сколько компонент связности имеет граф со следующим набором степеней вершин: 1, 1, 1, 2, 2, 2, 2, 3?
2. Изобразить граф . Найти , построить базис циклов.
3. Изобразить граф . Найти , построить базис циклов.
4. Построить базис циклов графа .
5. Построить базис циклов графа .
6. Построить базис циклов графа .
7. Построить базис циклов графа .
8. Является ли деревом прямое произведение деревьев?
9. Найти число компонент связности леса, который имеет 76 вершин и 53 ребра.
10. Сколько ребер имеет лес с 10 вершинами, если он имеет 3 компоненты связности?
11. Чему может равняться число компонент связности графа, имеющего 15 вершин и 35 ребер?
12. Чему может равняться число компонент связности графа, имеющего 12 вершин и 20 ребер?
13. Чему может равняться число ребер графа, имеющего 10 вершин и 3 компоненты связности?
14. Доказать, что если граф имеет 10 вершин и 37 ребер, то он связен.
15. Доказать, что если граф имеет 8 вершин и 23 ребра, то он связен.
16. Связный граф имеет 12 вершин. Сколько он может иметь ребер?
17. Сколько ребер может быть у связного графа с п вершинами?
18. Сколько всего неизоморфных деревьев с пятью вершинами? Изобразить их.
19. Сколько всего графов с 12 вершинами и 65 ребрами? с 64 ребрами?
20. Построить коды деревьев (два для каждого дерева), изображенных на рис. 2.43.
21. Построить дерево по коду (00101001011101).
22. Построить дерево по коду (00101011001101).
23. Построить дерево по коду [5345566].
24. Построить дерево по коду [4445477].
У каких из графов, изображенных на рис. 2.44, существует эйлеров путь или эйлеров цикл? Если существует, то построить его.
1. 1 или 2. Указание. Рассмотреть, сколько вершин может быть в каждой компоненте связности. 2. См. рис. 2.45. . Базис циклов: (1, 2, 3), (1, 3, 6, 4), (3, 2, 5, 6), (1, 2, 5, 4). 3. . 4. .
5. . 6. . 7. . 8. Не является (см. рис. 2.12).
9. 23. 10. 7. 11. От 1 до 7. 12. От 1 до 6. 13. От 7 до 28. 14. Указание. Доказать, что несвязный граф с 10 вершинами имеет не более 36 ребер. 15. Указание. Доказать, что несвязный граф с 8 вершинами имеет не более 21 ребра. 16. От 11 до 66. 17. От до . 18. 3 , см рис. 2.46. Указание. Рассмотреть возможные наборы степеней вершин. 19. Один, два. 20. При нумерации, указанной на рис. 2.47:
а) (01000010110101101101), [114457557]; б) (0000101110010111); [2332477]; в) (0010100101011011), [ 4444666];
г) (00001010101111), [246666]. 21. См. рис. 2.48а . 22. См. рис. 2.48б.
23. См. рис. 2.48в. 24. См. рис. 2.48г. 25. а), в) – существует; б) нет.
Количество компонент связности в дополнении заданного графа
В программе используются следующие определения.
Граф представляет собой множество точек (вершин, узлов) вместе с линиями, соединяющими некоторые или все пары точек. Направленные линии со стрелками называют дугами, не имеющие направления – ребрами.
2. ОПИСАНИЕ ПРИМЕНЕНИЯ.
2.1. Постановка задачи.
2.2. Обращение к программе.
2.3. Входные данные.
2.4. Выходные данные.
2.5.1. Информационные сообщения.
2.5.2. Сообщения об ошибках.
3. ОПИСАНИЕ ПРОГРАММЫ.
3.1. Структура программы.
3.2. Описание модулей.
3.2.1. main – главный модуль.
3.2.2. vvod – функция ввода данных.
3.2.3. vivod– функция вывода матрицы.
3.2.4. matrica_dopolnenii– функция получения дополнения графа.
3.2.5. matrica_sviaznosti – функция матрицы связности графа.
3.2.6. comp_sv– функция количества компонент связности.
4. ОТЛАДКА ПРОГРАММЫ.
4.1. План отладки.
4.2. Проектирование тестов программы.
4.2.1. Тесты черного ящика.
4.2.2. Тесты белого ящика.
4.3 Отладочные средства.
4.4 Отладка программы.
Работа содержит 1 файл
Курсовая работа по программированию.doc
Министерство образования Российской Федерации
Казанский Государственный Технический Университет
имени А.Н. Туполева
К У Р С О В А Я Р А Б О Т А
По программированию на языке высокого уровня
Количество компонент связности в дополнении заданного графа.
ИСПОЛНИТЕЛЬ: студент группы 28203 С.Н. Трофимова
РУКОВОДИТЕЛЬ: доцент кафедры АСОИУ З.Х. Захарова
2. ОПИСАНИЕ ПРИМЕНЕНИЯ.
2.1. Постановка задачи.
2.2. Обращение к программе.
2.3. Входные данные.
2.4. Выходные данные.
2.5.1. Информационные сообщения.
2.5.2. Сообщения об ошибках.
3. ОПИСАНИЕ ПРОГРАММЫ.
3.1. Структура программы.
3.2. Описание модулей.
3.2.1. main – главный модуль.
3.2.2. vvod – функция ввода данных.
3.2.3. vivod– функция вывода матрицы.
3.2.4. matrica_dopolnenii– функция получения дополнения графа.
3.2.5. matrica_sviaznosti – функция матрицы связности графа.
3.2.6. comp_sv– функция количества компонент связности.
4. ОТЛАДКА ПРОГРАММЫ.
4.1. План отладки.
4.2. Проектирование тестов программы.
4.2.1. Тесты черного ящика.
4.2.2. Тесты белого ящика.
4.3 Отладочные средства.
4.4 Отладка программы.
СПИСОК ЛИТЕРАТУРЫ
- Системные файлы проекта.
- Текст программы модуля main
- Текст программы модуля vvod
- Текст программы модуля vivod
- Текст программы модуля matrica_dopolnenii
- Текст программы модуля matrica_sviaznosti
- Текст программы модуля comp_sv
- Результаты тестирования программы
- Трудоемкость курсовой работы
Подсчитать количество компонент связности в дополнении заданного графа.
2. ОПИСАНИЕ ПРИМЕНЕНИЯ
2.1. Постановка задачи
Разработанная программа подсчитывает количество компонент связности в дополнении заданного графа с количеством вершин ≤ 150.
В программе используются следующие определения.
Граф представляет собой множество точек (вершин, узлов) вместе с линиями, соединяющими некоторые или все пары точек. Направленные линии со стрелками называют дугами, не имеющие направления – ребрами.
Вершины, соединенные ребром или дугой, называют смежными. Ребра, имеющие общую вершину, также называются смежными. Представление квадратной булевой матрицы, отражающей смежность вершин, называется матрицей смежности, где
Дополнением графа является дополнение данного графа до полного. В ограниченной решетке элемент называется дополнением элемента а , если и .
Граф связан тогда, когда его нельзя представит в виде объединения двух графов. Говорят, что две вершины связаны, если между ними существует их простая цепь.
Матрица связности С размера n*n содержит элементы:
Матрица связности С получается :
Обозначим С(k)[ i , j ] – есть путь от i к j через вершины множества .
Тогда без промежуточных вершин:
С (-1) [ i , j ] = A [ i , j ] (A – матрица смежности графа)
Если через две вершины из множества есть путь от i до j или есть два пути : от i до k и от k до j , то есть путь от i к j через вершины из множества . Отсюда:
C(k)[ i , j ] = C(k-1)[ i , j ] | | C(k-1)[ i , k ] & C(k-1)[ k, j ].
Отношение связности вершин является эквивалентностью. Классы эквивалентности по отношению к связности называют компонентом связности графа.
где p – число вершин;
q – число ребер;
k – число компонент связности.
Решаемая задача иллюстрируется рис. 2.1. и 2.2. На рис. 2.1. изображен граф, для которого необходимо определить количество компонент связности в его дополнении. На рис. 2.2. изображено дополнение графа с 2 компонентами связности.
2.2. Обращение к программе
Запуск программы производится командой операционной системы MS DOS вида
где TROFIMOVA – имя файла, содержащего исполняемый модуль программы, входной файл – имя входного файла, выходной файл – имя выходного файла. Файлы задаются в произвольном порядке. Если входной файл не указан, исходные данные вводятся с клавиатуры, если не указан выходной файл, результаты выводятся на экран дисплея.
2.3. Входные данные
Входными данными программы является граф. Выбор метода представления графа зависит от конкретной задачи. В данном случае граф представляется последовательностью (списком) рёбер, перед которой указывается количество вершин n (где n не должно быть меньше 1 и больше 150). Такой метод очень удобен для внешнего представления графа при вводе.
Каждое ребро задаётся парой номеров вершин. Они нумеруются от 0 до n-1. Номера вершин разделяются пробелом. Ввод количества вершин заканчивается клавишей . Ввод ребра также заканчивается клавишей . а ввод списка ребер — , (обозначает конец файла).
Ниже приводится пример задания входных данных:
2.4. Выходные данные
Результатом работы программы, то есть её выходными данными будут сообщения, последовательно выводимые на экран дисплея. При этом входные данные тоже можно увидеть на экране. Рассмотрим результаты обработки графа на следующем примере:
Zadanie: Podchitat kol-vo component sviaznosti v dopolnenii zadannogo grafa.
Vvedite kol-vo verchin (ot 2 do 150).
Vvedite rebra grafa (ctrl+z).
Сколько компонент связности в изображенных графах
Задан неориентированный невзвешенный граф. Найдите количество его компонент связности.
Вход. В первой строке содержится количество вершин n (n ≤ 100) в графе. Далее в n строках задается по n чисел – матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Выход. Выведите количество компонент связности графа.
Пример входа
Пример выхода
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
РЕШЕНИЕ
графы – компоненты связности
Используя систему непересекающихся множеств, ищем количество компонент связности в графе.
Изначально расположим каждую вершину в отдельном множестве. Каждая вершина является представителем своего множества .
Далее для каждого ребра (u, v) объединим множества, содержащие u и v . После обработки всех ребер количество компонент связности равно числу множеств в системе непересекающихся множеств.
Задачу можно решить также при помощи поиска в глубину. Количество вызовов функции dfs будет равно числу компонент связности графа.
Приведенный в примере граф имеет вид:
Изначально расположим каждую вершину в отдельном множестве. Каждая вершина является представителем своего множества .
Далее для каждого ребра (u, v) объединим множества, содержащие u и v . После обработки всех ребер две вершины будут находиться в одной компоненте связности если у них одинаковый представитель .
Количество компонент связности равно числу множеств в системе непересекающихся множеств. Количество множеств равно числу представителей, а именно количеству таких v, для которых parent[v] = v . В примере имеется три представителя: 3, 5 и 6. То есть в графе имеется три компоненты связности.
В MAX содержится максимальное количество вершин в графе. В mas[i] содержится номер вершины, на которую указывает вершина i.
Функция Repr возвращает номер вершины – представителя множества, содержащего вершину n. Двигаемся по указателю на следующий элемент, пока не встретим представителя множества (его указатель указывает на него самого).
while (n != mas[n]) n = mas[n];
Функция Union объединяет два множества, которые содержат вершины x и y. Ищем представителей множеств, содержащих x и y. Пусть этими представителями будут x1 и y1. Если x1 = y1, то x и y содержатся в одном множестве, и в таком случае ничего делать не надо. Иначе указатель представителя x1 перенаправляем на y1.
void Union( int x, int y)
int x1 = Repr(x),y1 = Repr(y);
if (x1 == y1) return ;
Основная часть программы. Изначально каждая вершина указывает сама на себя (mas[i] = i).
if (i > j) continue ;
if (value) Union(i,j);
Подсчитываем количество компонент связности в переменной count. Оно равно количеству вершин – представителей множеств (которые указывают сами на себя).
if (mas[i] == i) count++;
printf( «%d\n» ,count);
Реализация алгоритма – поиск в глубину
int g[MAX][MAX], used[MAX];