Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ПОНЯТИЕ СПЕКТРА ГРАФА

1.1 ПОНЯТИЕ СПЕКТРА ГРАФА

1.2 ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ

1.3 НЕКОТОРЫЕ ТЕОРЕМЫ ТЕОРИИ МАТРИЦ И ИХ ПРИМЕНЕНИЕ К ИССЛЕДОВАНИЮ СПЕКТРОВ ГРАФОВ

ГЛАВА 2. СВЯЗИ МЕЖДУ СПЕКТРАЛЬНЫМИ И СТРУКТУРНЫМИ СВОЙСТВАМИ ГРАФОВ

2.1 ОРГРАФЫ

2.2 ГРАФЫ

2.3 РЕГУЛЯРНЫЕ ГРАФЫ

ГЛАВА 3. ПРЕДФРАКТАЛЬНЫЙ ГРАФ С ЗАТРАВКОЙ РЕГУЛЯРНОЙ СТЕПЕНИ

3.1 ОПРЕДЕЛЕНИЕ ПРЕДФРАКТАЛЬНОГО И ФРАКТАЛЬНОГО ГРАФА

3.2 СПЕКТР ПРЕДФРАКТАЛЬНОГО ГРАФА С ЗАТРАВКОЙ РЕГУЛЯРНОЙ СТЕПЕНИ.

ВЫВОДЫ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

В последние десятилетия значительно возросла научная активность в области дискретной математики, переживающей период интенсивного развития и проникновения в самые разнообразные области знания. Наиболее ярко это проявилось в одном из ее разделов - теории графов, обширные возможности приложения которого обусловлены теоретико-множественными, комбинаторными и топологическими аспектами, составляющими основу понятия самого графа. Успех применения методов теории графов можно объяснить также тем, что она представляет собой удобный язык для формулировки задач, относящихся к весьма широкому кругу научных проблем, и является эффективным инструментом для их решения.

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

Приведены приложения спектральных методов в теории графов, комбинаторике, химии и физике, описаны химические и физические модели, в которых спектры графов имеют важное самостоятельное значение.

В последнее время теоретико-графовые (топологические) подходы приобрели для химии большое значение, что, по мнению специалистов, обусловлено несколькими причинами: во-первых, результаты, полученные при топологическом рассмотрении, не всегда могут быть извлечены из прямых численных расчетов; во-вторых, существует много молекулярных свойств, которые лучше всего поддаются объяснению с помощью представлений, основанных на понятии связности молекулярного гpaфa. Повышенный интерес, проявляемый к теории графов, вызван также тем, что теория молекулярных орбиталей Хюккеля продолжает совершенствоваться и успешно применяться в химии сопряженных молекул. Анализ теории Хюккеля на языке теории графов не только открывает новые возможности для наглядной интерпретации, но и позволяет глубже разобраться в структурном обосновании многочисленных закономерностей, установленных для -электронных систем.

ГЛАВА 1. ПОНЯТИЕ СПЕКТРА ГРАФА

1.1 ПОНЯТИЕ СПЕКТРА ГРАФА

Спектр графа - это множество всех собственных значений матрицы смежности с учетом кратных ребер.

Кратные ребра - несколько ребер, инцидентных одной и той же вершине.

Граф включает множество вершин и множество ребер, являющиеся подмножеством декартова квадрата множества вершин (т.е. каждое ребро соединяет ровно две вершины).

Орграф G =(V,E) есть пара множеств, V- множество вершин, Е- множество дуг.

Дуга - это упорядоченная пара вершин (V,W) , где вершину V называют началом, а W- концом дуги.

Графы с неориентированными или ориентированными кратными ребрами называются соответственно мультиграфами или мультиорграфами. В этих случаях допускается существование петель (петля - это ребро или дуга, обе вершины которой совпадают). Используемая терминология совпадает с терминологией Харари, с тем лишь отличием, что в настоящей работе мультиграфах (мультиорграфах) допускается наличие петель. Хотя термином «граф» принято обозначать то, что в некоторых работах по теории графов называется «конечным неориентированным графом без петель и кратных ребер» (или, короче, «обыкновенным графом»), мы ради удобства чтения будем иногда (когда это не вызовет недоразумений) использовать термин «граф» в более широком смысле, т. е. будем этим термином обозначать неориентированные графы, орграфы и даже мультиграфы и мультиорграфы.

Две вершины называются смежные, если они соединены ребром (дугой). Матрица смежности А мультиграфа (мультиорграфа) G с множеством вершин {х1, х2, *** , хn} - это квадратная матрица порядка n, в которой значение aij элемента, расположенного на месте (i, j) равно числу ребер (дуг), начинающихся в вершине хi, и оканчивающихся в вершине xj. Будем обозначать ее А=(аij)=(а); иногда элемент aij будет удобно обозначать через (A)ij. Например,

Размещено на http://www.allbest.ru/

X1 X2 X3 X4

рис1.1.

матрица смежности графа, изображенного на рис.1.1, имеет вид

Для мультиграфа значение аij равно удвоенному числу петель (неориентированных), присоединенных к вершине xi.

Иногда удобно отождествлять мультиграф G с мультиорграфом, матрица смежности которого такая же, как и у графа G. Объясним это подробнее: любое неориентированное ребро, соединяющее различные вершины, может рассматриваться как пара дуг, соединяющих те же самые вершины, но имеющих взаимно противоположные направления, и наоборот. Аналогично, любые две «ориентированные петли», присоединенные к одной и той же вершине, можно заменить одной неориентированной петлей и наоборот.

Мультиграфы (мультиорграфы) G = (X, U) и Н = (У, V) называются изоморфными, если существует (1, 1)-отображение у = ц (х) Х на Y такое, что для любой пары вершин х', x" Х в Н имеется столько же ребер (дуг), следующих из у' = ц (х') в у" = ц (х"), сколько их в G следует из х' в х". Такое (1,1)-отображение ц,сохраняющее смежность, называется изоморфизмом. Очевидно, G и Н изоморфны тогда и только тогда, когда их вершины можно обозначить (занумеровать) так, что соответствующие матрицы смежности будут равны. Ясно, что отношение изоморфизма является отношением эквивалентности, разбивающим множество всех мультиграфов (мультиорграфов) на классы эквивалентности, которые можно рассматривать как абстрактные мультиграфы (мультиорграфы). Таким образом, изоморфные мультиграфы (мультиорграфы) представляют один и тот же абстрактный мультиграф (мультиорграф). Если G и Н изоморфны, будем писать GН, если же G и Н рассматриваются как абстрактные мультиграфы (мультиорграфы), то G = Н,

Определитель квадратной матрицы А обозначается через или det А.

Характеристический многочлен матрицы смежности А графа G называется характеристическим многочленом графа G и обозначается через PG (л). Собственные значения матрицы А (т. е. нули многочлена ) и спектр матрицы А (состоящий из собственных значений) называются соответственно собственными значениями и спектром графа G. Если л1,…, лn - собственные значения графа G, то весь спектр обозначается через Sp (G) = [л1,…, лn]. Ясно, что изоморфные мультиграфы (мультиорграфы) имеют один и тот же спектр.

Собственные значения матрицы А можно определить также как такие числа л, удовлетворяющие уравнению Ах = лх, для которых имеется ненулевой вектор х. Каждый такой вектор х называется собственным вектором матрицы А (или графа G), соответствующим собственному значению л.

Для графа G, изображенного на рис. 1.1, имеем

;

Спектр полного графа Кn на n?1 вершинах состоит из числа n - 1 и n-1 чисел, равных -1.

Спектры графов вошли в математическую литературу начиная с фундаментальных работ Л. М. Лихтенбаума и Л. Коллаца и У. Синоговица. Но химики-теоретики начали интересоваться спектрами графов еще раньше, после появления работы Э.Хюккеля в 1931г.

Перечислим причины проявляемого интереса к спектрам графов.

1. В квантовой химии скелеты некоторых ненасыщенных углеводородов представляются в виде графов. Энергетические уровни электронов в такой молекуле в действительности являются собственными значениями соответствующего графа. Устойчивость молекулы, а также другие важные химические свойства тесно связаны со спектром графа и соответствующими собственными векторами.

2. В теории графов и комбинаторике имеется много теорем, при доказательстве которых применяются спектры графов, хотя они и не встречаются в формулировке теорем. Следовательно, использование спектров графов играет роль весьма важного метода, который называется спектральным.

3. И наконец, еще один аспект - вычислительный: спектр - конечная последовательность числовых инвариантов. Исходя из того, что интересующая нас информация (или ее значительная часть) содержится в спектре, мы можем вместо графа использовать его спектр, так как конечную последовательность чисел легко обрабатывать на вычислительной машине. Последнее, разумеется, имеет смысл только тогда, когда существуют эффективный метод вычисления спектров для достаточно широкого класса графов и обратный метод - «декодирование» спектра, т. е. восстановление интересующих нас свойств графа по его спектру при помощи алгебраических вычислений.

Следует отметить, что химики и физики обычно знают структуру графа и интересуются его спектром, в то время как специалисты в области теории графов и комбинаторики в большинстве случаев предполагают, что спектр графа известен и при этом задаются вопросом о том, что можно сказать о структуре графа.

Эти вопросы совместно с общей задачей теории графов о нахождении и исследовании инвариантов графа, а также некоторые другие весьма интересные факты, стоящие за этой темой, стимулировали исследование взаимосвязей между спектральными и структурными свойствами графов. Представляет также интерес характер поведения собственных значений при некоторых преобразованиях графов, особенно в тех случаях, когда спектр сложного графа можно выразить в терминах спектров элементарных графов.

1.2 ОСНОВНЫЕ ПОНЯТИЯ И ОБОЗНАЧЕНИЯ

Приведем еще несколько теоретико-графовых понятий, часто применяемых в настоящей работе, а также введем некоторую типовую систему обозначений и объясним сущность отдельных соглашений, которые используются в дальнейшем.

Говорят, что граф Н = (У, V) является подграфом графа G = (Х, U), если YX и V U. Граф Н называется остовным подграфом или частичным графом графа G, если У = Х. Если множество V состоит из всех тех ребер множества U, которые соединяют вершины из множества У, то Н называется порожденным подграфом. Иногда говорят, что порожденный подграф покрывается своими вершинами, а частичный подграф покрывается своими ребрами.

Число ребер, инцидентных данной вершине неориентированного графа, называется степенью или валентностью этой вершины. Заметим, что неориентированную петлю считают дважды, и, следовательно, ее вклад в валентность вершины, к которой она присоединена, равняется 2. Если все вершины графа имеют одну и ту же валентность, равную r, то граф называется регулярным степени r.

В орграфах будем проводить различие между полустепенью захода или задней валентностью и полустепенью исхода или передней валентностью вершины, указывающих соответственно число дуг, которые заходят в данную вершину, и число дуг, которые из нее выходят.

Если дуга направлена из вершины х к вершине у, то запись имеет вид ; х и у называются соседними вершинами, причем х является задним соседом вершины у, а у - передним соседом вершины х.

Контур длины n (обозначается ) - это орграф с множеством вершин {x1, ...,хn}, у которого дyгaми являются (хi, хi+l), i = 1, ... , n - 1, и (хn,x1). Линейный ориентированный граф - это орграф, в котором полустепени исхода и захода каждой вершины равны 1, т. е. он состоит из контуров.

Остовный линейный подграф мультиграфа (мультиорграфа) G, т. е. линейный подграф графа G, содержащий все его вершины, иногда называют линейным фактором графа G. Линейный фактор мультиграфа состоит из непересекающихся копий К2.

Регулярный остовный подграф степени s мультиграфа G называется фактором (регулярным) степени s, или, короче, s-фактором графа G.

Любая последовательность следующих друг за другом ребер (дуг) мультиграфа (мультиорграфа в направлении их ориентации) называется мaршрутом. Длина маршрута - это число его ребер (дуг). Маршрут может содержать одно и то же ребро (дугу) более чем один раз.

Простая цепь Рn длины n - 1, n ? 2,- это граф, имеющий n вершин х1, … , хn и n - 1 ребер, в котором вершины хi, и хi+l, i = 1, ... ... , n - 1. соединены ребром.

Мультиграф (мультиорграф) называется связным (сильно связным), если любые его две вершины соединены простой цепью (маршрутом). В противном случае мультиграф называется несвязным и состоит из двух и более частей, называемых компонентами; две вершины несвязного графа принадлежат различным компонентам, если они не соединяются никакой простой цепью.

Длина кратчайшей простой цепи между двумя вершинами называется расстоянием между этими вершинами. Диаметр связного мультиграфа - наибольшее из расстояний между его вершинами.

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

Мультиграф G называется правильно раскрашенным, если его смежные вершины имеют различные цвета. Граф G является k-раскрашиваемым, если его можно правильно раскрасить k цветами. Хроматическое число графа G равно k, если G k-раскрашиваем и не является (k - l)-раскрашиваемым. Граф G называется двудольным, если его хроматическое число равно 1 или 2. Множество вершин двудольного мультиграфа G можно разбить на две части, например Х и У, таким образом, чтобы каждое ребро графа G соединяло вершину из Х с некоторой вершиной из У. Иногда граф G будем обозначать как G = (Х; У; U), где U - множество ребер графа. Если G - связный граф, имеющий по крайней мере одно ребро, то Х и У не пусты и граф G определяется однозначно (с точностью до обозначений). Если вершины обозначены таким образом, что

Х = {x1, x2, … , xт}, Y = {xт+l, xт+2, … , xт+n} ,

то матрица смежности графа G будет иметь вид

,

где В - nт-матрица, а ВТ - матрица, транспонированная к матрице В.

Мультиграф называется полурегулярным степеней r1, r2 (возможно r1= r2 ) если он двудольный, каждая его вершина имеет степень r1или r2 . И каждое ребро соединяет некоторую вершину степени r1 с некоторой вершиной степени r2 .

Полный n-вершинный граф Кn - это граф, любые две вершины которого соединены ребром. Полный двудольный граф с n + т вершинами обозначается через Кт,n; K1,n называется звездой. Полный k-дольный граф с n1 + n2 + … + nk вершинами обозначается .

Лес - это граф без циклов, дерево - связный лес.

Дополнением графа G называется граф, у которого множеством вершин является множество вершин графа G и две вершины смежны в тогда и только тогда, когда они не смежны в графе G. Очевидно, =G. Граф, не имеющий ни одного ребра, называется вполне несвязным; его дополнением является полный граф.

Граф подразбиений S(G) графа G получается из G, если каждое ребро графа G заменить простой цепью длины 2, или, что равносильно, поместить одну дополнительную вершину на каждом ребре графа G. Ясно, что S (G) является двудольным графом (Х, Y; U), где Х и Y множества соответственно исходных и дополнительных вершин.

Реберным графом L (G) графа G называется граф, вершинами которого являются ребра графа G, и две вершины графа L (G) смежны тогда и только тогда, когда соответствующие им ребра графа G имеют общую вершину.

Вершинно-реберная матрица инциденций R мультиграфа G = (Х, U) без петель определяется следующим образом. Пусть

Х = {x1, x2, … , xт}, U = {u1,u2, … ,uт}

Тогда R = (bij) является nт-матрицей, где bij = 1, если xi инцидентна ui (т. е. является концевой вершиной ребра ui), и bij = 0 В противном случае. Реберно-вершинная матрица инциденций - это матрица , транспонированная к матрице R.

Матрица смежности мультиграфа (мультиорграфа) G обозначается через А = А (G). Матрицей степеней (или валентностей) D мультиграфа называется диагональная матрица, у которой на (i, i)-месте находится значение степени хi вершины хi.

Для графа G вершинно-реберная матрица инциденции R, матрица степеней D и матрицы смежности графов G, L (G) и S (G) связаны следующими соотношениями:

Приведенные выше определения и формулы легко обобщаются на произвольные мультиграфы.

Матрица (0,1,-1)-инциденций V мультиорграфа G без петель с множеством вершин x1, x2, … , xт и множеством дуг u1,u2, … ,uт определяется следующим образом: V = (хij) - это nт-матрица, у которой

хij = 1, если uj; выходит из xi;

хij = - 1, если и, заходит в xi;

хij = О во всех остальных случаях.

В большинстве случаев мы будем пользоваться следующими типовыми обозначениями: n- число вершин графа, m - число его ребер или дуг; r - степень регулярного графа, а также его индекс; I - единичная матрица, In - единичная матрица порядка n; J - квадратная матрица, все элементы которой равны 1. Матрица, транспонированная к матрице X, обозначается через Хт, rk Х - ранг матрицы Х.

Символ Кронекера дij определяется следующим образом: дij = 1 и дij = О, если j?i. Запись a/b означает, что а делит b.

Спектр неориентированных мультиграфов состоит из действительных чисел. В этом случае собственные значения л1, л2,…, лn упорядочены таким образом, что л1=r? л2,?…? лn

Другие теоретико-графовые понятия и обозначения будут приводиться в тех местах, где они непосредственно используются.

1.3 НЕКОТОРЫЕ ТЕОРЕМЫ ТЕОРИИ МАТРИЦ И ИХ ПРИМЕНЕНИЕ К ИССЛЕДОВАНИЮ СПЕКТРОВ ГРАФОВ

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

Множество собственных векторов, соответствующих собственному значению л , вместе с нулевым вектором образуют собственное пространство, соответствующее л. Геометрическая кратность собственного значения л - это размерность соответствующего ему собственного пространства. Алгебраической кратностью собственного значения л называется его кратность как корня соответствующего характеристического многочлена. Алгебраическая кратность собственного значения л всегда не меньше его геометрической кратности.

Матрица Х называется симметрической, если хТ = Х.

Теорема 1.1. Геометрическая кратность собственного значения симметрической матрицы равна его алгебраической кратности.

В дальнейшем термин «кратность собственного значения» будет означать алгебраическую кратность. Матрица называется неотрицательной, если ее элементами являются неотрицательные числа.

Так как матрица смежности мультиграфа (мультиорграфа) G неотрицательна, то спектр графа G обладает свойствами спектра неотрицательных матриц. Для этих матриц справедливы следующие утверждения.

Теорема 1.2 . Неотрицательная матрица всегда имеет неотрицательное собственное значение r такое, что модули всех ее собственных значений не превосходят числа r. Этому «максимальному» собственному значению соответствует собственный вектор с неотрицательными координатами.

Вектор с положительными (неотрицательными) координатами в дальнейшем будем называть положительным (неотрицательным) вектором. Матрица А называется разложимой, если имеется матрица перестановок Р такая, что матрица Р-1- АР имеет вид где Х и Z -квадратные матрицы. В противном случае матрица А называется неразложимой.

Спектральные свойства неразложимых неотрицательных матриц описываются следующей теоремой Фробениуса.

Теорема 1.3. Неразложимая неотрицательная матрица А всегда имеет положительное собственное значение r, которое является простым корнем характеристического уравнения. Модули всех других собственных значений не превосходят числа r. «Максимальному» собственному значению r соответствует собственный положительный вектор. Кроме того, если А имеет h собственных значений, по модулю равных r, то эти числа все различны между собой и являются корнями уравнения и вообще весь спектр [] матрицы А, рассматриваемый как система точек в комплексной л-плоскости, отображается на себя при повороте этой плоскости на угол 2р/h. Если h > 1, то перестановкой строк с такой же перестановкой столбцов можно матрицу А привести к следующему «циклическому» виду:

(1.1)

вдоль главной диагонали здесь стоят квадратные блоки.

При h > 1 матрица А называется импримитивной; число h - ее индекс импримитивности. В противном случае матрица А примитивна.

Согласно теореме 1.3 спектр мультиграфа (мультиорграфа) G лежит в круге , где r - наибольшее действительное собственное значение. Это собственное значение называется индексом графа G. Алгебраическая кратность индекса может быть больше 1. В этом случае существует соответствующий данному индексу неотрицательный собственный вектор.

Неразложимость матрицы смежности графа связана со свойством связности. Матрица смежности сильно связного мультиорграфа неразложима: мультиорграф, матрица смежности которого неразложима, сильно связен. В неориентированных мультиграфах свойство сильной связности сводится просто к связности.

Согласно теореме 1.3. индекс сильно связного мультиорграфа является простым собственным значением матрицы смежности, которому соответствует положительный собственный вектор.

Как показывает следующая теорема, в случае симметрической матрицы смежности справедливо также обратное утверждение .

Теорема 1.4. Если «мaксимaльное» собственное значение r неотрицательной матрицы А является простым и ему соответствуют положительные собственные векторы матриц А и АТ, то А - неразложимая матрица.

Теорема 1.5. «Максимальному» собственному значению r неотрицательной матрицы А соответствует положительный собственный вектор матрицы А и положительный собственный вектор матрицы АТ тогда и только тогда, когда матрица А может быть представлена перестановкой строк и такой же перестановкой столбцов в квазидиагональном виде А = diag (А1, … , As). где A1, … Аs - неразложимые матрицы, у каждой из которых r «максимальное» собственное значение.

Приведем еще несколько теорем из теории матриц, характеризующих спектральные свойства графов.

Теорема 1.6 . «Максимальное» собственное значение r' любой главной подматрицы (порядок которой меньше n) неотрицательной матрицы А (порядка n) не превосходит «максимального» собственного значения r матрицы А. Если А - неразложимая матрица, то неравенство r' < r справедливо всегда. Если А - разложимая матрица, то по крайней мepe для одной главной подматрицы r' = r.

Теорема 1.7. При увеличении любого элемента неотрицательной матрицы А «максимальное» собственное значение не уменьшается. Оно строго возрастает, если А - неразложимая матрица.

Теоремы 1.6 и 1.7 утверждают, что индекс любого подграфа связного (сильно связного) мультиграфа (мультиорграфа) G меньше индекса графа G.

Теорема 1.8 Все собственные значения эрмитовой матрицы являются действительными числами.

Комплексная матрица А = () называется эрмитовой, если Ат =, т.е. = .

Теорема 1.10 . Пусть А - эрмитова матрица с собственными значениями и В - одна из ее главных подматриц с собственными значениями м1,…, мm .Тогда справедливы неравенства лn-m+1?мi?лi (i = 1, ... , m).

Это - известные неравенства Коши, а само утверждение известно как теорема о сплетении.

Теорема 1.11 Пусть А - действительная симметрическая матрица с собственными значениями при условии что задано разбиение множества {l, 2, ... , n} =, рассмотрим соответствующую блочную матрицу А = (Аij), у которой блок имеет размеры ni nj. Если еij - сумма значений элементов матрицы Аij и В = (eij/ni), т. е. eij/ni - средняя сумма значений элементов строки матрицы А, то спектр матрицы В содержится в отрезке [лn ,л1].

Если предположить, что в каждом блоке Aij (см. теорему 1.11) все суммы значений элементов строк одинаковы, можно получить даже более сильное утверждение.

Теорема 1.12. Пусть А - блочная матрица с разбиением на блоки согласно условиям теоремы 1.11. Пусть, далее, для всех строк блока А ij сумма bij значений элементов строки одинакова и В = (bij). Тогда спектр матрицы В содержится в спектре матрицы А.

Квадратные матрицы А и В называются подобными, если существует невырожденная квадратная матрица Х, преобразующая А в В, т. е. такая, что X-1AX = В. Каждая симметрическая матрица и каждая матрица, все собственные значения которой различны, подобны диагональной матрице. Если А является матрицей смежности мультиграфа, то она симметрична и, следовательно, подобна диагональной матрице D, а именно D = (дij,лi).

Обратимся к известной теореме Гамильтона - Кэли, которая утверждает, что всякая квадратная матpица А удовлетворяет своему характеристическому уравнению, т. е. если f(л)=I, то f(А)=О.

Минимальный многочлен m (л) матрицы А - это многочлен m (л) = лм + ... такой, что: (i) m (А) =О; (i) степень м многочлена m(л), удовлетворяющего условию (i), является минимальной.

Кроме того, справедливы следующие предложения.

1. Многочлен m(л) однозначно определяется матрицей А.

2. Если F (л) - многочлен, для которого F (А) = О, то m(л )| F (л) и, в частности, m(л )| F (л) .

3. Пусть {л(1), л(2) ,… , л(k)} - множество различных собственных значений матрицы А и - алгебраическая кратность собственного значения . Тогда

,

и

причем 0< ( = 1, 2, …, k).

4. Если А подобна диагональной матрице, то все равны 1 и

5. Пусть n - порядок матрицы А. Если все собственные значения матрицы А различны, то

Квадратная матрица, минимальный и характеристический многочлены которой тождественны, называется простой. Таким образом, предложение 5 утверждает, что квадратная матрица, все собственные значения которой различны, является простой.

А теперь опишем некоторые основные свойства спектра неориентированного мультиграфа. Для удобства изложения результаты в большинстве случаев будем приводить без доказательств, так как их можно найти в соответствующих местах в последующих главах.

Матрица смежности неориентированного мультиграфа G является симметрической и, следовательно, эрмитовой. Поэтому спектр графа G содержит лишь действительные числа, которые согласно теореме 1.8 принадлежат отрезку [-r, r].

Пусть [] - спектр мультиграфа. Так как удвоенное число петель равно следу матрицы смежности, то в случае мультиграфа без петель tr А = о, т. е. = О. Число вершин, разумеется, равно n, и тог да число ребер m неориентированного графа без петель и кратных ребер определяется формулой .

Для индекса r связного графа выполняется неравенство . Нижняя граница достигается в случае, когда граф является простой цепью, верхняя при полном графе. Если предположение о связности графа не принимается во внимание, то для графа без ребер r = 0, в противном случае r? 1 ,

Для наименьшего собственного значения q спектра графа G справедливо неравенство . Для графа без ребер q =0, в противном случае q? -1. Это следует из теоремы 1.9, так как подграф К2 соответствует главной подматрице, наименьшее собственное значение которой равно -1. Значит, q = -1 тогда и только тогда, когда все компоненты графа G являются полными графами . Нижняя граница q = -r достигается в случае, когда компонента графа G с наибольшим индексом является двудольным графом . Резюмирует сказанное выше следующая теорема, описывающая фундаментальные спектральные свойства неориентированных графов.

Теорема 1.13. Для спектра [] неориентированного графа G справедливы следующие утверждения:

10 - действительные числа и=0 ;

20 если граф G не содержит ребер, то =0;

30 если граф G содержит по меньшей мере одно ребро, то

(1.2)

?q? -1 (1.3)

Верхняя граница в (1.2) достигается тогда и только тогда, когда G - полный граф, в то время как нижняя граница достижима тогда и только тогда, когда компонентами графа G являются графы К2 и, возможноК1. Верхняя граница в (1.3) достигается тогда и только тогда, когда компонентами графа G являются полные графы; нижняя граница достигается тогда и только тогда, когда компонента графа G с максимальным индексом является двудольным графом. Если G - связный граф, то нижняя граница в (1.2) заменяется на 2соs; Равенство справедливо тогда и только тогда, когда G - простая цепь.

А теперь перечислим некоторые спектральные свойства регулярных мультиграфов. Индекс мультиграфа равен его степени. Легко видеть, что это утверждение справедливо и для несвязных мультиграфов, за исключением случая, когда индекс не является простым собственным значением. Кратность индекса равна числу компонент. Очевидно, что вектор, у которого все координаты равны 1, является собственным вектором, соответствующим индексу.

Собственные векторы, соответствующие остальным собственным значениям, ортогональны этому вектору, т. е. сумма их координат равна О.

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

ГЛАВА 2. СВЯЗИ МЕЖДУ СПЕКТРАЛЬНЫМИ И СТРУКТУРНЫМИ СВОЙСТВАМИ ГРАФОВ

В этой главе описывается лишь часть известных связей между спектром и структурой графов. Известно, что некоторые структурные свойства не определяются однозначно спектром, тем не менее даже в таких случаях можно, используя спектр, уточнить область изменения этих свойств.

В данной главе содержится много неравенств и для различных численных характеристик. Во всех приведенных ниже теоремах предполагается, что заданы либо спектр, либо собственные векторы матрицы смежности графа, либо и то и другое вместе и указан некоторый класс, к которому принадлежит граф. Если задан спектр графа, предполагается, что известен его характеристический многочлен, и наоборот. В некоторых случаях класс графов, к которому принадлежит граф с заданным спектром, может быть определен с помощью спектра.

2.1 ОРГРАФЫ

Орграф G=(V,E) есть пара множеств, V- множество вершин, Е- множество дуг.

Будем полагать, что А - матрица смежности,

РG(л) (2.1)

- характеристический многочлен, а - спектр графа G.

С самого начала будем предполагать, что в рассматриваемых орграфах допускаются кратные ориентированные ребра и петли. Прежде чем формулировать некоторые теоремы, отметим несколько простых результатов.

Число вершин орграфа G равно степени n его характеристического многочлена, т. е. числу собственных значений орграфа G. Число ориентированных петель равно следу матрицы смежности - сумме л1+…+ лn , т.е. величине - al. Если все вершины орграфа G имеют одно и то же число петель, то характеристический многочлен рн (л) орграфа Н, получающегося из G в результате удаления всех его петель, полностью определяется многочленом РG (л): если каждая вершина орграфа G имеет точно h ориентированных петель, то и Рн (л) = РG (л + h).

Если G -- орграф без петель, то ни одна пара вершин орграфа G не соединена двумя противоположно ориентированными ребрами тогда и только тогда, когда а2 = 0. Этот результат можно легко объяснить при рассмотрении всех главных миноров второго порядка матрицы смежности.

Непосредственно следует: орграф G не содержит контуров тогда и только тогда, когда все коэффициенты aI (i = 1, ... ..., n) равны 0, т. е. тогда и только тогда, когда спектр орграфа G не содержит отличных от нуля собственных значений.

Число замкнутых маршрутов заданной длины k в орграфе G может быть определено посредством спектра орграфа G;

это число равно tr Aк =

Применяя теорему Гамильтона - Кэли, из характеристического многочлена (3.1) выводим следующее соотношение:

An+k +аiAn+k-1} + *** +а nАк = О (к = 0, 1, ...). (2.2)

Из (2.2) можно получить некоторую информацию относительно структуры орграфа.

А теперь сформулируем несколько теорем о цикловидной структуре орграфа G без кратных ребер. Отдельные утверждения приводятся в дальнейшем как частные случаи этих теорем.

Длина g (G) кратчайшего контура в орграфе G (если только он существует) называется обхватом орграфа G. Если G не имеет контуров, то g(G) = +?. Очевидно, каждый линейный ориентированный подграф орграфа G с менее чем 2g вершинами, где g = g (G), необходимо является контуром.

Выводим

ai = (i<2g).

спектр граф теория матрица

Таким образом, --ai является числом контуров длины i, содержащихся в G.

Теорема 2.1. Пусть G -- орграф с характеристическим многочленом (2.1) и g (G) = g. Пусть, далее, i ? min (2g-1, n). Тогда число циклов длины i, содержащихся в G, равно - ai. Обхват g орграфа G равен наименьшему индексу i, для которого ai ? 0.

Этот результат обобщается и на тот случай, когда можно определить число контуров длины i для некоторого i > 2g -- 1. Введем новое понятие: d-обхват орграфа. Для произвольного целого числа d > 1 d-обхват gd (G) орграфа G определяется как длина кратчайшего контура среди тех контуров, длины которых не делятся на d. Если же таких контуров нет, то gd (G) = +?.

Теорема 2.2. Если G -- орграф с характеристическим многочленом (2.1), g (G) = g, gd (G) -- gd и, кроме того, i? min (g + gd - 1, n), i0 (mod d), то число контуров длины i, содержащихся в G, равно -; d-обхват gd орграфа G равен наименьшему индексу, не делящемуся на d, для которого at ? 0.

Замечание. Если g не делится на d, то, очевидно, gd = g и теорема 2.2 утверждает меньше, чем теорема 2.1. В противном случае, когда d является множителем в g, разумеется, gd > g. Если же gd > g + 1, теорема 2.2 дает новую информацию, которую нельзя получить из теоремы 2.1.

Пример. Пусть g = 9, gg = 15, gg = 20. Теорема 2.1 дает числа контуров длины с для с ? 17. При d = 9 теорема 2.2 дает эти числа дополнительно для с = 19, 20, 21, 22, 23, а при d = 3 -- также и для с = 25, 26, 28.

При d = 2 получаем

Следствие. Длина g2 кратчайшего контура нечетной длины в G равна индексу первого отличного от нуля коэффициента среди a1 a3, а5, ...; число кратчайших контуров нечетной длины равно --аg2.

Доказательство теоремы 2.2. Пусть i? min (g + gd - 1, n), i 0 (mod d). Тогда каждый линейный ориентированный подграф в G с i вершинами необходимо является контуром. Как и в приведенных выше рассуждениях,

что и завершает доказательство.

Из следствия теоремы 2.2 можно легко вывести следующую теорему.

Теорема 2.3. Орграф G не имеет контуров нечетной длины тогда и только тогда, когда его характеристический многочлен имеет вид

РG (л) =лn + а2лn-2 + а4 лn-4 + * * * = лp * Q (л2),

где Q -- многочлен, а р = 0 при четном n и р = 1 в других случаях.

Нетрудно доказать также такую теорему.

Теорема 2.4. Сильно связный орграф G с наибольшим собственным значением r не имеет контуров нечетной длины тогда и только тогда, когда -r также является собственным значением орграфа G.

Доказательство. Если G не имеет контуров нечетной длины, то тогда согласно теореме 2.3 -- r также является собственным значением графа G.

Обратно, если -- r принадлежит спектру орграфа G, то матрица смежности орграфа G импримитивна. В этом случае индекс импримитивности n может быть лишь четным числом и существует матрица перестановки Р такая, что РАР -1 имеет вид (1.1). А так как h -- четное, то G, очевидно, не содержит контуров нечетной длины, что и доказывает теорему.

Орграф G назовем циклически k-дольным, если множество его вершин может быть разбито на непустые взаимно непересекающиеся множества таким образом, что если (х, у) ( ) -- дуга орграфа G, то j-i (mod k). Заметим, что циклически k-дольный орграф является также циклически l -дольным, если k делится на l. Матрица смежности циклически h-дольного орграфа имеет вид (1.1). Можно сформулировать такую теорему.

Теорема 2.5. Характеристический многочлен циклически k-дольного орграфа G имеет вид

РG (л) = лp * Q (л2), (2.3)

где Q -- нормализованный многочлен, Q (0) ? 0, а р -- неотрицательное целое число.

Если G --сильно связный орграф, характеристический многочлен которого имеет вид (2.3), то G -- циклически k-дольный орграф.

Следующая теорема взята непосредственно из теории матриц .

Теорема 2.6. Пусть d, ..., и ,…, -- полустепени соответственно захода и исхода вершин орграфа G. Тогда для индекса r орграфа G справедливы следующие неравенства:

(2.4)

(2.5)

Если G сильно связен, то равенство в правой или левой части неравенства (2.4) или (2.5) справедливо тогда и только тогда, когда все величины d, ..., (или ,…,) равны.

Теорема 2.7 Для орграфа G с матрицей смежности А справедливы следующие утверждения:

1) существует многочлен Р (х) такой, что равенство

J=P(A) (2.6)

имеет место тогда и только тогда, когда граф G сильно связен и регулярен;

единственным многочленом Р (х) наименьшей степени, для которого выполняется (2.6), является nS (x)/S (d), где (х-- d) S (х) -- минимальный многочлен матрицы A, a d -- степень орграфа G;

если Р(х) -- многочлен наименьшей степени, для которого выполняется (2.6), то степень орграфа G является наибольшим действительным корнем уравнения Р (х) = n.

О = R (А) = (А -- dI) S (A). (2.7)

Если о -- нулевой вектор, то, поскольку R (A) х= о для всех векторов х, из (2.7) следует, что (А -- dI) S(A)х = о,

поэтому S(A) = бu для некоторого б.

Пусть (и,) -- скалярное произведение векторов и и х. Если и и х таковы, что то для каждого k и, таким образом, . Поэтому , т. е. б = 0.

Таким образом, для всех таких , что (,и)=0; далее, Следовательно, т.е. (2.6) выполняется для

(2.8)

Это завершает доказательство утверждения 1; часть 2 следует из того, что степень многочлена (2.8) меньше степени минимального многочлена матрицы А. Чтобы доказать 3, заметим, что А -- неотрицательная матрица, все строчные и столбовые суммы которой равны d. Таким образом, все собственные значения матрицы А по абсолютной величине не больше d. Корни многочлена Р (х) являются собственными значениями матрицы А, и, следовательно, для действительного х > d Р (х) является возрастающей функцией по х. Из (2.8) следует, что Р (d) = n, и поэтому, поскольку Р (х) -действительный многочлен, Р (х) > n для х > d.

Это завершает доказательство теоремы 2.7.

Заметим, что многочлен (2.8) называется соответствующим орграфу G, и будем говорить, что орграф G соответствует многочлену (2.8).

Некоторые нерегулярные графы могут иметь многочлены с подобными свойствами.

2.2 ГРАФЫ

Граф включает множество вершин и множество ребер, являющиеся подмножеством декартова квадрата множества вершин (т.е. каждое ребро соединяет ровно две вершины).

Если мультиграф Н имеет симметрическую матрицу смежности А с четными значениями диагональных элементов, то матрицу А можно интерпретировать как матрицу смежности неориентированного графа (мультиграфа) G. В этом смысле к графам могут быть применены результаты предыдущего параграфа. Собственные значения графа являются действительными числами, которые можно упорядочить таким образом, чтобы последовательность л1,…, лn была убывающей. В дальнейшем всегда будет использоваться указанное соглашение.

Далее рассматриваются только неориентированные графы без кратных ребер и петель.

Следующая теорема может быть доказана с привлечением рассуждений непосредственно из теории матриц.

Теорема 2.8. Если -- среднее значение валентности, а r наибольшее собственное значение графа G, то

(2.9)

где равенство имеет место тогда и только тогда, когда граф G регулярен.

Доказательство. Поскольку, как известно, матрица смежности А = (aij) графа G эрмитова, то задача нахождения максимального значения отношения Релея

(2.10)

(xi -- произвольные действительные числа, не равные одновременно нулю) имеет решение R =r. Максимум достигается тогда и только тогда, когда xi (i = 1, .... n) являются координатами собственного вектора матрицы А, соответствующего r.

Если в (2.10) положить хi = 1 (i = 1, ..., n), то

где di = -- валентность вершины i. Таким образом, -- частное значение отношения Релея, что доказывает (2.9).

Для регулярных графов равенство в выражении (2.9) достигается, так как в этом случае наибольшее собственное значение графа G совпадает с его степенью. Обратно, пусть справедливо равенство (2.9). Тогда значения xi = 1 (i = 1, ..., n) образуют собственный вектор матрицы А, соответствующий r, и из = r xi (i = 1, ..., n) следует di = = r (i = 1 ..... n). Поэтому граф G регулярен. Это и завершает доказательство теоремы.

Применяя к графам теорему 2.6 и используя теорему 2.8, получаем неравенства

???

где и -- соответственно минимальное и максимальное значения валентностей в G.

Рассмотрим еще несколько предложении, устанавливающих связь между коэффициентами аi многочлена РG (л) и некоторыми структурными свойствами графа G. Благодаря отсутствию петель всегда а1 = 0. Число замкнутых маршрутов длины 2 равно, очевидно, удвоенному числу ребер m, поэтому m =. Аналогичным образом может быть найдена и формула для числа t треугольников. Получается и . Коэффициент а4 равен числу пар несмежных ребер без удвоенного числа простых циклов С4 длины 4, содержащихся в G. Аналогичным образом находим, что коэффициент а5 равен удвоенному числу фигур, состоящих из треугольника и ребра (они не имеют общих элементов) без удвоенного числа простых циклов С5 длины 5.

Если G -- лес, то, очевидно, число 1-факторов равно \аn\; аn = (-1)n/2, если имеется 1-фактор, и аn = 0 в противном случае.

Для доказательства следующей теоремы потребуется простая лемма, которую приведем без доказательства.

Лемма 2.1. Пусть б1, ..., бk --действительные числа и r, s (r -- четное,r < s) -- неотрицательные целые числа. Тогда для а > 0 справедлива следующая импликация:

Равенство с правой стороны импликации имеет место тогда и только тогда, когда абсолютное значение точно одного из кванторов б1, ...,бk равно а, а все остальные кванторы равны нулю. Из строгого неравенства с левой стороны следует строгое неравенство с правой стороны импликации.

Teopeма 2.9. Если [л1 ,…,лn ] - спектр графа G, то из неравенства

(2.11) следует, что G содержит по крайней мере один треугольник.

Доказательство. Согласно лемме (2.1) из (2.11) получаем

Тогда число треугольников

что и завершает доказательство.

Так как , где т -- число ребер графа G, то справедливо

Следствие. Если , то G содержит по крайней мере один треугольник.

Следствие теоремы 2.2 может быть переформулировано для неориентированных графов следующим образом. Наряду с графом G рассмотрим орграф Н, который имеет такую же матрицу смежности, как и G. Каждому кратчайшему простому циклу нечетной длины графа G соответствует в точности два кратчайших цикла нечетной длины (с противоположной ориентацией) орграфа Н, и, следовательно, число кратчайших простых циклов нечетной длины графа G равно половине числа кратчайших контуров нечетной длины Н. Таким образом, доказана

Теорема 2.10. Пусть G -- граф с характеристическим многочленом (2.1). Тогда длина f кратчайшего простого цикла нечетной длины в G равна индексу первого не равного нулю коэффициента среди а1, а3, а5, ... Число кратчайших простых циклов нечетной длины равно .

Из этой теоремы немедленно следует

Теорема 2.11. Граф, содержащий, по крайней мере, одно ребро, является двудольным тогда и только тогда, когда его спектр, рассматриваемый как множество точек действительной оси, симметричен по отношению к нулевой точке.

Теорема 2.11 является одной из наиболее известных теорем, устанавливающих очевидную тесную связь между структурой и спектром графов. По-видимому, важность этой теоремы впервые была отмечена в химической литературе Коулсоном и Рашбруком (химики обычно называют ее «теоремой парности»). Полностью эта теорема была доказана Захсом в форме теоремы 2.3.

Интересно отметить, что теорема 2.11 неоднократно переоткрывалась.

Характеризация связного двудольного графа возможна также с помощью теоремы 2.4.

Рассмотрим задачу определения обхвата графа. Как и в случае орграфа, обхват графа G -- это длина кратчайшего из простых циклов этого графа.

Если попытаться сформулировать теорему для графов, подобную теореме 2.1, то возникнут следующие трудности. Наряду с графом G рассмотрим орграф H, который имеет ту же матрицу смежности, что и G. Если граф G содержит по крайней мере одно ребро, то g (H) = 2, тогда как g (G) при этом может быть сколь угодно большим. Поэтому обхваты графов G и H не связаны друг с другом. Однако легко убедиться вот в чем. При i <g (G) базисная фигура существует лишь для четного i = 2q и каждая базисная фигура U2q состоит из q несмежных ребер, так что р (U2q) = q и с (U2q) = 0. Следовательно,

(i<g(G)),

где bq -- число базисных фигур, состоящих в точности из q несмежных ребер.

Для i = g (G) базисные фигуры могут быть либо фигурами описанного выше вида (состоящими из несмежных ребер и лишь для четных i), либо это могут быть простые циклы длины g (G). Во втором случае вклад каждой такой базисной фигуры в ai равен --2. Если

,

то = 0 для i < g (G) и равно удвоенному числу простых циклов длины g(G)

Итак, получен следующий результат.

Теорема 2.12. Пусть G -- граф (мультиграф) с характеристическим многочленом (2.1) и bq -- число базисных, фигур, состоящих из q несмежных ребер. Пусть, далее,

Тогда g (G) равен индексу первого отличного от нуля числа среди число простых циклов длины g (G) равно -

Так как матрица смежности А графа является симметрической, можно на основе спектра определить ее минимальный многочлен. Если, как известно, {л(1), ..., лm } -- множество всех различных собственных значений матрицы А, то соответствующий минимальный многочлен

Пусть Тогда справедливо соотношение

(k=0,1,…) (2.12)

Используя его, можно доказать следующую теорему.

Теорема 2.13. Если связный граф G имеет точно m различных собственных значений, то его диаметр D удовлетворяет неравенству .

Доказательство. Предположим, что теорема неверна. Тогда для некоторого связного графа G имеем D = s? m. Из определения диаметра следует, что для некоторых i и j элементы а из i-й строки и j-го столбца матрицы Аk (k = 1, 2, ...) равны нулю при k< s, тогда как а = 0.

Положим в (2.12) k= s -- m. Используя определенное таким образом соотношение, из а? 0 (k = 1, ..., s -- 1) выводим а = 0, что противоречит предположению.

Это и завершает доказательство теоремы.

Число внутренней устойчивости б (G) графа G определяется как наибольшее число вершин, которые могут быть выбраны в G таким образом, что ни одна пара из них не соединена ребром в G.

Теорема 2.14. Число внутренней устойчивости б (G) графа G удовлетворяет неравенству

б(G) ? po + min (р-, р+), (2.13)

где p- , р0, р+ -- соответственно числа собственных значений графа G, меньших нуля, равных нулю и больших нуля. Существуют графы, для которых в (2.13) имеет место равенство.

Доказательство. Пусть s = р0 + min (p-, р+). Предположим, что существует граф G, для которого б (G) > s. Тогда существует порожденный подграф графа G с б (G) вершинами, не содержащий ребер. Отсюда следует, что главная подматрица порядка б (G) матрицы смежности графа G является нулевой матрицей. А так как все собственные значения нулевой матрицы равны нулю, то для собственных значений л1,…, лn графа G дает неравенства

л?0, (i = 1,... , б(G)).

Однако это противоречит предположению a (G) > s. Поэтому (2.13) справедливо.

Равенство в (2.13) имеет место, например, для полных графов. Это и завершает доказательство теоремы 2.14.

Теорема 2.15. Пусть и означают числа собственных значений графа G, которые меньше -1, равны -1 и больше -1; л* означает наименьшее собственное значение, большее -1. Пусть, далее, р = + 1 и s = min (p, ,r + 1), где r -- индекс (максимальное собственное значение) графа G, и



Если K(G)означает максимальное число вершин в полном подграфе графа G, то

(2.14)

Существуют графы, для которых равенство в (2.14) достигается.

Доказательство. Если G содержит полный подграф с k вершинами, то получаются следующие неравенства:

Наибольшее значение k, удовлетворяющее этим неравенствам, дается выражением в правой части неравенства (2.14). Равенство в (2.14) достигается, например, для полных многодольных графов. Это и завершает доказательство теоремы 2.15.

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

В общем случае хроматическое число не определяется спектром. Более того, Хоффман доказал, что в определенном смысле имеется существенное несоответствие между спектром и хроматическим числом графа.

Перейдем к изложению некоторых теорем, относящихся к рассматриваемой теме. Начнем с теоремы, принадлежащей Уилфу.

Теорема 2.16. Пусть ч(G) - хроматическое число, а r - индекс (равный максимальному собственному значению) связного графа G. Тогда

ч (G)? r + l. (2.15)

Равенство имеет место тогда и только тогда, когда G -- полный граф или простой цикл нечетной длины.

Доказательство. Пусть dmin (H) и dmax (H) означают наименьшую и наибольшую степень вершины в графе Н и пусть лl (H) -- индекс графа Н. Поскольку (G) -- хроматическое число графа G, то существует порожденный подграф Н графа G, для которого dmin (Н? (G) - 1. Получаем

dmin (H)? ч (G)-1 (2.16)

а, значит, и (2.15). Пусть в (2.15), а следовательно, и в (2.16) имеет место равенство. Тогда из лl (G) = л1 (Н) следует G =H, так как G связен. Далее, л1 (G) = dmin (G), откуда следует по теореме 2.8, что G регулярен. Значит, (G) = 1 + r = 1 + dmax (G). Из известной теоремы Брукса следует теперь, что G - либо полный граф, либо простой цикл нечетной длины. Это и завершает доказательство.

Прежде чем перейти к обобщению этой теоремы, введем несколько определений.

Граф G называется k-вырожденным для некоторого целого неотрицательного k, если dmin (H) ? k для каждого порожденного подграфа H графа G. Число вершинного разбиения (G) графа G есть наименьшее число множеств, на которые может быть разбито множество вершин графа G так, что каждое такое множество при этом порождает k-вырожденный подграф графа G. Так как 0-вырожденные графы -- это в точности вполне несвязные графы, то 0 (G) -- хроматическое число графа G. 1 (G) называется вершинной древесностью графа G, поскольку 1-вырожденные графы являются лесами.