Матричный метод нахождения путей в графах

Нахождение множества вершин, входящих в путь

Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T⁺(x_i) – это множество вершин, в которые есть пути из вершины x_i, а T–(х_j) – множество вершин, из которых есть пути в x_j, то T⁺(x_i) T–(x_j)– множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от x_i к x_j. Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин x_i и x_j. Все остальные вершины графа называются несущественными или избыточными, поскольку их удаление не влияет на пути от x_i к x_j.

Рис. 4.2. Орграф

Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из вершины х₂ в вершину х₄, сводится к нахождению Т⁺(х₂) ={ х₂, х₃, х₄, х₅, х₆}, Т^-(х₄) ={ х₁, х₂, х₃, х₄, х₅}, и их пересечения T⁺(х₂) T^–(х₄) ={ х₂, х₃, х₄, х₅}.

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А² определяется по формуле

a⁽²⁾ _ik= ⁿ _j=1a_ija_jk

Слагаемое в формуле равно 1 тогда и только тогда, когда оба числа a_ij и a_jk равны 1, в противном случае оно равно 0. Поскольку из равенства a_ij = a_jk = 1следует существование пути длины 2 из вершины x_i в вершину х_k, проходящего через вершину x_j, то (i -й, k -й) элемент матрицы А² равен числу путей длины 2, идущих из x_i в х_k.

На таблице 4.1a представлена матрица смежности графа, изображенного на рис. 4.2. Результат возведения матрицы смежности в квадрат А² показан на таблице 4.1б.

Так "1", стоящая на пересечении второй строки и четвертого столбца, говорит о существовании одного пути длиной 2 из вершины х₂ к вершине х₄. Действительно, как видим в графе на рис. 4.2, существует такой путь: a₆, a₅. "2" в матрице A2 говорит о существовании двух путей длиной 2 от вершины х₃ к вершине х₆: a₈, a₄ и a₁0, a₃.

Аналогично для матрицы смежности, возведенной в третью степень A3 (таблица 4.1в), a ⁽³⁾ _ik равно числу путей длиной 3, идущих от x_i к х_k. Из четвертой строки матрицы A3 видно, что пути длиной 3 существуют: один из х₄ в х₄(a₉, a₈, a₅), один из х₄ в х₅(a₉, a₁₀, a₆) и два пути из х₄ в х₆(a₉, a₁₀, a₃ и a₉, a₈, a₄). Матрица A₄ показывает существование путей длиной 4 (таблица 4.1г).

Таким образом, если a ^р _ik является элементом матрицы A^р,то a ^р _ik равно числу путей (не обязательно орцепей или простых орцепей) длины р, идущих от x_i к х_k.

5. Лекция: Типы графов (нет)

Граф G = (X, A) называют полным, если для любой пары вершин х_i и х_j в X существует ребро (х_i, х_j) в неориентированном графе G=(X,A), т. е. для каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их (рис. 5.1,а).

Граф G =(X, A)называется симметрическим, если в множестве дуг A для любой дуги (х_i, х_j) существует также противоположно ориентированная дуга (х_j, х_i) (рис. 5.1,б).

Рис. 5.1. а – полный граф; б – симметрический граф; в – антисимметрический граф;

г – полный симметрический

Антисимметрическим называется такой граф, для которого справедливо следующее условие: если дуга (х_i, х_j) A, то во множестве A нет противоположно ориентированной дуги, т. е. (х_j, х_i) A (рис. 5.1,в). Очевидно, что в антисимметрическом графе нет петель.

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

Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения:

• граф G =(X, A), в котором любая пара вершин (х_i, х_j) соединена двунаправленными дугами, называется полным симметрическим (рис. 5.1,г);
• граф G =(X, A), имеющий для каждой пары вершин (х_i, х_j) только одну дугу, называется полным антисимметрическим или турниром.

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

Рис. 5.2. Граф типа “дерево”: а – неориентированное дерево,

б – ориентированное дерево

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

Граф G =(X, A), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис. 5.3).

Рис. 5.3. Планарный граф

На рис. 5.4 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

Рис. 5.4. Непланарные графы

Неориентированный граф G = (X, A)называют двудольным, если множество его вершин X может быть разбито на такие два подмножества X^а и X^b, что каждое ребро имеет один конец в X^а, а другой в X^b (рис. 5.5,а).

Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 5.5,б,в).

Двудольный граф G=(X^а X^b, A) называют полным, если для любых двух вершин х_i X^а и х_j X^b существует ребро (х_i,х_j) в G=(X,A) (рис. 5.5,г).

Рис. 5.5. Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф