Математическая модель. Метрические характеристики неориентированного графа

Пусть G(V,X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний C n 2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа : d(G) = maxd(v, w).

Эксцентриситет (максимальное удаление) вершины : r(v) = maxd(v, w);

Радиус графа: r(G) = min r(v);

Центр графа : любая вершина vÎV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин, радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радиус графа r(G) = 2.

Центры графа v 2 , v 3 , v 4 .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v 1 в v n .

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(v i): a(v 1) = 0, a(v i) = ¥, i ¹ 1. окрасить вершину v 1 и положить v = v 1 .

Шаг 2. Для каждой неокрашенной вершины v j изменить индекс по правилу:

a(v j) = min {a(v j), a(v) + l(v, v j)}.

Окрасить ту из вершин, для которой a(v j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v j . Положить v = v j .

Шаг 3. Если v = v j , закончить процедуру, так как кратчайший маршрут из v 1 в v n . если v ¹ v n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(v j)= ¥. В этом случае вершина v n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v 1 в v 6 .

Шаг 1. Окрасим вершину v 1 . Присвоим вершинам индексы: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Полагаем v 1 = v.

a(v 2) = min {¥, 0+4} = 4,

a(v 3) = min {¥, 0+7} = 7,

a(v 4) = min {¥, 0+3} = 3,

a(v 5) = min {¥, 0+¥} = ¥,

a(v 6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v 4 и ребро {v 1 , v 4 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 4 .

a(v 2) = min {4, 3+¥} = 4,

a(v 3) = min {7, 3+¥} = 7,

a(v 5) = min {¥, 3+3} = 6,

a(v 6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v 2 и ребро {v 1 , v 2 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 2 .

a(v 3) = min {7, 4+3} = 7,

a(v 5) = min {6, 4+2} = 6,

a(v 6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v 5 и ребро {v 4 , v 5 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 5 .

a(v 3) = min {7, 6+¥} = 7,

a(v 6) = min {¥, 6+2} = 8.

Окрашиваем вершину v 3 и ребро {v 1 , v 3 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 3 .

a(v 6) = min {8, 7+2} = 8.

Окрашиваем вершину v 6 и ребро {v 5 , v 6 }.

Так как вершина v 6 окрашена, то работу прекращаем. Получили минимальный маршрут v 1 v 4 v 5 v 6 , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v 1 и v 6 минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v 4 , v 5 } ребро {v 2 , v 5 }, тогда бы получили другой маршрут той же длины.

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

Граф без циклов называется лесом.

Дерево – это связный ациклический граф.

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

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

Радиус графа – минимальный эксцентриситет вершин, а диаметр графа – максимальный эксцентриситет вершин.

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

Периферийные вершины имеют эксцентриситет, равный диаметру.

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

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

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

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

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

Решение. В данной задаче удобно использовать матрицу расстояний S . Элемент этой квадратной симметричной матрицы равен расстоянию между вершиной i и вершиной j . Для графа, показанного на рис. 12.1, матрица расстояний имеет следующий вид:

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица S симметрична). Получаем

Радиус графа r – минимальный эксцентриситет вершин. В данном случае r = 2. Такой эксцентриситет имеют вершины № 2, № 4 и № 5. Эти вершины образуют центр графа. Диаметр графа d – максимальный эксцентриситет вершин. В данном случае d = 3. Такой эксцентриситет имеют вершины № 1 и № 3, это периферия графа. В исследованном графе вершины оказались либо центральными, либо периферийными. В графах большего порядка существуют и другие вершины.

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

Теорема 12.4. Пусть – матрица смежности графа G без петель и , где . Тогда равно числу маршрутов длины k от вершины к вершине .

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

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

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

Будем заполнять матрицу расстояний, рассматривая степени матрицы смежности. Единицы матрицы смежности показывают пары вершин, расстояние между которыми равно единице (т.е. они соединены одним ребром).

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

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

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

следовательно, , и окончательно

Полученная матрица совпадает с матрицей расстояний S (12.2), найденной непосредственными вычислениями по рисунку.

1. Присваиваем p =1 (p − количество компонент связности), .

2. Включаем в множество вершин V p компоненты сильной связности D p вершины, соответствующие единицам первой строки матрицы S p . В качестве матрицы A (D p ) возьмем подматрицу матрицы A (D A V p .

3. Вычеркиваем из S p строки и столбцы, соответствующие вершинам из V p . Если не остается ни одной строки (и столбца), то p - количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как S p +1 , присваиваем p = p +1 и переходим к п. 2.

Пример

Выделим компоненты связности ориентированного графа, изображенного на рис. 1. В данной задаче количество вершин n = 5.

Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом

Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:

,
,

Следовательно,

Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:

Присваиваем p =1
и составляем множество вершин первой компоненты сильной связностиD 1: это те вершины, которым соответствуют единицы в первой строке матрицы S (D ). Таким образом, первая компонента сильной связности состоит из одной вершины
.

Вычеркиваем из матрицы S 1 (D ) строку и столбец, соответствующие вершине v 1 , чтобы получить матрицу S 2 (D ):

Присваиваем p =2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S 2 (D ), то есть
. Составляем матрицу смежности для компоненты сильной связности
исходного графаD − в ее качестве возьмем подматрицу матрицы A (D ), состоящую из элементов матрицы A , находящихся на пересечении строк и столбцов, соответствующих вершинам из V 2:

Вычеркиваем из матрицы S 2 (D ) строки и столбцы, соответствующие вершинам из V 2 ,чтобы получить матрицу S 3 (D ), которая состоит из одного элемента:

и присваиваем p =3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины
.

Таким образом, выделены 3 компоненты сильной связности ориентированного графа D :

Задание 2. Расстояния в ориентированном графе

С помощью алгоритма фронта волны найти расстояния в ориентированном графе D : диаметр, радиус и центры.

Пусть
ориентированный граф сn³2 вершинами и v ,w (v ¹w ) – заданные вершины из V .

Алгоритм поиска минимального пути из вв ориентированном графе

(алгоритм фронта волны ).

В противном случае продолжаем:

В противном случае мы нашли минимальный путь из в
и его длина равнаk . Последовательность вершин

есть этот минимальный путь. Работа завершается.

Замечания

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R (D )между его вершинами. Это квадратная матрица размерности
, элементы главной диагонали которой равны нулю (
,i =1,..,n ).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (
, если
). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i -тая и на пересечении с j -тым столбцом стоит единица (то есть
). Это значит, что из вершиныможно попасть в вершинуза один шаг. Рассматриваемj -тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент
. Тогда из вершиныв вершинуможно попасть за два шага. Таким образом, можно записать
. Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Примечание: В контрольной работе самый длинный путь найти при помощи алгоритма фронта волны.

Пример

Найдем расстояния в ориентированном графе D , изображенном на рис. 2. В данной задаче количество вершин n = 7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 7×7.

Матрица смежности:

Начинаем заполнять матрицу R (D ) минимальных расстояний: сначала ставим нули по главной диагонали и r ij =a ij , если a ij =1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать
. Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит,
,
. Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому
. В итоге получаем следующую матрицу:

Таким образом, диаметром исследуемого ориентированного графа будет
.

Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше
:r (v i ) − максимальное из расстояний, стоящих в i -той строке. Таким образом,

r (v 1)=3, r (v 2)=3, r (v 3)=5, r (v 4)=4, r (v 5)=2, r (v 6)=2, r (v 7)=3.

Значит, радиусом графа G будет

Соответственно, центрами графа G будут вершины v 5 и v 6 , так как величины их эксцентриситетов совпадают с величиной радиуса
.

Опишем теперь нахождение минимального пути из вершины v 3 в вершину v 6 по алгоритму фронта волны. Обозначим вершину v 3 как V 0 , а вершину v 6 - как W (см. рис. 3). Множество вершин, принадлежащих образу V 0 , состоит из одного элемента - это вершина v 4 , которую, согласно алгоритму, обозначаем как V 1: FW 1 (v 3)={v 4 }. Поскольку искомая вершина не принадлежит фронту волны первого уровня
, продолжаем работу алгоритма. Строим фронт волны второго уровня- это множество вершин, принадлежащих образу вершины V 1: FW 2 (v 3)={v 7 }, обозначаем v 7 ≡V 2 . В образ вершины V 2 входят две вершины - v 5 и v 4 , но, так как v 4 уже была помечена как V 0 , то фронт волны третьего уровня состоит из одного элемента: FW 3 (v 3)={v 5 }, v 5 ≡V 3 . Из непомеченных вершин в образ вершины V 3 входят v 1 и v 2 , соответственно, FW 4 (v 3)={v 1 , v 2 }, v 1 ≡V 4 , v 2 ≡V 4 . Теперь помечены все вершины, кроме v 6 , которая входит в образ вершины
, то естьFW 5 (v 3)={v 6 ≡W }, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины v 3 в вершину v 6 выглядит так: v 3 v 4 v 7 v 5 v 1 v 6 .

Периферийные вершины имеют эксцентриситет, равный диаметру.

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

Теорема 12.1. В связном графе диаметр не больше ранга его матрицы смежности.

Теорема 12.2. (Жордана) Каждое дерево имеет центр, состоящий из одной или двух смежных вершин.

Пример 12.5. Найти радиус, диаметр и центр графа, изображенного на рис. 12.1.

. (12.2)

№

Пример 12.6. Найти матрицу расстояний графа, изображенного на рис. 12.1, алгебраическим методом.

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

Диагональные элементы матрицы расстояний – нули. Умножаем матрицу смежности на себя:

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

Для этого напомним правила умножения матриц. Пусть даны произвольные матрицы с числовыми элементами: матрица $A$ размерности $n\times m$ с элементами $a_{ik}$ и матрица $B$ размерности $m\times q$ с элементами $b_{kj}$. Матрица $C$ размерности $n\times q$ называется произведением матрицы $A$ на $B$ (порядок важен), если её элементы $c_{ij}$ определяются следующим образом: $c_{ij} = \sum\limits_{k = 1}^m {a_{ik} b_{kj}}$. Произведение матриц записывается обычным образом $AB=C$. Как видим, произведение матриц требует согласованности размеров первого и второго сомножителей (число столбцов первой матрицы-сомножителя равно числу строк второй матрицы-сомножителя). Это требование отпадает, если рассматривать квадратные матрицы одного порядка и, следовательно, можно рассматривать произвольные степени квадратной матрицы. Это одно из преимуществ квадратных матриц перед прямоугольными. Другое преимущество состоит в том, что мы можем дать графовую интерпретацию элементам степеней матрицы смежности.

Пусть матрица смежности $A$ имеет вид: $A = \left({{\begin{array}{*c} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & {...} & {a_{2n} } \\ {...} & {...} & {...} & {...} \\ {a_{n1} } & {a_{n2} } & {...} & {a_{nn} } \\ \end{array} }} \right)$, а её $k$-ая степень — $A^k = \left({{\begin{array}{*c} {a_{11}^{(k)} } & {a_{12}^{(k)} } & {...} & {a_{1n}^{(k)} } \\ {a_{21}^{(k)} } & {a_{22}^{(k)} } & {...} & {a_{2n}^{(k)} } \\ {...} & {...} & {...} & {...} \\ {a_{n1}^{(k)} } & {a_{n2}^{(k)} } & {...} & {a_{nn}^{(k)} } \\ \end{array} }} \right)$, где $k = 2,3,...$ Очевидно, что $A^k$, как и матрица $A$ будет симметричной матрицей.

Пусть $k=2$. Тогда $a_{ij}^{(2)} = \sum\limits_{k = 1}^n {a_{il} a_{lj}}$ ($i,j = 1,2,...,n$), и каждое слагаемое $a_{il} a_{lj}$ равно либо $0$, либо $1$. Случай, когда $a_{il} a_{lj} = 1$ означает, что в графе существуют два ребра: ребро $\{i,l\}$ (поскольку $a_{il} = 1)$ и ребро $\{l,j\}$ (поскольку $a_{lj} = 1$) и, следовательно, путь $\{{ \{i,l\}, \{l,j\} }\}$ из $i$-ой вершины в $j$-ую длиной два (путь из двух ребер). Здесь речь идет именно о пути, а не цепи, поскольку указано направление — из из $i$-ой вершины в $j$-ую. Таким образом, $a_{ij}^{(2)}$ дает нам количество всех путей на графе (в геометрической интерпретации графа) длины 2, ведущих из $i$-ой вершины в $j$-ую.

Если $k=3$, то $A^3 = A^2A = AA^2 = AAA$ и $a_{ij}^{(3)} = \sum\limits_{l_1 = 1}^n {a_{il_1 } } a_{l_1 j}^{(2)} = $ $\sum\limits_{l_1 = 1}^n {a_{il_1 } } \left({\sum\limits_{l_2 = 1}^n {a_{l_1 l_2 } a_{l_2 j} } } \right) =$ $\sum\limits_{l_1 = 1}^n {\sum\limits_{l_2 = 1}^n {a_{il_1 } } } a_{l_1 l_2 } a_{l_2 j} = \sum\limits_{l_1 ,l_2 = 1}^n {a_{il_1 } a_{l_1 l_2 } a_{l_2 j} }$.

Слагаемое $a_{il_1 } a_{l_1 l_2 } a_{l_2 j} $ в случае если оно равно 1, определяет путь длины 3 идущий из $i$-ой вершины в $j$-ую и проходящий через вершины $l_1$ и $l_2$. Тогда $a_{ij}^{(3)}$ дает нам количество путей длины 3, соединяющих $i$-ую и $j$-ую вершины. В общем случае $a_{ij}^{(k)}$ задает количество путей длины $k$, соединяющих $i$-ую и $j$-ую вершины. При этом $a_{ij}^{(k)} = \sum\limits_{l_1 ,l_2 ,...,l_{k - 1} = 1}^n {a_{il_1 } a_{l_1 l_2 } ...} a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j}$.

Ясно, что величина $a_{ii}^{(k)} $ дает нам количество замкнутых путей длины $k$, начинающихся и оканчивающихся в вершине $i$. Так, путь длины 2 — $a_{il} a_{li}$, означает путь, проходящий по ребру $\{ i,l \}$ из вершины $i$ в вершину $l$ и обратно. Поэтому $a_{ii}^{(2)} = s_i$, т.е. диагональные элементы матрицы $A^2$ равны степеням соответствующих вершин.

Рассмотрим теперь наряду с матрицей $A$ матрицу $\dot {A}$, которая отличается от матрицы $A$ только тем, что у неё элементы (числа 0 или 1) рассматриваются как элементы булевой алгебры. Поэтому действия с такими матрицами будут проводиться по правилам булевой алгебры. Поскольку действия сложения и умножения матриц с булевыми элементами сводится к действиям сложения и умножения элементов этих матриц по правилам булевой арифметики, то, надеемся, что это не приведет к затруднениям. Матрицу с булевыми элементами будем называть булевой матрицей. Очевидно, что операции сложения и умножения булевых матриц замкнуты на множестве булевых матриц, т.е. результат этих операций будет снова булевой матрицей.

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

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

Проинтерпретируем теперь вторую степень булевой матрицы смежности $\dot {A}^2$ с элементами $\dot {a}_{ij}^{(2)} = \sum\limits_{l = 1}^n {\dot {a}_{il} \dot {a}_{lj} }$. Ясно, что $\dot {a}_{ij}^{(2)} = 1$, если хотя бы одно слагаемое $\dot {a}_{il} \dot {a}_{lj} $ равно 1 и $\dot {a}_{ij}^{(2)} = 0$, если все слагаемые равны 0. Если матрица $\dot {A}$ является матрицей смежности некоторого графа, т.е. является симметричной (0,1)-матрицей с нулевой главной диагональю, то матрица $\dot {A}^2$, вообще говоря, не является матрицей смежности графа в принятом нами смысле, поскольку у неё все диагональные элементы равны 1 (если у графа нет изолированных вершин). Чтобы и на такие матрицы можно было смотреть как на матрицы смежности, мы должны при рассмотрении связей между вершинами некоторой связанной системы, определяющих эту систему как граф, допустить связь некоторых вершин самих с собой. «Ребро», определяющее связь некоторой вершины самой с собой называется петлей . Мы дальше, по-прежнему, под словом граф будем понимать граф без петель, а про граф с петлями, если это не будет ясно из контекста, так и будем говорить — граф с петлями.

Рассмотрим сумму $\dot {A}^{} = \dot {A} + \dot {A}^2$. Матрица $\dot {A}^{}$ задает нам граф, полученный из исходного «насыщением» его дополнительными связями, соответствующими путям длины 2. То есть в новом графе вершины $i$ и $j$ смежные, если они смежные в исходном графе или эти вершины связаны каким-нибудь путем длины 2, и вершины $i$ и $j$ несмежные, если они несмежные в исходном графе и не существует никакого пути длины 2, соединяющего эти вершины.

Аналогично определяется $\dot {A}^{} = \dot {A} + \dot {A}^2 + \dot {A}^3$. То есть в графе, заданном матрицей $\dot {A}^{}$ вершины $i$ и $j$ смежные, если они смежные в графе $\dot {A}^{}$ или эти вершины связаны каким-нибудь путем длины 3 в исходном графе, и вершины $i$ и $j$ несмежные, если они несмежные в графе $\dot {A}^{}$ и не существует никакого пути длины 3, связывающих эти вершины в исходном графе. И так далее.

В общем случае $\dot {A}^{[k]} = \sum\limits_{i = 1}^k {\dot {A}^i} $. Нетрудно видеть, что все $\dot {A}^{[k]}$ при $k \ge n - 1$, где $n$ — порядок матрицы $\dot {A}$, равны между собой. Действительно, если вершины $i$ и $j$ связны, то существует путь (цепь) связывающий эти вершины, а, следовательно, существует простой путь (простая цепь) связывающий эти вершины. Максимальная возможная простая цепь в $n$-вершинном графе имеет длину $n-1$ (простая цепь, связывающая все различные вершины графа). Поэтому, если в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 1, то на этом же месте в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ будет также стоять 1, поскольку матрица $\dot {A}^{}$ входит в качестве булева слагаемого в определение матрицы $\dot {A}^{[k]}$. Если же в матрице $\dot {A}^{}$ на месте $(i,j)$ стоит 0, то это значит, что в графе не существует никакой простой цепи, соединяющей $i$-ую и $j$-ую вершины, а, следовательно, не существует вообще никакой цепи связывающей эти вершины. Значит, в рассматриваемом случае и в матрице $\dot {A}^{[k]}$ при $k \ge n - 1$ на месте ($i$,$j)$ будет стоять 0. Что и доказывает наше утверждение о равенстве всех матриц $\dot {A}^{[k]}$ при $k \ge n - 1$ матрице $\dot {A}^{}$ и, следовательно, между собой.

Матрицу $\dot {A}^{}$ называют матрицей транзитивного замыкания матрицы $\dot {A}$, а также матрицей смежности транзитивного замыкания графа, заданного матрицей $\dot {A}$. Достаточно очевидно, что матрицей транзитивного замыкания связного графа будет матрица смежности полного графа, т.е. квадратная матрица, состоящая из одних единиц. Это наблюдение дает нам и метод определения связности графа: граф связный тогда и только тогда, когда матрица транзитивного замыкания его матрицы смежности будет состоять из одних единиц (будет матрицей полного графа) .

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

Покажем теперь, как процедура транзитивного замыкания позволяет построить так называемую «матрицу расстояний». Для этого определим расстояние между вершинами $i$ и $j$. Если вершины $i$ и $j$ связные, то расстоянием между ними назовем длину минимального (по числу обхода ребер) простого пути, связывающего эти вершины; если вершины $i$ и $j$ несвязные, то положим расстояние равным нулю (ноль как отрицание какого-либо пути связывающего эти вершины). При таком определении расстояния расстояние между вершиной и ею же самой равно 2 (длина пути по ребру и обратно). Если же при вершине имеется петля, то расстояние между вершиной и ею же самой равно 1.

Для построения матрицы расстояний для $n$-вершинного графа с матрицей смежности $A$, которая указывала бы расстояние между любыми двумя вершинами, введем в рассмотрение матрицы $A^{\{k\}} = A^{[k]} - A^{}$, где $k = 2,3,...,n - 1$ и $A^{\{1\}} = A^{} = A$. Отсутствие точек над обозначением матриц указывает, что мы рассматриваем матрицы $A^{[k]}$ ($k = 1,2,...,n - 1)$ как числовые (0,1)-матрицы, естественным образом получаемые из матриц $\dot {A}^{[k]}$ (булевы элементы 0 и 1 мы теперь рассматриваем как числа 0 и 1). Из способа построения матриц $A^{[k]}$ следует, что $A^{[k]} \ge A^{}$ ($k = 2,3,...,n - 1$) и, следовательно, $A^{\{k\}}$ ($k = 1,2,...,n - 1$) являются (0,1)-матрицами. Причем матрица $A^{\{2\}}$ содержит 1 только на тех местах, где определяемые этим местом (номер строки и номер столбца) вершины соединены некоторым путем длины два и не соединены меньшим путем. Аналогично, $A^{\{3\}}$ содержит 1 только на тех местах, где определяемые этим местом вершины соединены путем длины три и не соединены никаким путем меньшей длины, и т.д. Таким образом, матрица $D = \sum\limits_{k = 1}^{n - 1} {k \cdot A^{\{k\}}}$ и будет искомой матрицей расстояний. Элемент $d_{ij}$ этой матрицы и будет равен расстоянию между вершинами $i$ и $j$. Расстояние между вершинами $u$ и $v$ будем также обозначать как $d(u,v)$.

Замечание. Конкретное произведение-слагаемое $a_{il_1 } a_{l_1 l_2 } ...a_{l_{k - 2} l_{k - 1} } a_{l_{k - 1} j} = 1$ элемента $a_{ij}^{(k)}$ $k$-ой степени матрицы смежности $A^k$ задает конкретный $(i,j)$-путь $i\{i,l_1\}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ из $i$-ой вершины в $j$-ую. Последовательность смежных вершин и соединяющих их ребер $i\{i,l_1 \}l_1 \{l_1 ,l_2 \}l_2 ...l_{k - 2} \{l_{k - 2} ,l_{k - 1} \}l_{k - 1} \{l_{k - 1} ,j\}j$ называют ещё $(i,j)$-маршрутом . Маршрут отличается от цепи, состоящей только из различных смежных ребер, ещё тем, что в маршруте допускаются равные ребра. Простой маршрут состоит из различных смежных вершин и ребер, т.е. практически совпадает с простой цепью.

Достаточно очевидно, что элемент $d_{ij} $ матрицы расстояний определяет длину минимальной цепи соединяющей $i$-ую вершину с $j$-ой.

Рассмотрим примеры графов, заданных рисунками 1 и 2, их матриц смежности и их матриц расстояний.

Рис.1 (Граф $\Gamma _1$, матрица смежности $A_1$, матрица расстояний $D_1$).
$A_1 = \left({{\begin{array}{*c} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} }} \right), $
$D_1 = \left({{\begin{array}{*c} 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end{array} }} \right) $

Рис. 2 (Граф $\Gamma _2$, матрица смежности $A_2$, матрица расстояний $D_2$).
$A_2 = \left({{\begin{array}{*c} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array} }} \right)$,
$D_2 = \left({{\begin{array}{*c} 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & 3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \\ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end{array} }} \right). $

По матрицам $D_1$ и $D_2$ легко определяются диаметры $d_1$ графа $\Gamma _1$ и $d_2$ графа $\Gamma _2$, как максимальные значения элементов этих матриц. Так $d_1 = 3$, а $d_2 = 6$.

Кроме матрицы расстояний теория графов рассматривает и другие матрицы, элементы которых определяются через длину пути. Таковой, например, является матрица обходов . В матрице обходов $(i,j)$-й элемент равен длине наиболее длинного пути (наиболее длинной цепи) из $i$-ой вершины в $j$-ую, а если таких путей нет вообще, то в соответствии с определением расстояния $(i,j)$-ый элемент матрицы обходов полагается равным нулю.

О методах определения минимальной и максимальной цепей с использованием матрицы расстояний, соединяющих $i$-ую и $j$-ую вершины в графе, сделаем замечание в конце параграфа.

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

Эксцентриситет $e(v)$ вершины $v$ в связном графе $\Gamma$ определяется как max $d(u,v)$ по всем вершинам $u$ в $\Gamma$. Радиусом $r(\Gamma)$ называется наименьший из эксцентриситетов вершин. Заметим, что наибольший из эксцентриситетов равен диаметру графа. Вершина $v$ называется центральной вершиной графа $\Gamma$, если $e(v) = r(\Gamma)$; центр графа $\Gamma$ — множество всех центральных вершин.

Так для графа $\Gamma _1$ с рис.1, эксцентриситет вершины 13 будет равен 2 ($e(13) = 2$). Такие же эксцентриситеты будут иметь вершины 3, 5 и 10 ($e(3) = e(5) = e(10) = 2$). Эксцентриситет равный 2 будет наименьшим для графа $\Gamma _1$, т.е. $r(\Gamma _1) = 2$. Центр графа $\Gamma _1$ будет состоять из вершин 3, 5, 10 и 13. Наибольший эксцентриситет будет равен 3 и будет равен, как отмечалось выше, диаметру графа $\Gamma _1$.

Для графа $\Gamma _2$ с рис. 2 наименьший эксцентриситет будет иметь единственная вершина 4 ($e(4) = r(\Gamma _2) = 3$). Следовательно, центр графа $\Gamma _2$ состоит из одной вершины 4. Диаметр графа $\Gamma _2$, как отмечалось выше, равен 6.

Граф $\Gamma _2$ является деревом, а структуру центра любого дерева описывает приводимая ниже теорема.

Теорема Жордана—Сильвестра. Каждое дерево имеет центр, состоящий или из одной вершины или двух смежных вершин.

Доказательство. Обозначим через $K_1$ граф, состоящий из одной изолированной вершины, а через $K_2$ — граф — из двух вершин соединенных ребром. По определению положим $e(K_1) = r(K_1) = 0$. Тогда утверждение теоремы будет выполнено для $K_1$ и $K_2$. Покажем, что у любого дерева $T$ те же центральные вершины, что и у дерева ${T}"$, полученного из $T$ удалением всех его висячих вершин. Ясно, что расстояние от данной вершины $u$ до любой другой вершины $v$ может достигать наибольшего значения только тогда, когда $v$ — висячая вершина.

Таким образом, эксцентриситет каждой вершины дерева ${T}"$ точно на единицу меньше эксцентриситета этой же вершины в $T$. Отсюда вытекает, что вершины дерева $T$, имеющие наименьший эксцентриситет в $T$, совпадают с вершинами, имеющими наименьший эксцентриситет в ${T}"$, т.е. центры деревьев $T$ и ${T}"$ совпадают. Если процесс удаления висячих вершин продолжить, то мы получим последовательность деревьев с тем же центром, что и у $T$. В силу конечности $T$ мы обязательно придем или к $K_1$, или к $K_2$. В любом случае все вершины дерева полученного таким способом, образуют центр дерева, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин. Доказательство закончено.

Покажем теперь, как с помощью матрицы расстояний можно определить, например, минимальную цепь соединяющую вершину 4 с вершиной 8 на графе $\Gamma _1$. В матрице $D_1$ элемент $d_{48} = 3$. Возьмем 8-ой столбец матрицы $D_1$ и найдем в столбце все элементы этого столбца равные 1. По крайней мере, один такой элемент найдется в силу связности графа $D_1$. На самом деле таких единиц в 8-ом столбце будет три, и расположены они в 5-ой, 6-ой и 7-ой строках. Возьмем теперь 4-ую строку и рассмотрим в ней элементы, расположенные в 5-ом, 6-ом и 7-ом столбцах. Эти элементы будут 2, 3 и 3 соответственно. Только элемент, расположенный в 5-ом столбце равен 2 и вместе с 1, расположенной на месте (5,8), дает сумму 3. Значит, вершина 5 входит в цепь $\{ \{4,?\}, \{?,5\}, \{5,8\} \}$. Возьмем теперь 5-ый столбец матрицы и рассмотрим 1 этого столбца. Это будут элементы расположенные в 3-ей, 6-й, 7-ой, 8-ой, 10-ой и 13-ой строках. Вновь возвращаемся к 4-ой строке и видим, что только на пересечении третьего столбца и 4-й строки стоит 1, что в сочетании с 1 на месте (3,5) дает в сумме 2. Следовательно, искомая цепь будет $\{ \{4,3\}, \{3,5\}, \{5,8\} \}$. Посмотрев теперь на рисунок 1, убеждаемся в справедливости найденного решения.

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