XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 58
Текст из файла (страница 58)
рис. 5.43). Это значит, что каждая сумма И~~ 6 Ю~, о = О, п-1, есть цикл (в пространстве цепей графа С). Обозначим его ооо. Ь„ а, Ъуо о Рис. 5.43 Докажем, что циклы х; попарно не пересекаются (т.е. не имеют попарно ни общих вершин, ни общих ребер). Действительно, цепи Ю1 и ФУ~ при о ~ у не могут иметь ни общих вершин, ни общих ребер, так как вершины ам 6м аз, 6з, ..., аа, 6„— это, по построению, все вершины, общие для циклов С~ и Сз.
В то же время (для фиксированного а Е (1, 2)) никакие две цепи И~о и И'о при о ~ у не могут иметь общих вершин и 362 О. ТЕОРИЯ ГРАФОВ ребер, так как тогда циклы С1 или Сз не были бы простыми цепями. Итак, циклы х; попарно не пересекаются. Тогда С1ЕСз =мо9ь1Е" Юьа-1~ причем в том и только в том случае, когда множество ребер (е1,..., е„) формирует цепь, написанная вьппе сумма есть цикл. Аналогично рассматривается случай, когда циклы С1 и Сз, не имея общих ребер, имеют общие вершины: а1, аз, ..., а„ (рис. 5.44).
Тогда, как можно видеть на рис. 5А4, сумма С1 8 Сг будет замкнутой цепью (которал в общем случае не будет циклом). а, Рис. 5.44 Пусть С вЂ” произвольный цикл графа, а у1, ..., (;„— все его обратные ребра, и пусть Р1, ..., Р„, — фундаментальные циклы, содержащие ребра ум ..., у„, соответственно. Рассмотрим суммы (в пространстве циклов): 363 5.9. Элемевты лккломаткки Как было доказано выше, каждан нз этих сумм есть либо ззмкнутая цепь, либо множество попарно не пересекающихся циклов, причем сумма С;, 1 <1< 11 — 1, содержит обратные ребра Л+1> " ~ Уем и только их, так как при сложении С с Р1 исчезает общее для них ребро ~1, при сложении С1 с Р2 — общее для них ребро у2 и т.д.
Следовательно, последнии иэ этих сумм содержит единственное обратное ребро Д,. Значит, сумма С 1 есть цикл. В самом деле, если бы она была непустым множеством попарно не пересекающихся циклов, то содержала бЫ ПО КрайНЕй МЕРЕ дза таКИХ цИКЛа. ПОСКОЛЬКУ В Стл 1 ТОЛЬКО одно обратное ребро, то по крайней мере один иэ этих циклов проходил бы только по древесным ребрам, что невозможно. Аналогично, предполагал, что С„, 1 есть замкнутая цепь, не являющаяся циклом, получим (с учетом следствия 5.1), что такял цепь представима в виде суммы по крайней мере двух циклов, не имеющих общих ребер.
Тогда один из этвх циклов содержит только древесные ребра, что невозможно. Итак, сумма Се, 1 есть цикл, содержащвй только одно обратное ребро. В силу взаимно однозначного соответствия между множеством обратных ребер и множеством фундаментальных циклов цикл С„, 1 совпадает с фундаментальным циС 1=як, откуда (поскольку каждый элемент пространства циклов про- тивоположен сам себе) Таким образом, произвольный цикл С представляется в виде некоторой линейной комбинации фундаментальных циклов.
1ь Из доказанной теоремы следует, что число фундаментальных циклов, находимое алгоритмом поиска в глубину, равно 364 5. ТЕОРИЯ ГРАФОВ размерности линейного пространства циклов и не зависит от выбора начальной вершины, поскольку все базисы конечномерного линейного пространства состоят из одного и того же числа векторов [1Ч). Это число называют циклическим рангом неориентированного графа. Разность числа всех ребер графа и его циклического ранга называется ноцнклпнесннм рангом неориентированного графа.
Таким образом, циклический ранг неориентированного графа — это число обратных ребер при поиске в глубину из любой вершины, а коциклический ранг — число древесных ребер при поиске в глубину из той же вершины. Выведем формулу, связывающую циклический ранг и, число ребер тп, число вершин тт и число номнонентв свлэносшп я произвольного неориентированного графа С.
Обозначим через р коциклический ранг графа С. Тогда, поскольку в неорвенптнрованнозт дереве число ребер на единицу меньше числа вершин, получим и = тв- р = тп — ((тт1 — 1) +... + (тЫ, — 1)) = тп — тт+ й, где яч — число вершин в 1-й компоненте связности графа С. Итак, и = тп — тт+Й. Эта формула выражает циклический ранг неориентированного графа через характеристики графа, не завиапцие от способа поиска в глубину, и тем самым еще раз подтверждает инвариантность циклического ранга относительно выбора начальной вершины для поиска. Выбирая различные начальные вершины в алгоритме поиска в глубину, мы получаем различные базисы пространства циклов. Циклический ранг неориентированного графа показывает „степень цикличности" этого графа: чем больше циклический ранг, тем больше в графе циклов. Лес, в частности дерево, имеет нулевой циклический ранг (нуль — мерное пространство циклов).
365 5.9. Элемевты викломатвки Пример 5.1б. Рассмотрим неориентированные графы, изображенные на рис. 5.41. Предположим, что в списках смежности вершины упорядочены по возрастанию номеров. На рис. 5.41 показаны результаты поиска в глубину из двух разных вершин: о1 в графе 01 и е4 в графе Сг. Древесные ребра в графах выделены. По результатам поиска циклический ранг равен 4, а коциклический ранг — 5. В графе С1 фундаментальными являются циклы' С1. Еенпзнеенве, С2.
'Пз низ но4 низ~ СЗ. 'Ю4~ ~езн~пгн94~ С4: ЕЗнп1нпгнОЗ Циклы пронумерованы в порядке обнаружения. Для графа Сг фундаментальными будут циклы Р1. 'ЕЗ н Ег н Е1 н ЕЗ а'2: ЕЗ' «Е4' 'Ег' «Е1' 'ЕЗ) ОЗ' Ез н Е4 н ог н Е1 н ЕЗ н Ез~ Р4. 'Ебнп4 ног нп1 низ ноз нпе Разложение одного и того же цикла С Ег низ низ н'ее н $4 н'ог по двум указанным базисам будет следующим (рис. 5.45): С=С145СгЮСз, С=Ю1ЮВ4 45 Можно доказать, что изомор4мые неориентированные графы имеют изоморфкые линейные пространства циклов, однако "Записывав циклы (которые, по опредеаепшо, есть последовательвости вориши), мы.ради ваглвдкости пишем меиду вершинами зиачок ~-~ иеш» средствевпой достимимости. 366 б.
ТЕОРИЯ ГРАФОВ з«з ззз Рис. 5.46 обратное в общем случае неверно. Более того, в изоморфных графах должны совпадать „тонкие" структуры циклов: любое утверждение о циклах, истинное в одном графе, останется истинным в изоморфном ему графе. Таким образом, анализ циклов может быть использован для доказательства невзоморфности графов. Пример 5.1Т. Рассмотрим графы, представленные на рис. 5.46. Заметим, что у этих графов одинаковое количество вершин и ребер, а также одинаковые степени всех вершин. Поэтому гипотеза об их изоморфности представляется правдоподобной. Однако для доказательства изоморфизма графов необходимо явно указать биекцию множества вершин одного графа на множество вершин второго, при которой сохраняется отношение смежности. Поиск такой биекции весьма трудоемок, так как может потребовать полного перебора всех возможных вариантов.
Для доказательства неизоморфности достаточно показать принципиальную невозможность установления требуемой биекции. Используем для этого анализ циклов. Проведем поиск в глубину в каждом из графов. Если количество обратных ребер окажется различным, неизоморфность 367 5.9. Элеыеиты циилоыатики ев савв Св с! ев ев е]в Рис. 5.40 графов будет доказана. Для определенности в каждом из графов начнем поиск с вершины 01 и будем считать, что списки смежности каждой вершины упорядочены по возрастанию номеров вершин. На рис. 5.46 в графах выделены древесные ребра, полученные при поиске в глубину.
В каждом из графов оказалось по шесть обратных ребер, и, следовательно, вывод о неизоморфности сделать нельзя. Различие можно увидеть в „тонких" стуктурах циклов. Заметим, что в графе С] имеются четыре цикла длины 3: 01' '02н'04' '01~ Е1' ~03' '04' в91 07ноансвн07~ 08но9но]ено8. В графе С2 таких циклов также четыре: 0]н02 04не], 07 н08 н09 н 07 '02' 03' 011 08 н09 но]0 н08. Однако количество циклов длины 4 в графах различно.
В графе С] таких циклов шесть: 0] н02 н 04 н$3 не]в 02 не4 н03 н03 нЪ 09 н 07 н 08 н 010 н 09, 01' '02 ' ~05 " '03 ' ~01~ 09 н 07 н 08 н 010 н 09 ~ 07 08 010 ~00 07, 368 5. ТЕОРИЯ ГРАФОВ а в графе Сг — всего два: е1незнезне4не~> сзне10неэн'утнез. Следовательно, графы неизоморфны. Итак, исследование структуры циклов неориентированного графа как инварианта, сохраняющегося при изоморфизмах, позволяет в некоторых случаях быстро находить ответ на вопрос об изоморфности двух заданных графов. Заметим, что в общем случае все циклы графа можно получить, рассматривал различные линейные комбинации над Ез фундаментальных циклов. При этом следует учесть, что результатом сложения может быть множество ребер, образующих несколько непересекающихся циклов.
Вопросы и задачи 5.1. Сколько существует неориентированных графов с и вершинами? 5.2. Доказать, что сумма степеней всех вершин неориентированного графа равна удвоенному числу ребер (это утверждение известно под названием „леммы о рукопожатиях"). 5.3. Доказать, что если число ребер неориентированного графа с п вершинами при п > 2 больше С~ з, то он связный. 5.4. Доказать, что не существует неориентированного графа, степени всех вершин которого попарно различны. 5.5.
Найти все попарно неизоморфные неориентированные графы с четырьмя вершинами и тремя ребрами. 5.6. Установить, какие из изображенных на рис. 5.47 графов изоморфны, а какие — нет. 5.7. Привести пример неориентированного графа с четырьмя вершинами, изоморфного своему дополнению (самодополнительного). Доказать, что число вершин любого самодополнительного неориентированного графа равно 4й или 4Й+ 1. 369 Воиросы и задачи Рис. 5.4Т 5.8. Найти группы автоморфизмов графов, изображенных на рис.
5.48. Рис. 6.48 б.9. Пусть симметрическая матрица А порядка и, в ке ждой строке которой находится одинаковое нечетное число Ф ненулевых элементов, является матрицей смежности неориентированного графа. Показать, что число вершин графа и четное. (Учесть, что аи = О.) 5.10. Доказать, что отношение взаимной достижимости в ориентированном графе есть эквивалентность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
