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

3 Из первой части приведенного доказательства вытекает Следствие 4.10. При фиксированных и и у~ш среди графов С порядка и с й(6)= й существует только один граф, а имен,но, 6 =0,, 0 К,»ь с максимальным числом ребер. Графы с минимальным числом ребер (при фиксированных и и й) изучаются в следующей главе. в 5. Степени вершин графа Степенью (или валентноетью) вершины графа 6 называется число инцидентных ей ребер, т. е. число верн|пи в ее окружении. Будем обозначать степень вершины о через дедов (или дев и). Тем самым деу и = ~Х(о) ~. Максимальная и минимальная степени вершин графа Гг'- обозначаются символами Л(6) и б(6) соответственно: Л(6) = шах дени, б(6) = ш1пдеуо. »и то е ко Список степеней вершин графа называется его степенной последовательностью.

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

Каж— дое ребро вносит в эту сумму 2, поэтому верно Утверждеяие 5.1 (влемма о рукопожат ня х»). Сумма степеней всех вершин графа — четное 26 число, равное удвоенному числу ребер: с(ело = 2) ГС ~. вето Возможная интерпретация этой леммы такова: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала). Следствие 5.2. В любом графе число вершин нечетной степени четно. Поннтие степени вершины и лемма о рукопожатиях сохраняются для мульти- и псевдографов. Прн этом каждая петля вносит в степень соответствующей вершины двойку.

э б. Матрицы, ассоциированные с графом В этом параграфе вводятся три матрицы, связанные с произвольным графом, и еще одна матрица, связанная с двудольным графом. На всем протяжении этой книги элемент матрицы М, занимающий позицию (с, /), обозначается символом Мв. Матрица, каждый элемесст которой равен О исси 1, называется бинарной. Пусть С вЂ” помеченный граф порядка и, УС =-11, 2, ..., п). Определим бинарную и Х и-матрицу А =А(6), положив 1, если вершины с и с' смежны, Ам = О в противном случае. м Л(С) называется матрицей смелсссости графа С.

Это симметрическая матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины. Очевидно, что соответствие 6 А(6) определяет биекцию множества помеченных графов порядка и на множество бинарных симметрических и Х п-матриц с пулевой диагональю. Аналогично определяются матрицы смежности А мульти- и псевдографов; Ав равно числу ребер, соединяющих вершины с и с (при этом петля означает два ребра). Так же определяется матрица смежности А(6) ориентированного графа С: ) 1, если (1, 1) ~ А6, (А(6))ц = (О в противном случае.

Здесь А6 — множество дуг орграфа 6. Очевидно, что любая квадратная бинарная матрица является матрнцей смежности некоторого ориентированного графа. На рис, 6.1 изображен ориентированный граф с матрицей смежности 0111 1011 0010 0000 4 Рис. ОА Абстрактный граф приводит к различным матрицам смежности в зависимости от нумерации вершин, Посмотрим, как связаны между собой зти матрицы. Пусть 6 и Н вЂ” помеченные графы порядка и и 6 — = Н. Это означает, что 6 и Н различаются только нумерацией вершин, т.

е. существует подстановка в на множестве вершин, сохраннющая смежпосттк вершины и и о тогда и только тогда смежны в 6, когда их образы в(и) и г(о) смежны а Н. 11оложив А(6)=А, В(6)=В, получаем Вне.о, =Ав, 1=1, и, )=1, н. (1). Тем самым доказано У т в е р ж д е н и е 6,1. Графы нзоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов. Это утверждение верно также для мультиграфов„ псевдографов и ориентированных графов. Из предыдущего утверждеяня вытекает, в частности, что ранги матриц смежности изоморфных графов равны. Последнее позволяет ввести для абстрактного графа следующее определение ранга: рангом графа называется ранг его матрицы смежности.

Как и в случае матриц, ранг графа 6 будем обозначать через гапк 6. Пусть в — произвольная подстановка, действующая па множестве (1, 2, ..., и). Определим бинарную п Х п- 28 матрицу Я, положив (1, если г(1) = !, Яо = ( (О в противном случае. Очевидно, что в каждой строке и в каждом столбце матрицы Я содерясится ровно по одной единице и ое1Я = =~1.

С помощью прямых вычислений проверяется, что (ЕАЕ ')и = А для любой а Х и-матрицы Л. Равенства (1) теперь можно переписать в виде одного матричного равенства В = БАБ '. Из последнего равенства следует, что матрицы смежности изоморфпых графов подобны. Поэтому равны характеристические полиномы этих матриц. Следовательно, октн оп е еление хакорр о р д рактеристаческого иолииома графа как характе- ° рнстического полинома его матрицы смежности. Спектр этой матрицы, т. е. Рис. 6.2 совокупность корней характеристического полинома с учетом нх кратностей, называется спектром графа. Как известно из линейной алгебры, вещественная симметрическая матрица (а матрицы смежности графов являются таковыми) определяется своим спектром с точностью до подобия.

Тем не менее из совпадения характеристических полиномов графов отнюдь не следует изоморфизм этих графов. Неизоморфные графы с равными характеристическими полиномами называются коспектральнымн. Например, два графа, изображенные на рис. 6.2, коспектральны, их характеристический полинам равен хз(хе — 4).

Глубокие свойства и применения спектра графа рассмотрены в книге [31!. С двудольным графом удобно связать еще одну матрицу. Разбиение множества вершин двудольного графа па доли определяется этим графом неоднозначно. Часто такие графы рассматривают вместе с фиксированными разбиениями на доли. Если С вЂ” двудольный граф с долями Х и У и множеством ребер Е, то пшпут С= =(Х, У, Е). Итак, пусть С =(Х, У, Е), !Х! = т, !У! =п, Занумеруем вершины доли Х числами 1, 2, ..., т, а до- ли У вЂ” символами уп ум ..., у„, Определим бинарную т Хи-матрицу ЛХ= ЛХ(Х, 'г", Е), положив 1, если вершины с и у; смежны, ЛХО = О в противном случае. с Матрицу ЛХ назовем приведенной матрицей смежности двудольного графа.

Возвратимся к произвольным графам. Вторая из матриц, вводимых в общей ситуации,— матрица Кирхгофа. Пусть С вЂ” помеченньпй граф порячка и, ИС = (1, 2, ... ..., и!. Определим и Хи-матрицу В =В(С), полонсив — 1, если вершины с и у смежны, Вп= О, если учьу и вершины с и у не смежны, Йеи с, если ! = у. Матрица В(С) называется матрицей Хрирхгофа графа су, Сумма элементов в каждой стротсе и в каждом столбце этой матрицы равна нулю. Утверждение 6.1 останется верным, если вместо матриц смежности рассматривать матрицы Кирхгофа.

Сохраняется и прежнее доказательство. Во второй главе этой книги используется следующее Утверждение 6.2. Пусть  — произвольная числовая и Х п-матрица, в каждой строке которой и в каж.дом столбце сумма элементов равна нулю: ь п ~, Вц = О, с' = 1,п; ~, Вц = О, у = 1, п. с=с 'Тогда алгебраические дополнения всех элементов матрицы В равны между собой. В частности, этим свойством обладает матрица Кирхгофа произвольного зрафа, Г Очевидно, что гап!с В ( и. Вслп гап!с В ( п — 1, то алгебраические дополнения всех элементов этой матрицы равны О.

Пусть гасйсВ = и — 1 и С вЂ” присоединенная матрица для матрицы В, т. е, элемент Со равен алгебраическому дополнению А„. элемента Вя в матрице В, й = 1, и, у = 1, и. Известно, что ВС =(с(е$В)Е, где Е— единичная матрица. В наших условиях бес В = О, ВС = = Π— нулевая матрица. Следовательно, для столбца матрицы С с номером у, у = 1, и, верны равеяства ВоСп+ ВпСг +... +В,„С„с = О, с = 1, и, ВеА я + ВаА г +... + ВыА, = О, 1 = 1, Вти равенства можно рассматривать как систему линейных однородных уравнений с матрицей В относительно.

неизвестных Ая, Авь ..., Ам. Так как гап(сВ=п — 1, то все решения системы пропорциональны. Но вектор (1, ..., 1) удовлетворяет системе, поэтому Ан =Аз=...=А, 1=1, и. Учитывая, что СВ = О, аналогично получаем Аи=Аи= =А „(=1, п. Следовательно, Ае=Ля, ,Е,й,(=1, .а Наконец, определим матрицу ипцидентности графа. Пусть С вЂ” (и, т)-граф, ЕтС = (1, 2, ..., и), ВС = (ен ег, ..., е ). Определим бинарную п Х т-матрицу 1=1(С) условиями: -( 1, если верптина Ег и ребро е, инцидептны, 1ы = О в противном случае.

Матрица 1 называется матрицей инцидептности графа С В каждом ее столбце ровно две единицы, равных столбцов нет. Нак и выше, соответствие С вЂ” 1(С) является биекцией множества помеченных (и, пг)-графов с занумерованными ребрами на мноткество и Х т-матриц, удовлетворяющих описанным условиям. Для ориентированных графов определение матрицы ипцидентиости 1 видоизменяется: 1, если вергпина й является началом дуги аы 1ы = — 1, если вершина Ег является концом дуги а,, О, если вершина Ег и дуга а~ не инцидентны.. Аналогично утверждению 6.1 получается У т в е р ж д е н и е 6.3. Графы (орграфы) изоморфньг тогда и только тогди, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.

Пусть С вЂ” граф. Превратим каждое его ребро в дугу,. придав ему одну из двух возможных ориентаций. Полу- ченный ориентированный граф называется ориентацией графа С. Непосредственно проверяется У т в е р ж д е н и е ОА. Если  — матрица Еирхгофа графа С, а 1 — матрица инциде~тности какой-либо его ориентации Н (нумеров,ия вершин в Н та хсе, что и в С), то В =11 (здесь Т вЂ” операция транспонирования матрицы) . й 7. Регулярные графы Граф называется регулярным (или однородным), если степени всех его вершин равны; степенью регулярного графа называется степень его вершин.

Степень регулярного графа С обозначается через дед С. Все полные графы регулярны. Графы платоновых тел также регулярны. Регулярным графом степени п является и-мерный куб (~ . Из леммы о рукопожатиях вытекает, что не существует регулярного графа, порядок и степень которого нечетны. Утверждение 7.1. 11усть натуральные числа и и Ы, среди которых есть четное, удовлетворяют неравенствам 0 < д < и — 1.

Тогда существует регулярный граф .порядка и и степени Ы. С' Для и =0 утверждение очевидно. Кроме того, если С вЂ” регулярный граф порядка п степени Ы, то дополнительный граф С также регулярен и дед С = и — 1 — д. Поэтому достаточно рассмотреть случай, когда 0<д< < (и — 1) /2. Пусть Մ— аддитивная группа классов целых чисел по модулю и, А < Х„, 0 ФА и для х ~ А класс — х также принадлежит множеству А. Определим граф С порядка и с множеством вершин Х„следующим условием: вершины х и у смежны, если х — у ~ А.