Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 37
Текст из файла (страница 37)
атой цепью является остов графа Н„. Расстояние И(х, у) между двумя вершинами х, у б Н„равно >, > = 1, 2, ..., и. Две вершины х и у п-куба, уда- т,<с> Рис. З.тб тбт <к » т,<к„,> %пз Ри . з.тт ленные друг от друга на расстояние, равное диаметру, соединены между собой п! цепями. Теорема 3.22. Если эафиксировать люБую вершину и-куба х б Н„, то множество всех остальных вершин раэбиваетсл на п подмножеств 1'; б Н„таких, что каждая вершина >-го подмножестова о; к У; имеет расстояние до фиксированной вершины, равное д(х, и;) = >, а число таких вершин в >'-м подмножестве равно (",) длл всех С Поставим в соответствие каждой вершине и-куба двоичный вектор длины п.
Так как п-куб является регулярным графом, каждая вершина которого имеет степень, равную и, то, не теряя общности, в качестве фиксируемой вершины возьмем вершину 00...0. Гл.З. Теория графов и могрофов 13.6. Вложение графов 201 200 1 1 От От 0000 о 4 Рис, 3.29 0=3 10000 От 000000 г б Рис. 3.23 Разбив множество вершин и-куба на подмножества вершин, которым соответствуют векторы с равным числом единиц, заметим, что каждая вершина 1-го подмножества, которой соответствует вектор с 1 единицами, удалена от рассматриваемой вершины на расстояние, равное 1. количество таких вершин равно (",.). Теорема 3.23.
В п-кубе количестпво простых цепей длины Й, 6< и, между вершинами ю, юд, расстояние между котпорыми д(ю, юд) = Ь и которые не имеюпт других общих вершин, кроме ю, юд, равно й. Все 6! цепей длины 6 между вершинами ю„и юд, а(ю,„, юд) = /с, образуют Й-куб. В этом кубе минимальная мощность множества отделяющих вершин равна й — количеству вершин, смежных с ю и юд. Отсюда согласно теореме 3.9 количество простых вершин непересекающихся цепей между вершинами ю и юд равно й.
Полученный результат является важным при изучении запрешенных (критических) графов. Заметим, что число наикратчайших простых (геодезических) цепей между двумя вершинами, тт и Д, гиперкуба равно расстоянию между этими вершинами. Число же непересекающихся простых цепей' между вершинами п-куба, для которых расстояние по Хеммингу между ними меньше их длины, находится в зависимости от размерности п-куба. На рис, 3.28, а приведены три наикратчайшие цепи, соединяюшие вершины 000 и 111 в трехмерном кубе. На рис. 3.28, б-г иллюстрируется рост количества цепей длины 3 в кубах размерности 4, 5, б соответственно. Теорема 3.24.
Граф С=(У, Ц, включающий в себя 6 твершинно не пересекающихся простых цепей длины й между вершинами ст, )3 б Ъ; Иа(ст, 13) = 6, вложим в и-куб Н„, причем расстояние по леммингу между вершинами тт и В остается неизменным (т. е. ан(тт, 13) = Йс(тт, 13) = к), птогда и только тогда, когда две любые смежные вершины графа ст а, 6 ч T входят в цикл (а, Ь~ к ((а, Ь), (Ь, с), (с, йг, (й, аД длины 4 (рис. 3.29) птакой, что если Ин(тт, а) = тах йн(тт, 1) = 1, 1 = а, Ь, с, 14, то дн(тт, 6) = дн(ет, И) = 1 — 1, йн(ет, с) = à — 2. Теорема 3.23. В критпическом графе Я = (г', У) найдутпся две вершины ттт В, расстояние между котпорыми равно диа'метру д(тт,,8) = тт(Я), а число Ь простых путей на единицу больше: 6 = И®)+1.
Сформулируем несколько теорем, цозволяюших порождать за.Прешенные графы вложения в п-куб. Теорема 3.26. Если тл — критпический граф, то графТ2(С) тпакже критический тпогда и тполько тогда, когда степень вер'йтины а больше степени вершины Ь, т. е. в(а) ) в(Ь) (рис. 3.30), й преобразование не приводитп к образованию критпического подграфа (т. е. С не содержит четыре вершинно непересекающиеся простые цепи длины 3 между вершинами а, 6, а подграф ~И графа Тз(т.
) не представляетп собой две вершинно непересекающиеся цепи длины 3). Гл.з. Теория в вфов и мографов $3.0. Вложение графов 203 202 Ь т<в С тфс' Рис. 3.30 т'<в Рис. 3.31 т <с> Рнс. 3.32 Теорема 3.2Т. Замена любого ребра (а, Ь) йС критического графа С на к вершинно непересекающихся простых цепей длины 3 тогда и только тогда приводит к образованию критического графа Тз(С), когда 6 удовлетворяет одному из еле дующих условий: 1) 6 = 1, если удаляемое ребро является оБщим ребром двух циклов длины 4; 2) 6 = 2, если з(а) = 3, з(6) = 2 и вершины а, 6 принадлежат циклу длины 4; 3) 6 = т+ 2 — з(а), если з(а) > з(6) и т = д(С'), где Б(С')— диаметр графа С', полученного из графа С заменой удаленного ребра цепью длины 3> 4) 6 = 4, если удаляемое реБро инцидентно вершинам степени 2: з(а) = з(Ь) = 2.
Теорема 3.28. Граф Тв(С) (Т~(С)) (рис. 3.31) критический тогда и только тогда, когда является критическим граф С. Теорема 3.29. Граф Тз(С) критический тогда и только тогда, когда граф С критический (рнс. 3.32). Теорема 3.30. Если С вЂ” кршпический граф то графТв(С) критический тогда и только тогда, когда подграф Н содержит п1очку сочленения, и число доБавляемых цепей определяется из условия 6 = д(С') + 1 — з(а), где а, 6 б Н при з(а) > з(6), и граф С' получается из графа С заменой цепи длины 2 между вершинами а, 6 на цепь длины 4 (рис.
3.33, а). Пример преобразования, задаваемого данной теоремой, для подграфа Н приведен на рис. 3.33, б, где з(а) = з(6) = 2, диаметр есть Б(С') = 4 и 6 = 4+ 1 — 2 = 3. Множество запрешенных графов вложения в и-куб является счетным. На рис. 3.34 приведены критические графы с мошностью носителя от 8 до 17, часто встречаюшиеся на практике. ' Среди них имеются как графы, полученные с помошью приведенных преобразований Т;, 1= 1, 2, ..., б, так и графы, не имеюшие предшественников. При порождении запрещенных фигур необходимо проверить полученные графы на изоморфизм. Рассмотрим алгоритм установ- пения изоморфизма между графами Св> Сь, основанный на частот- ном Разложении моделей Фв(Св), Фь(Сь), постРоенных по этим графам.
205 33.6. Вловсеиие графов Гл.3. Теорил графоо и мографое 204 1. С помощью алгоритма, приведенного выше, выделяем полные полграфы в графах С„Сь. Выделенные подграфы образуют слова в соответствующих моделях Фе(бе) Фь(Сь) 2. Находим частотные разложения моделей Ф,(С,), Фь(СЬ), Определяем равенство коэффициентов в разложениях. Если ча статные разложения равны, то графы С и Сь изоморфны. л Рис. 3.33 Из равенства разложений тривиально определяем изоморфизм. Если частотные разложения не равны, то графы С, и Сь не изо- морфны. Проиллюстрируем алгоритм иа примере установления нгоморфигма между графами Сь и ььь (рис.
3.33). Пункт 1 алгоритма выполняется тривиально, так как графы двулольные (пол- ными подграфами являются ребра). Отсюда следует, что модели й„и ть соот- ветственно совпадают с графами С, и Огл ьуь = (Уь, от), Уь = (о~ )Уу у 61 от = ((о, я, (о, 6), (а, (), ()у, г), (ъ и), (Ъ О, (р, ), (,6, (, ) ( ° ч) (ч с))' фь=(Уь, Ят), Уь = (а~ Ь~ ° иь), Ят м ((а, Ь), (а, с), (а, д), (а, е), (Ь Л~ (, р), (),д),(е,ь),(у, ) (р, ) (Ь '")). и Рис. 3.34 207 5 3.6. Влолсгяпе графов 206 Гл.
3. Теаров графов и мографог Оь Рис: 3.35 б( ) э- е»С)У е Рнс. 3.36 Частотные разложения моделей Ф и Фь имеют следующий югд: г(т )тЗа о2~3 о22 а2р о4с о25 оти~о2я а35 о оар оабоабо пса ур о ту орг аебо сиакяо ар, Р(фь) = 4аэ о 2Ьэ о 2сэ о Заэ о 2еэ озуэ оЗдэ озьэ а Зтэ оаЬоос а о ля оае а Ь| о сд ояд оеь о утодт а Ьт.
Частотные разложения равны: р(к») = г (ть). Графы С» и Сь иэоморфны. Для опрелеления ивоморфиэма устанавливаем взаямно однозначное соответствие между буквами с одинаковыми спектрами частот: с ьь а, р ьь Ь(е), Д ьь с(я), и ьь е(Ь), б ьь а(с), т ь+ У(Ь), а с.+ д, ч ьь Ь(Ь), б ьь т. При определении изоморфизма ориентированных графов в предложенный алгоритм добавляют третий пункт. 3. Если графы сх, и Сь изоморфны без учета ориентации, рассматривая соответственные пары вершин, определяем сохранение изоморфизма графов с учетом ориентации.
Другой алгоритм определения изоморфизма графов заключается в последовательном разбиении классов вершин графа, каждый из которых состоит из вершин, имеюших равные степени, на основе подсчета количества ребер, связываюших рассматриваемую вершину с вершинами этих классов. Рассмотрим двв графа, С, и Сь (уме. 3.36, а, б).
Носитель графа С, ко значенньа степеней вершин разбивается на четыре класса: Кг (1, 2, 6), Кэ = (4), Кэ = (3), К» ю (5). Носитель графа Сь также разбивается на четыре влзсса: К,' = (Ь, с, у), Кэ = (е), Кэ -- (а), К( = (И). Количество классов н их мошностн совпадают; следовательно, графы С, и Сь могут быть изоморфны, кри этом нзоыорфнзм я отображает, очевидно, вершины 3, 4, 5 в а, е, а соответственно: а ю я(3), е = я(4), Л = Ч(5) Определим коли гество связей вершик 1, 2, 6 в графе С, и вершин Ь, с, у в графе Сь с вершвнаьяг выделенных классов.
Для этого построим двумерную тэблипу (табл. 3.2), каждой строке которой взаимно одноаначио соответствует вьгделенный класс, столбпу — вершина, а на пересечении (ь, У) укавывзегся . количество связей,у-й вершины с вершинами Ьго класса. Таблипа 3.2 Анализируя таблнпу, взметаем, что класс Кь разбивается из пвэ класса: К1 = (2, б) и Кэ т (1); класс К( такие раэбнваетсяна два класса: К,' = (Ь, у) и,Кь = (с). Если этн графы изоморфны, то с = а(1). Для устаиовлешш сает. мтствуюших вершин графов С„Сь строим табвику (табл.
З.З) для полученного равбиения вершин. Тзблипз З.З Одинаковые столбпы укавывают на то, что вершина 2 (вершина 6) может Ф быть содоставлена юш вершние Ь, так и У. Получена лва соответствия, о и я, так кав окреспюстя вершин 2 и б совкалают. Выбрав алка иэ них и прове- рив его иа иэоморфизм, делаем вывод, чта рассматрнвымые графы изоморфны (рис. З.зб,е), 209 208 Гл.3. Теория графов и мографог ь 3.7. Раскраска агршин и реБер графа 3 3.7. Раскраска вершин и ребер графа.
Характеризация реберности Раскраской вершин графа С = (У, У) а Ь цветов (или Ь-раскраской) называехся разбиение носихеля Ъ' графа С, при кохором каждое подмножество т ь р) ~ О У = $; У;. П Ъ;.ь = И, т'„ть = 1,2,..., Ь ь=1 не содержит ни одной цары смежных вершин. Каждому подмножеству сопоставляется цвет, в который окрашивают все элементы этого подмножества, Вершины, окрашенные в один цвет, будем называхь соцаетными. Хроматпическим числом Ь(С) графа С называется минимальное число и, для которого граф имеет и-раскраску. Граф, хроматическое число которого равно и, называется п-хроматически.м; если же Ь(0) < и, то граф С называется п-раскрашиваемым. Очевидно, что 1-хроматическим граф может быть тогда и только тогда, когда он является пустым графом.
Для 2-хромахических графов справедлива следуюшая теорема. Теорема 3.31 (Кениг). Граф является 2-хроматпическим тпогда и только тогда, когда он не содержитп циклов нечетпной длины. Отметим, что аналогичная теорема задает и условие двудольности. Поэтому все 2-хроматические (двуцветные) графы являются двудольными. Любое дерево, поскольку оно является двудольным графом, двуцветно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
