В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 6

Очевидно, что граф С регулярен и степень его равна ~А~. Остается доказать, что для любого числа Ы, удовлетворяющего указанным выше условиям, существует подходящее д-элементное множество А. При д = 2Й моягно взять А = (~1, ~2, ..., ~Ы, а при Ы = 21+ 1 оказывается четным и, и можно взять А =(х1, — '2, ..., ~)с, и!2) (см. рис. 7.1, где п = 8, д = 3) .

<3 Утверждение 72. Если С=(Х, У, Е) — непустой регулярный двудольный граф, то ~Х~ = ~У~, С' Так как доле Х принадлежит только один из концов каждого ребра графа С, то число пг его ребер равно т = 1У! бей 6. Следовательно, Поскольку е)еп 6 Ф О, то Пусть х, — координата вектора х с максимальным модулем, 7У;=7ч(7') — окружение вершины 7' в графе 6, Из равенства (1) для 7'-н1 координаты вектора Ах вытекает (Лх), = ~ хг = е1хг (2) еемз 1Х1 Йеп 6. Аналогично 1Х! деп 6 = !У! Йой 6. !Х1 = !у1. а Иногда, хотя и редко, граф определяется степенями своих вершин. Например, только О„является регулярным графом порядка и пулевой степени. Пегуляршрй граф первой степени имеет четный порядок 2т и является дизъюпктным объединением гп ребер. Этот граф обозначается символом пгКг.

Все связные компоненты регулярного графа второй степени являются простыми циклами. Однако уже кубические графы, т. е. регулярные графы степени 3, устроены сложно и пе опродоляются Рве. 73 степенямп своих вершин. Примером кубического графа является граф Петерсена (рпс. 1.О). Отметим любопытное свойство спектра регулярного графа. Теорема 7.3.

Пусть 6 — регулярный граф степени е(. Тогда: 1) число й является корнем характеристического полинома графа 6; 2) если 6 — связный граф, то кратность корня д равна 1; 3) д ~ !),1 для любого корня 7. характеристиееского полинома графа С. 1) Пусть И6 = (1, 2, ..., п), Л (6) = Л вЂ” матрица смежности графа С, и — столбец высоты и, все злемепты которого равны 1.

Поскольку в каждой строке матрицы А ровно д единиц, то Аи = е(и и, следовательно, и — собственный вектор, а а — собственное значение линейного оператора А. Но кахедое собствешюе значение является корнем характеристического полипома. Тем самым доказано, что е( — корень характеристического полипома графа 6. 2) Для произвольного собственного вектора х = (х,, хи..., х„) с собственным значением г( имеем Лх = в(х, х Ф О. (1) 3 В А. еиелечее и яр. 33 и, далее, Ы(х;(( ~~'., !х;(.

(3) $8. Метрические характеристики графа Пусть 6 — связный граф, а и и о — две его несов- падающие вершины. Длина кратчайшего (и, о)-маршру- та (он, естествешю, является простой цепью) называ- ется раеетояниел< между вершинами и и о и обознача- ется .через сс(и, о). Положим еще сс(сс, и) = О. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомалс лсетрики; 1) сУ(и, о)> О, 2) с((сс, о) = О тогда и только тогда, когда и = о, 3) ас(и, о) = сК(о, и), 4) Л(и, и)+ с((и, и)) й(и, ш) (неравенство тре- угольника).

Понятие расстояния между вершинами в связном гра- фе позволяет определить й-ю степень графа. Пусть С— связный граф, Й вЂ” натуральное число. Граф 6' имеет то же множество вершин, что и 6; несовпадающие вершины и и о смежны в графе 6' тогда и только тогда, когда для графа С верно неравенство сс(и, о)» к. Очевидно, что если к >!6~ — 1, то 6' — полный граф. Для фнкснрованноп верспппы и величина е(и) = шах сс(и, о) сеун Поскольку ~Дсс! = сс, то из соотношений (2) и (3) следует, что х; =хс для всех с из Л'ь Для связного графа 6 теперь получаем, что все коордппаты вектора х равны между собой, т.

е. размерность подпрострапства собственных векторов линейного оператора Л, относящихся к собствешюму значению д, равна 1. Следовательно, и кратность корпя сс характеристического полипома матрицы Л равна 1. 3) Пусть Х вЂ” произвольный корень характеристического полипома матрицы А, х — соответствующий собственный вектор. Тогда Ах = с.х, и в тех же обозначениях, что и выше, имеем (Лх),=,'," хс=Ххсч )Хнх,((,"., )хс(==д(х,(, сект сенс откуда ~Л!» с(. 'л Вор~пипа и называется периферийной, если е(о)= Ы(6). Простая цель длины с((6), расстояние между концами которой равно д(С), называется диаметральной цепью. Для иллюстрации обратимся к графу на рнс. 8.1. Здесь д(1, 2) = 1, д(1, 3) = 2; е(1) = 2; И(6) = 2.

Все вершины, кроме вершины з 2, являются периферийными, (1, 2, 8)— диаметральная цепь. Утверждение 8.1. Для всякого связного графа 6 верно неравенство с((6) - гап1с 6. С. Пусть Ы(С) = Ы и 5 1 Рвс. 8Л оп ог, °, оз.ь~ — одна из дпаметральпых цепей графа С. Рассмотрим матрицу смеяпгостн Л(6), причем выберем нумерацию вершил так, чтобы вершины (1) имели лонера 1, 2, ... ..., с(+ 1 соответственно. Очевидно, что называется энсцентриситетом вершины и.

Максимальный среди всех зксцептрпситетов вершин называется диаметром графа С и обозпачается через И(6). Теы самым Ы(6) = шахе(и). ,ьн~ о — клеточная матрица, в левом верхнем углу которой расположена матрица смшкпости А порожденного подграфа 6(оп ог, ..., игь~). Этот подграф является простой цепью, следовательно, 010...00 1 0 1 ... 0 0 0 1 0 ... 0 0 000...01 000...10 — симметрическая матрица порядка Ы+ 1, все злемепты которой, за исключением двух ближайшнх к диагонали полос единиц, равны нулю.

Милор порядка д матрицы Л, остающийся после устрапелия первого столбца и последней строки, равен 1. Следовательно, гап)с Л (6) ~ > гав)с А ~ д. <5 Минимальный из зксцоптриситетов вершил связного графа называется его радиусом и обозначается через Зь 35 г(6) г (6) = пйп е (и) = шил шах и (и, и). мего на ус ветс Очевидно, что радиус графа не больше его диаметра. Вершина и называется центральной, если е(в) = г(6). Множество всех центральных вершин графа называется его централи Граф мшкот иметь единственную центральную вершину или несколько центральных вершин.

Наконец, центр графа может совпадать с множеством всех воршин. Например, центр простой цепи Р„при четном число вершин и состоит ровно из двух вершин, а при нечетном — из однои; для цикла же С„все вершины являются центральными.

Задача нахождения центральных першил графа постоянно возникает в практической деятельности людей. Пусть, папрпмор, граф представляет сеть дорог, т. е. вершины ого соответствуют отдельным населенным пунктам, а ребра — дорогам мея«ду ними. Требуется оптимально разместить больницы, магазины, пункты обслу'кивапия. В подобных ситуациях критерий оптимальности часто заключается в оптимизации «паихудлпего» случая, т.

е. в минимизации расстояния от места обслуживания до наиболее удаленного пункта. Следовательно, местамп размсгцоппн должны быть центральные вершины графа. Реальные задачи (их называют лшнимаиеными задачалш разл«ещения, см. (27) ) отличаются от этой идеальной тем, что приходится еще учитывать другие обстоятельства — фактические расстояния между отдельными пунктами, стоимость, время проезда и прочее. Для того чтобы учесть это, используют понятие «взвешенный граф». Пусть 6 — граф, ш: К6- В» — веществепнозначпая функция, ставящая в соответствие каждому ребру е положительное (илп неотрицательное) число ш(е)— вее ребра е. Пару (6, ш) назовем взвешенным грифель Под длиной (илн весом) любого подграфа взвешеш«ого графа будем понимать сумму весов сто ребер. В остальном все определения сохраняются. й 9.

Критерий двудольпости графа Д. Кениг сформулировал простой критерий двудольпостн графа в терминах длин циклов. Теорема Коняга (1939 г.). Для дврдольноети гра$а необходил«о и доетато чио, чтобы он ие содержал цш;лов нечетной длины. 30 г Необходимость. Пусть С вЂ” двудолыьый граф, С вЂ” один из его циклов длины к. Пройдем всо ребра этого цикла в той последовательности, в какой опп на нем расположены, начиная с некоторой вершины о. Сделав й шагов, вернемся в о.

Так как концы каждого ребра лежат в разных долях, то й — четное число. Д о с т а т о ч и о с т ь. Не ограничивая общности, можно рассматривать только связные графы, ибо дизыопктное объединение двудольных графов также двудольпо. Пусть связный граф С порядка и ) 1 пе имеет циклов нечетной длины, о ы УС. Построим разбиение УС = Л 0 В следующим образом: произвольную вершину и графа С агнесам к классу А, если расстояние д(и, о)— четное число, и к классу В, если l зто расстояние нечетно.

Остается доказать, что порожденные пад.р.ь вьч, о|в) „„... „. стыни. Пусть, напротив, существуют две смежные вершины и и ш, входящие в один класс. Тогда ни одна из них не совпадает с о, поскольку о ш Л, а окружение вершины о входит в класс В. Пусть, далее, с'— кратчайшая (и, о) -цепь, И' — кратчайшая (ю, о) -центе о1 — последняя, считая от о, из общих вершин зтпх цепей, лежащая на цепи С (рис. О.1) .

Осозпачпм чорез Х„и У соответственно (о, о1)- п (оп и)-подцепп цепи С, а через Х„и ӄ— соотвотствепно (о, о~)- и (оь ю)-подцепп цепи И'. Очевидно, что длины цепей Х и Х совпадают и, слсдоватольяо, длины цепей У„и У одного характера четности. Но тогда объединение цепей У„и У и ребра ию является циклом нечетной длины. 0 Очевидно Следствие 9.1. Граф является двудольныя гогов и только тогда, когда он не имеет простых циклов нечетной длины. Доказательство теоремы Кеиига подсказывает простой способ распознавания двудольпости графа. Этот способ основан на простом приеме, называемом поиском в ширину. Поиск в шарику следующим образом приписывает верптинам рассматриваемого графа номера О, 1, 2, ...