В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 7
Текст из файла (страница 7)
Начиная с произвольной вершины, приписываем ей номер О. Каждой вершине пз окруяьеппя вершины О 37 приписываем номер 1. Теперь рассматриваем поочередно окруясения всех вершин с номером 1 и каждой пз входящих в эти окружения вершин, еще не занумерованных, приписываем номер 2. Рассматриваем окруясения всех вершин с номером 2 и т. д., пока возможно. Если исходный граф С свнзеп, то поиск в ширину зануморует все ого вершины. Далее, разобьем множество )т6 па две части — Л и В, отнеся к Л все вершины с четными номерами, а к  — все остальные вершины, и рассмотрим порожденные подграфы 6(Л) и 6(В). Если оба опи пусты (достаточно проверить, что все пары вершин с равными номерами пе смексны), то 6 =(Л, В, Е) — двудолькый граф.
В противном случае граф 6 пе является двудольпым. Простых способов распознавания 1с-дальности графа при й ) 2 нет. Очевидно, что с помощью поиска в спирину можно также решить следующие задачи: 1) разбить множество вершин графа на его области связности; 2) для несовпадающнх вершин и и о связного графа найти кратчайшую (и, о)-цепь; 3) в ориентированном графе найти множество всех вершин, достиясимых из заданной вершины о. $10. Реберный граф Пусть Я вЂ” непустое мноскество, а г' = (Яь Яг, ... ..., Я„) — его покрытие пепустыми несовпадающими подмножествами. Определим граф У. (Г) следующими условиями: стгг(р)=г', вершины яс и я, смежны, если счьу и Я, П Я, Ф ю. Произвольный граф 6 называется графом пересечений, если и только если существуют такое мпоясество Я и такое покрытие этого мпо'кества Г, что 6 = ш (г(Р).
У тв е р ж де ни е 10.1. Любой граф яеляется графом пересечений. ~> Пусть 6 — граф, ст6 = (1, 2, ..., и), Я вЂ” мпогкоство элементов графа 6. Для с = 1, и обозначим через Яс множество, составленное из вершины 1 и всех ннцндентпых ей ребер. Положив Р = (Яс, Ян ..., Я„), получим 6 =— = а(г). а Важный класс графов пересечений составлясот реберные графы. Для произвольного графа 6 реберный граф Ь(6) определяется следующими двумя условиями: 38 1) <тС(6)= ЕС, 2) верпшны е< и ег смежны в Х.(С) тогда и только тогда, когда ребра е, и ег смея<ны в С. Если для некоторого графа Н существует такой граф С, что Н вЂ” Х,(С), то Н также называется реберным графом.
На рис. 10.1 совмещены два графа — С и Х (6). Вершипы графа 6 — темные кружочки, вершины графа Рис. 10.1 Л(С) — светлые круп<ни. Ребра графа С вЂ” тонкие ляпин, ребра графа Х,(6) — жирные липин. У та ер ж де ни е 10.2. Если <(п с(г, ..., с(„— степенная последовательность (и, та)-графа С, то Е(6) является (гп, 1)-графог<, где 2 ~> Очевидно, что 1-я вершина графа С порол<дает ребер графа Х (6), поэтому и е е 1 1Хда 1214 1 удг и 0 < 2 2 лы г а=т Очевидно, что если графы С и ХХ изоморфны, то Х,(6) и Х(ХХ) также изоморфны.
В то же время справедливы соотношения Х (Кг) — = Х (К< з) = Кг. Х. Уитни доказал, что Кг и К<,г — единственная пара несовпадающих связных графов, имеющих один и тот п<е реберпый граф. Если порядок хотя бы одного из рассматриваемых графов меньше пяти, то это проверяется непосредственно, а для графов больших порядков вытекает из следующей теоремы. 39 Т с о р о м а 10.3 (Х.
Уитни, 1932 г.). Пусть С и Н— связные графы, )6) ) 4, )Н) ) 4 и Е(6)== Е(Н). Тогда 6 св П и, более того, для всякого изоморфизма >р: 1,(С)- 1(Н) существует единстве>и>ь>й изоморфизм >)ч 6 Н, иидуииру>ощий >р, т. е. такой, что тр(е) = >)>(и)>р(о) для л>обоза ребра е = ио графа 6. ~> Изоморфнзм >р реберпых графов Е(6) и Е(П) будем рассматринать как бнекцию ЕС вЂ” ЕП меп>ду ънп>- жестнами ребер графов 6 и П, при которой смелтпым ребрам соответствуют смежные, а несмежным — несмежные.
Л е и м а 10.4. Если ребра е> (> = 1, т) составляют звезду К>, в графе 6, то их образы >р(е,) составляют такую же звезду К>, в графе Н. ~> Доказательство леммы. Прит=2утнерждепие помпы верно по определению изоморфизма графов. Пусть с= 3 и ребра е>, е„., ез состанляют и графе С знезду К> з. Поскольку граф 6 снязоп и порядок его более четырех, то н нем есть четвертое ребро е, сможное с кан;— дым пз ребер е; плн точно с одним из них. Таким яге свойстном обладает >р(е) по отношешпо к >р(е,). Ребра >р(е,) составляют и графе Н либо гнезду К> з, либо треугольник. По ребро, смежное с какнм-либо ребром треугольника, смежно ровно с двумя нз ребер. Тем самым доказано, что ребра >р(е,) составляют звезду н графе Н.
Нужное утнержденпе доказано для г= 3. Очевидно, что для г) 3 опо просто получается по индукции. З Поскольку отображение >р '. 1(П)- 1(6) такяте янляетсн пзоморфнзмом реберпых графов, то из предыдущой леммы вытекает следующее утнер>кдепие: ребра е, (> = 1, >.) составляют максимальную (относнтельно нключонпя) заезду К> „и графе 6 тогда и только тогда, когда нх образы >р(е,) составляют максимальную звезду К>, н графе Н. Итак, нзоморфизм >р онредоляет бнекцшо между множестнами максимальных знезд графов 6 н П.
Оченндно, что н каждой из зтпх гнезд более одного ребра, н потому н ней есть лишь одна центральная вершина. Максимальную звезду графа 6 с центром х обозначим через Я,(х). Оченпдпо, что если ц>(о,(х))= Ят>(х'), то соотнетстнпо >)>: х х' является пньекцпей множества всех першин графа С, не являющихся копцоными, и аналогичное подмпожестно першин графа П. Из сообраягенпй симметрии следует, что >)> — бпекцпя.
Теперь распространим дейстнпе отображения >)> па ко>щеные норшппы графа 6. Пусть о — одна пз таких нер- йо шин. В графе 6 есть смея~ная с ней вершина х степени большей, чем 1. Положим хэ = е п выберем в звезде Я„(х') такое ребро е' = х'э', >то Ч>(е) = е'. Покажем, что дед о' = 1. (1) Пусть это не так. Тогда в звезде Я««(и') ест> ребро е, = = е'. Следовательно, в звезде ср '(Я>«(о')) есть робро е, = ср (е,), смежное с ребром е, но пе входящее в Я,(х).
Но тогда вершина о — конец этого ребра н Йоп э чь чь 1. Равенство (1) доказано. Полон|ив >р(э) = о', получим инъекцию множества концевых вершин графа 6 в мноясество концевых вершин графа Н. Из сообра>кений симметрии теперь следует, что >р — биекцня. Итак, построена биекция >ч РС вЂ” ГН. Докажем, что зта биекцня является графовым изоморфизмом. Оолраним обозначение Я,(х) п в том случае, когда >)ед х = 1. В этой ситуации Яа(х) содеря|пт одн» ребро, ипцидентное вершине х, и не является максимальной звездой.
Смен«ность вершин х и у в графе 6 означает, что звезды Я,(х) и Яэ(у) имеют общее ребро. Поэтому (ху «и Е6) с=>- (х'у' я ЕН) . Доказано, что >р: С вЂ” Н вЂ” изоморфизм графов. Из определения отображения >р видно, что оно индуцирует ~р, т. е. >р(е) = х'у' = >Р(х)>Р(у) для любого ребра е = ху ~н ЕС. Существование нужного изоморфизма «)> доказано. Остается доказать единственность. Пусть, напротив, есть два изоморфизма >р> Ф ф, удовлетворяющим услови>о теоремы.
Тогда >р> (а) ~ >рэ(а) для некоторой вершины а«н )«6. Рассмотрим произвольное ребро е = ах в графе С. Тогда >р> (а) >)» (х) = гр (е) = >р> (а) >)>э(х), и, следовательно, >)»(х) = «р>(а). Волн дед а ) 1 и ау— другое ребро С, то аналогично получаем >)>э(у)= >р>(а) = = >)>э(х), что противоречит ипъективностп >Ч. Если же дода = 1, то из >рз(х)= >)»(а) получаем де>г х = 1, что противоречит связности С. <1 Известно, что не всякий граф является реоерным, например, звезда К>з не есть реберпый граф. (Характерпвация реберныл графов имеется в книге (7).) Однако класс реберныл графов достаточно содержателен, Об этом свидетельствует, в частности, тот факт, что гипотеза ро- 41 берной реконструируемости произвольных графов эквивалентна гипотезе вершинной реконструируемости реберпых графов, Приведем без доказательства следующую теорему.
Теорема 10.5 (Р. Хеммипджер, 1969 г.). Связный граф 6 с более чем тремя ребрами реберно реконструируем тогда и только тогда, когда реберный граф Е(6) вершинно реконструируем. Отметим еще любопытную связь, существующую между матрицей инцидептпости графа 6 и матрицей смежности реберного графа Е(6).
Ут в е р ж де ни е 10.6. Если 1=1(6) — матрица инцидентности графа 6 и А =А(Е(6)) — матрица смежности графа Е(6), записштая при той же, что и 1, нумерации ребер, то 1'1 = А + 2Е, (2) где Š— единичная матрица порядка ')Е6~. Г Рассмотрим элемент произведения 1'1, занимающий позицию ()с, 1): Последняя сумма равна числу вершин графа 6, инцидептных обоим ребрам с номерами й и й При й =1 это число равно 2. Если й во 1, то это число по определению есть элемент Аи матрицы А.
Равенство (2) доказано. 0 С л е д с т в и е 10Л. Любой корень характеристического полинома всякого реберного графа не меньше, чем — 2. 1> Пусть 6 — реберный граф. Тогда для него верно равенство (2). С другой стороны, пусть Ах =).х для ненулевого вектора х. Тогда 1т1х =(т, + 2)х (в силу равенства (2) ). Теперь рассмотрим квадрат длины вектора 1х: (1х)г хт1т1х (т. + 2) хтх (т ( 2) ~х~г Следовательно, ), + 2 > О, 7, > — 2. З 5 11. Группа автоморфизмов графа Характеристикой симметрии графа является его группа автоморфизмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
