Матричные представления сетей

Каждая сеть может быть однозначно задана в матричном представлении. Основными используемыми для этого матричными величинами являются матрицы обобщенных стоимостей C_n,n, смежности X_n,n и инциденции Z_n,k. Здесь индексы являются размерностью матриц, n - число узлов сети, k - число ее дуг.

Элементом c_ij матрицы стоимостей C_n,n является обобщенная стоимость дуги [i, j] A. Для неориентированной сети эта матрица симметрична. Значение элементов c_ij с i и j, для которых в графе G не существует дуг [ i, j ], определяется конкретной задачей и обычно полагается равным бесконечности ().

Элемент x_ij матрицы смежности X_n,n определяется следующим образом:

Xi j =

1, если [ i, j ] A,   0 в другом случае.

Свойства матрицы смежности для ориентированной сети:

1) каждый нулевой столбец соответствует источнику;

2) каждая нулевая строка соответствует стоку;

3) ненулевой элемент главной диагонали соответствует петле;

4) матрица не симметрична.

Для неориентированной сети эта матрица симметрична, для нее выполняется свойство 3) и каждому узлу сети, не связанному со всеми остальными ее узлами, соответствуют нулевые строка и столбец матрицы смежности.

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

Zij =

1, если узел i - начало дуги j, -1, если узел i - конец дуги j, 0 в остальных случаях.

для ориентированной сети

Zij =

1, если узел i принадлежит дуге j,   0 в противном случае.

для неориентированной сети

Матрицы обобщенных стоимостей C_n,n, смежности X_n,n и инциденции Z_n,k для сети (рис. 6) имеют следующий вид:

C = ; X = ;

Z = ,

для Z: [1, 2] = 1; (1, 3) = 2; [2, 2] = 3;

(2, 3) = 4; (2, 4) = 5; [3, 4] = 6.

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

Теорема. Для определения маршрутов, состоящих из k ребер (дуг), необходимо возвести в k -ю степень матрицу смежности вершин Х. Тогда элемент х_ij ^{[ k ]} матрицы X^k=X ^{[ k ]} даст количество маршрутов длины k (состоящих из k ребер) из вершины i в вершину j.

Для построения матрицы расстояний для n -вершинного графа с матрицей смежности X, которая указывала бы расстояние между любыми двумя вершинами, введем в рассмотрение матрицы X ^{{ k }}= X ^{[ k ]}− X ^{[ k −1]}, где k =2,3,..., n −1 и X ^{1}= X ^[1]= X. Из способа построения матриц X ^{[ k ]} следует, что X ^{[ k ]}≥ X ^{[ k −1]} (k =2,3,..., n −1) и, следовательно, X ^{{ k }} (k =1,2,..., n −1) являются (0,1)-матрицами. Причем матрица X ^{2} содержит 1 только на тех местах, где определяемые этим местом (номер строки и номер столбца) вершины соединены некоторым путем длины два и не соединены меньшим путем. Аналогично, X ^{3} содержит 1 только на тех местах, где определяемые этим местом вершины соединены путем длины три и не соединены никаким путем меньшей длины, и т.д. Таким образом, матрица D =∑ _{k =1} ^{n −1} k ⋅ X ^{{ k }} и будет искомой матрицей расстояний. Элемент d_ij этой матрицы и будет равен расстоянию между вершинами i и j. Расстояние между вершинами u и v будем также обозначать как d (u, v). По матрице D определяются диаметр d графа G, как максимальное значение элементов этой матрицы.

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

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

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

Доказательство. Обозначим через 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. В любом случае все вершины дерева полученного таким способом, образуют центр дерева, который, таким образом, состоит или из единственной вершины, или из двух смежных вершин. Доказательство закончено.

Укладка графа. Плоские и планарные графы.

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

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

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

Пример плоского графа приведен на рис. слева. Изоморфный ему полный граф К ₄ (на рис. справа), укладываемый на плоскости, имеет два пересекающихся ребра, поэтому граф К ₄ не является плоским - он только планарный.