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

Рассмотрим связный граф G=(S,U) Пусть x₁ и x₂ – две его вершины. Длина кратчайшего (x₁, x₂) – маршрута называется расстоянием между вершинами x₁ и x₂ и обозначается d(x₁, x₂).

Свойства расстояния между вершинами.

1. Расстояние между вершинами является длиной простой цепи.

2. d(x_i, x_i)=0.

Для вершины x величина

(1)

называется эксцентриситетом вершины x. Максимальный из всех эксцентриситетов называется диаметром графа G и обозначается d(G),т.е.

(2)

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через r(G).

(3)

Вершина x называется периферийной, если её эксцентриситет равен диаметру графа.

Простая цепь, расстояние между концами которой равно d(G), называется диаметральной цепью.

Вершина x называется центральной, если e(x)=r(G). Множество всех центральных вершин графа называется его центром.

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

1.6. Упорядочивание дуг и вершин орграфа

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

1. вершины первой группы не имеют предшествующих вершин, а вершины последней группы последующих;

2. вершины любой другой группы не имеют предшествующих в следующей группе;

3. вершины одной и той же группы дугами не соединяются.

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

Алгоритм Фалкерсона.

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

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

Аналогичным образом упорядочиваются дуги орграфа.

1. Находятся дуги, не имеющие предшествующих дуг.

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

П ример.

Рис. 16

1. Вершина B не содержит входящих дуг, отнесём её к первой группе.

2. Вычеркнем все дуги, исходящие из B, получим граф

Рис. 17

В нём опять находим вершину, в которую не заходит ни одна дуга. Эта вершина D. Вычёркиваем дуги, исходящие из D. Появится ещё одна вершина E, в которую не заходит ни одна дуга.

Рис. 18

После вычёркивания дуг EC и EA получим вершину A, которая входит, таким образом, в четвёртую группу, а вершина C - в пятую.

Изоморфный граф с упорядоченными вершинами:

Рис. 19

Упорядочим теперь дуги исходного графа.

Рис. 20

Штриховыми линиями показаны связи между дугами, существующие в исходном графе.

Матричный способ упорядочивания вершин орграфа.

Составляют матрицу смежности вершин P. Вычисляют компоненты вектора , представляющие собой полустепени захода вершин графа. Для орграфа различают полустепень захода P⁺(х_i) (количество дуг заходящих в х_i) и полустепень выхода P^-(х_i) (количество дуг исходящих из х_i). Первую группу составляют вершины, полустепени заходов которых равны 0. Исключают из рассмотрения эти вершины и дуги, из них исходящие, вычеркнув соответствующие строки матрицы P. Затем вычисляют компоненты вектора , представляющий собой полустепени захода оставшихся вершин графа. Вершины с ненулевыми компонентами образуют вторую группу. Так продолжают до вектора, у которого будет часть только нулевых компонент, а остальные вычеркнуты.

Для нашего примера:

Таблица 2.

	A	B	C	D	E
	2	0	4	1	2
	1	-	3	0	1
	1	-	2	-	0
	0	-	1	-	-
	-	-	0	-	-
Группа	4	1	5	2	3

1.7. Выявление маршрутов с заданным количеством рёбер.

Теорема. Для определения маршрутов, состоящих из k рёбер, необходимо возвести в k-ую степень матрицу смежности вершин. Тогда элемент даст количество маршрутов длины k из вершины x_i в вершину x_j.

Следствие 1. В графе G мощности n тогда и только тогда, когда существует (x_i, x_j) - маршрут (x_i не равно x_j), когда (i,j) элемент матрицы P+P²+…+Pⁿ не равен 0.

Следствие 2. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину x_i когда (i,j) элемент матрицы P+P²+…+Pⁿ не равен 0.

Пример. Рассмотрим неориентированный граф:

Рис. 21

;

Рассмотрим первую строку. Элемент . Это значит, что существует три маршрута из А в А длиной в 2 ребра. Действительно, это маршруты Au₁Bu₁A, Au₂Cu₂A, Au₃Du₃A. Из A в B существует два маршрута Au₂Cu₅A, Au₃Du₄A.

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

Действительно, для данного маршрута имеем:

Пример 2.

Рис. 22

Рассмотрим элемент после возведения матрицы

смежности вершин в квадрат. т.е. из вершины В в вершину В есть 2 маршрута длиной 2 дуги. Это маршруты Вu₃Cu₄B и Bu₂Au₁B. После возведения матрицы в куб сохраняется та же картина. Например, ; это значит, что есть 2 маршрута длиной 3 дуги из вершины А в вершину В. Это маршруты Аu₁Вu₂Аu₁B и Аu₁Вu₃Сu₄В. Для получения цепей (маршрутов, в которых каждое ребро встречается один раз) нужно в модифицированной матрице Р³ вычеркнуть те слагаемые, в которых какой–либо сомножитель встречается более одного раза. Card G=4=n.

Рассмотрим элементы матрицы А. Например, а₂₄=2≠0. Это значит, что в исходном графе существуют маршруты из вершины В в вершину D. Это маршруты: ВCD, BACD, BCBACD. Аналогично, b₂₂ = 7 ≠ 0. Т.о., существуют циклы, проходящие через вершину В, например, циклы ВАСВ, ВАВ и ВСВ. Т.к.

b₄₄ = 0, то через вершину D не проходит ни один цикл.