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

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w . Это расстояние удовлетворяет аксиомам метрики:

1) d(v, w) 0, причем d(v, w) = 0 тогда и только тогда, когда v= w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

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

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

Пример 82.

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Решение.

Чтобы определить центры, радиус, диаметр графа G , найдем матрицу D(G) расстояний между вершинами графа, элементами d ij которой будут расстояния между вершинами v i и v j . Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5 . В результате получаем: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3. Минимальное из полученных чисел является радиусом графа G , максимальное – диаметром графа G . Значит, R(G) = 2 и D(G) = 3 , центрами являются вершины v 2 , v 3 , v 4 .

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

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

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

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

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

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

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

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

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

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

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

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

. (12.2)

Вычислим эксцентриситет каждой вершины. Эту величину можно определить как максимальный элемент соответствующего столбца матрицы расстояний (или строки – поскольку матрица 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. Будем умножать матрицу смежности саму на себя до тех пор, пока в матрице не появится ненулевой элемент . Тогда соответствующий элемент матрицы расстояний равен степени матрицы смежности: . На следующем шаге получаем

В прошлом параграфе мы подчеркнули, что введенная там матрица смежности $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, убеждаемся в справедливости найденного решения.

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

Пусть 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. Задачи на деревьях

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

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

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

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

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

2. тогда и только тогда, когда ;

3. ;

4. справедливо неравенство треугольника:

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

Диаметром графа называют число , равное расстоянию между наиболее удаленными друг от друга вершинами графа:

.

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

Минимальный из эксцентриситетов вершин связного графа называют его радиусом и обозначают :

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

Для иллюстрации обратимся к графу на рис. 4.29. Здесь

Поэтому

Вершина 2 является центром графа, а все остальные его вершины - периферийные. Цепь 1, 2, 3 - одна из диаметральных цепей.

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

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

Обходы графов

Уже отмечалось, что начало теории графов связывают с задачей о кенигсбергских мостах. Эта знаменитая в свое время задача состоит в следующем. Семь мостов города Кенигсберга (ныне Калининграда) были расположены на реке Прегель так, как изображено на рис. 4.30. Задача состоит в том, чтобы, выйдя из дома, вернуться обратно, пройдя только один раз по каждому мосту.

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

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

Например, граф, изображенный на рис. 4.31, является эйлеровым, поскольку он содержит эйлеров цикл 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер.

Теорема 4.7. (Л. Эйлер, 1736 г.) Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Цепь называется эйлеровой , если она содержит все ребра графа.

Теорема 4.8 (Л. Эйлер, 1736 г.) Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2.

Несмотря на «похожесть» в определениях для эйлеровых и гамильтоновых циклов, соответствующие теории, устанавливающие критерии существования и алгоритмы поиска таких циклов, имеют мало общего. Терема Эйлера (теорема 4.7) позволяет легко установить, является ли граф эйлеровым. Разработаны алгоритмы, позволяющие достаточно просто найти эйлеровы циклы эйлерова графа. Что касается гамильтоновых графов, то здесь положение дел существенно иное. Ответить на вопрос, является ли некий граф гамильтоновым, как правило, очень трудно. Общего критерия, подобного критерию Эйлера, здесь нет. Но, как оказалось, среди множества всех графов эйлеровых графов ничтожно мало, а вот гамильтоновых графов достаточно много.