Матрицы в теории графов

    Таким образом, существует взаимно однозначное соответствие между помеченными графами с p вершинами и симметрическими бинарными (p_˟p)-матрицами с нулями на диагонали. На рисунке 1.2 показаны помеченный граф G и его матрица смежностей А. Легко заметить, что суммы элементов матрицы А по строкам равны степеням вершин графа G.

       

 
 
 
 
 
 
 
 
 

      Рис. 1. 2. Помеченный граф и его матрица смежностей. 

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

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

          для неориентированного графа:

      
 для ориентированного графа:

 
 
 
 
 
 

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

    Доказательство: Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их смежность: вершины x₁ и x₂ тогда и только тогда смежны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) смежны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

     Пример 1. Доказать, что графы изоморфны (рис. 1.3).

      

                                  Рис. 1.3

     Решение: воспользуемся теоремой и проанализируем матрицы смежности данных графов.  

    Р₁= Р₂= Р₃= 
 
 

    Видно, что Р₂= Р₃. Если одновременно переставить в Р₂ вторую и пятую строки и второй и пятый столбец, то получится матрица Р₁. Следовательно, по теореме все три указанных графа изоморфны. 

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

    В Примере 1   rankР₁ = 2,  следовательно, rankG₁ = 2.

    Аналогично  можно определить и матрицу смежности  дуг. Это так же квадратная матрица m_˟m порядка, где m – число дуг.

    Пример 2. Рассмотрим следующий граф (рис. 1.4):

      
 
 
 
 
 
 

                                        Рис. 1.4

    Элементы  q_ij матрицы смежности дуг равны единице, если дуга u_i непосредственно предшествует дуге u_j, и равны нулю в остальных случаях. Для неориентированного графа элемент qij равен единице, если u_i и u_j смежны, и нулю в остальных случаях.

      
 
 
 
 
 
 
 
 
 

    Утверждение: Для того, чтобы n-вершинный граф G с матрицей смежности A = A (G) имел хотя бы один контур, необходимо  и достаточно, чтобы матрица K = A² + A³ +…+Aⁿ имела ненулевые диагональные элементы.

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

    Достаточность: Пусть K = [k_ij] и для некоторого номера i выполняется k_ij>0. в этом случае для некоторого r из {2, …, n} справедливо a^(r)_ii>0, а следовательно найдётся путь в G из x_i в x_i. Но тогда в силу того, что в графе G из всякого цикла можно выделить простой цикл, в орграфе G найдётся простой контур.

    Необходимость: Пусть в графе G имеется некоторый контур.  Так как из всякого контура можно выделить простой контур, нетрудно увидеть, что длина простого контура не превышает числа вершин n. Но тогда в силу того,  что элемент матрицы ориентированного графа равен числу всех путей длины l, то для любой вершины x_i, принадлежащей некоторому простому контуру длины l, где 2 ≤ l ≤ n, элемент a^(l)_ii матрицы A^l отличен от нуля, а следовательно, и элемент k_ii матрицы К отличен от нуля.  

    Простой взвешенный граф так же может быть представлен своей матрицей весов Ω = (ω_ij), где ω_ij – вес ребра, соединяющего вершины x_i и x_j. Веса несуществующих рёбер полагают равными нулю или бесконечности в зависимости от приложений. Очевидно, что матрица весов является простым обобщением матрицы смежности вершин. 
 
 

 

1.  2.  3 Матрица инциденций 

    Другой  матрицей, связанной с графом G, в котором помечены и вершины и рёбра, является матрица инциденций B = |b_ij|. В этой (pxq)-матрице b_ij = 1, если v_i и x_j инцидентны, и b_ij = 0 а противном случае. Как и матрица смежностей, матрица инциденций определяет граф G с точностью до изоморфизма. На самом деле уже любые p-1 строки матрицы B определяют G, поскольку каждая строка равна сумме по модулю 2 всех остальных строк.

    Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-ый элемент равен 1, если вершина v_i инцидентна ребру х_j,и равен нулю, если v_i и х_j не инцидентны.  

    Для неориентированного графа элементы данной матрицы задаются следующим образом:

      
 
 

     Для ориентированного графа элементы матрицы задаются так:

     Строки  матрицы инциденций называют векторами инциденций графа G. Матрица инциденций также однозначно определяет структуру графа. Для матрицы инциденций справедлива теорема, аналогичная для матрицы смежности. 

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

    Доказательство:  Рассмотрим два графа G₁ и G₂, которые отличаются друг от друга лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, сохраняющая их инцидентность: вершины x₁ и x₂ тогда и только тогда инцидентны в G, когда их образы y₁ = s(x₁) и y₂ = s(x₂) инцидентны в G₁. Тогда, если P(G) = P и P(G₁) = P⁽¹⁾, то p_s(i)s(j)=p_ij, i, j = (1, n).

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

      Пример 3: Рассмотрим граф (Рис. 1.5) 
 
 
 
 
 
 

     Рис. 1.5 
 

     Его матрица инциденций имеет вид:

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. 2.  4 Матрицы связности и достижимости. Матрица контрдостижимости

 

     Определим матрицы связности и достижимости. Пусть P(G) – матрица смежности вершин графа G = (S_n, U), а B = E + P + P² + … + Pⁿ. Введём матрицу C = (cij), i,j = (1, n) по правилу:

     

     Матрица С называется матрицей связности, если G – неориентированный граф, и матрицей достижимости, если G – ориентированный. Это значит, что в графе G тогда и только тогда существует маршрут из вершины x_i в x_j, когда c_ij = 1.

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

     Матрица контрдостижимости L = (l_ij), i, j = (1, n), определяется следующим образом:

        
 
 

     Можно показать, что L = C^Т. Матрицы C и L используются для нахождения сильных компонент графа.

     Пусть F = C*L, где операция * означает поэлементное произведение матриц С и L: f_ij = c_ij l_ij. Элемент f_ij матрицы F равен единице тогда и только тогда, когда вершины x_i и x_j взаимно достижимы, т. е. x_i достижима из x_j, а x_j – из x_i. Таким образом, сильная компонента орграфа, содержащая вершину x_i, состоит из элементов x_j, для которых f_ij = 1.

      

      Пример 4: Матрицы достижимости С и контрдостижимости L для данного графа равны 
 
 
 
 
 

     Рис. 1.6

       
 

     С =  L =  

     

     По  матрице F легко определить состав вершин трёх подграфов, образующих сильно связанные компоненты исходного графа:

1. x_i;
2. x₂, x₃, x₄;
3. x₅, x₆.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. 3 Метрические характеристики графа

 

     Рассмотрим  связный граф G = (S, U), пусть x₁ и x₂ – две его вершины. Длина кратчайшего (x₁, x₂)-маршрута называется расстоянием между вершинами x₁ и x₂, обозначается через d(x₁ , x₂). Очевидно, что расстояние между вершинами является простой цепью и d(x₁ , x₂)=0. Для любой вершины x величина e(x) = max d(x, y) называется эксцентриситетом вершины x. Максимальный из всех эксцентриситетов называется диаметром графа и обозначается d(G), т. е. d(G) = max e(x) = max max d(x, y).

     Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через r(G): r(G) = min e(x) = min max d(x, y).

     Вершина x называется периферийной, если её эксцентриситет равен диаметру графа, т. е. e(x) = d(G). Простая цепь, расстояние между концами которой равно d(G), называется диаметральной цепью. 

     Теорема: Для любого связного графа G справедливо неравенство d(G) ≤ rankG.

     Доказательство: Пусть d(G) = d и x₁, x₂, …, x_d+1 – одна из диаметральных цепей графа G. Рассмотрим матрицу смежности вершин P(G) и выберем нумерацию вершин так, чтобы вершины x₁, x₂, …, x_d+1 имели номера 1, 2, … , d+1 соответственно. Так как цепь x₁, x₂, …, x_d+1 является подграфом G′ ᴄ G, то P(G) =( )представляет собой клеточную матрицу, в левом верхнем углу которой из-за выбранной нумерации вершин расположена матрица смежности подграфа G′. Этот подграф – простая цепь, т. е.