Спектральная оценка диаметра графа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования  «Белорусский государственный университет  информатики и радиоэлектроники»

Республиканский конкурс  научных работ студентов высших учебных заведений Республики Беларусь

Научная секция «Математика»

 

 

СПЕКТРАЛЬНАЯ  ОЦЕНКА ДИАМЕТРА ГРАФА

 

 

Михальцова  Екатерина Олеговна

2 курс

 

Черняк  Жанна Альбертовна

доцент  кафедры высшей

математики, кандидат

физико-математических наук

 

 

 

 

 

 

 

Минск 2012

 

РЕФЕРАТ

Работа 12 с. 3 рис., 7 источников.

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

Цель работы: привести новое доказательство известной теоремы о связи диаметра графа (метрической характеристики графа) с одной из спектральных характеристик графа – количеством различных собственных значений его матрицы смежности.

 

 

СОДЕРЖАНИЕ

РЕФЕРАТ……………………………………...…………………………………………2

СОДЕРЖАНИЕ………………………………………………………………………….3

ВВЕДЕНИЕ………………………………………………………………………………4

1. Основные определения и понятия…………………………………………………...6

2. Диаметр графа ………………………………………………………………………9

ЗАКЛЮЧЕНИЕ…………………………………………………………………………12

ЛИТЕРАТУРА………………………………………………………………………….13

 

ВВЕДЕНИЕ

Начало третьего тысячелетия  знаменуется существенным ростом интереса к сложным сетям, таким как Internet, the world wide web (всемирная паутина), биологические сети,  транспортные сети, социальные сети, нейронные сети человеческого мозга и т.д.

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

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

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

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

_^,

где ;

  _– собственные значения матрицы ;

 – ортогональная матрица,  столбцы которой – нормированные собственные векторы матрицы .

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

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

 

1. Основные определения и понятия

Неориентированный граф – упорядоченная пара , для которой выполнены следующие условия:

1) – непустое множество вершин, или узлов,

2) – множество пар (в случае неориентированного графа – неупорядоченных) вершин, называемых ребрами.

Пример. Приведем пример неориентированного графа на шести вершинах

Рис. 1

;

 – множество  ребер.

С графом можно ассоциировать  несколько видов матриц (матрица  смежности, матрица инцидентности и т.д.), самой простой из которых является матрица смежности _{, элементы которой равны либо 1, либо 0, при этом} в том случае, когда вершины _и соединены ребром, в противном случае . Для неориентированных графов предполагается, что не содержит петель (т.е. элемент ) и кратных (повторных) ребер между двумя вершинами. В этом случае матрица смежности является симметрической, т.е. ^.

Для графа, изображенного  на рисунке 1, матрица смежности имеет вид:

₌

Путь длиной из вершины _{в вершину} – это последовательность ребер          _, где _{, , … , ,} причем                      _{,    .}

Простой путь – это путь, в котором все вершины различны.

Цикл длиной – это простой замкнутый путь длиной (он начинается и заканчивается в одной и той же вершине).

Справедливо следующее утверждение  о числе путей длиной , существующих между вершинами _{и в графе} .

Обозначим ^– -ю степень матрицы смежности графа , а _{– элемент} этой матрицы, стоящий в позиции .

Лемма о числе  путей

Число путей длиной из вершины _{в вершину графа} равно _.

Доказательство. Индукция по .

Пусть . Путем длиной 1 между вершинами _{и является ребро, соединяющее эти вершины}. Существует только один путь длиной 1 между вершинами _и тогда и только тогда, когда и _{в графе} соединены ребром, что, в свою очередь, равносильно тому, что элемент   в матрице смежности . Таким образом, каждый элемент матрицы равен числу путей длиной 1 между вершинами _{и :} это либо 0, если вершины _{и не смежны, либо 1, если} они соединены ребром.

Таким образом, свойство выполняется  для . Предположим, лемма верна для путей длиной .

Докажем, что тогда она  верна и для путей длиной .

Путь длиной из вершины _{в вершину состоит из пути длиной} из вершины _{в вершину , которая смежна вершине (рисунок 2)}. По индуктивному предположению, число путей длиной из вершины _{в вершину равно ^{, а число путей длиной 1 из вершины} в вершину равно} элементу _{. Тогда общее число путей из} вершины _в вершину _длиной равно (по правилам матричного умножения), что и требовалось доказать ( - число вершин графа ).

Рис. 2

 

2. Диаметр графа 

Граф  называется связным, если любые две его вершины соединены путем. Лемма о числе путей показывает, что связность графа эквивалентна существованию некоторого целого положительного , для которого: _{^{для любой пары вершин}} и _{. Наименьшее целое} положительное такое, что для любой пары вершин и _{, называется} диаметром графа . Таким образом, диаметр графа равен наидлиннейшему из кратчайших путей между любыми парами вершин в графе .

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

Теорема:

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

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

Доказательство:

Матрица смежности графа  имеет вид:

 

Рис. 3

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

, ó

 ó

 ó

, т.е.

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

Вернемся к обсуждению теоремы.

Теорема утверждает, что ó . Так как диаметр всегда больше либо равен единице, мы заключаем, что (что на самом деле мы и наблюдаем в действительности).

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

Доказательство:

По определению, диаметр  графа  – это наименьшее целое положительное такое, что для любой пары вершин и _{, но} хотя бы для одной пары вершин и _{, если} .

Предположим, что число  различных собственных значений матрицы смежности этого графа равно l. Известно, что в этом случае минимальный многочлен _{матрицы} имеет степень , то есть

  ,     (1)

Поскольку минимальный многочлен матрицы , по определению, является аннулирующим многочленом минимальной степени для матрицы (аннулирующий многочлен для матрицы — многочлен, значение которого для данной квадратной матрицы равно нулю), то (где О – нулевая матрица) или, с учетом равенства (1),

 ó

 ó

       для любой пары вершин и

    (2)

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

 

ЗАКЛЮЧЕНИЕ

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

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

 

ЛИТЕРАТУРА

1. Харари Ф. Теория графов.: Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. – М.: Едиториал УРСС, 2003. – 296 с.
2. Татт У. Теория графов.: Пер. с англ. – М.: Мир, 1988. – 424 с.
3. Оре О. Графы и их применение.: Пер. с англ. 1965. – 176 с.
4. Piet Van Mieghem. Graph Spectra for Complex Networks.: Cambridge University Press, 2011 – 364 с.
5. Уилсон Р. Введение в теорию графов.: Пер. с англ. 1977. – 208 с.
6. Зыков А.А. Основы теории графов.: - М.: Наука, 1987. – 384 с.
7. Richard A. Brualdy. The Mutually Beneficial Relationship of Graphs and Matrices.: American Mathematical Society, 2011 – 98 с.