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

П.3. Способы задания графов

В подавляющем большинстве случаев граф задаётся матрицей. Для расчётов на ЭВМ это единственный способ.

Наиболее часто граф задают с помощью матриц смежности и инциденций.

Матрица смежности вершин – квадратная матрица порядка , где ‑ число вершин.

Рис. 5

Дуга на рис.5 называется петлёй.

Для ориентированного графа на рис.5 матрица смежности имеет вид:

Если предположить, что граф на рис.5 неориентированный, то матрица смежности будет следующей:

Матрица инцидентности рёбер – матрица размера , где ‑ число вершин, ‑ число рёбер.

Рис. 6

Для ориентированного графа на рис.6 матрица инцидентности имеет вид:

Если предположить, что граф на рис.6 неориентированный, то матрица инцидентности будет следующей:

Пусть связный орграф без контуров.

Определение. Под упорядочиванием вершин графа понимается разбиение вершин на группы, при котором:

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

1-я группа

последняя группа

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

i-я группа

(i+1)-я группа

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

Рис. 7

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

Графический способ упорядочивания вершин графа (алгоритм Фалкерсона)

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

Рис. 8

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

Пример. Упорядочить вершины орграфа рис.7.

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

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

Рис. 9

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

3. Вычёркиваем вершину D и все дуги, исходящие из D. Получим граф на рис.9.

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

4. Вычёркиваем вершину Е и все дуги, исходящие из Е. Получим граф на рис.10.

Рис. 10

Рис. 11

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

5. Вычёркиваем вершину А и все дуги, исходящие из А. Получим граф на рис.11.

Находим вершины, в которые не заходит ни одна дуга. Это вершина С. Отнесём её к пятой группе.

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

Рис. 12

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

Рассмотрим матрицу смежности вершин графа:

Определим полустепени входа вершин графа

полустепени выхода вершин графа

Вычислим полустепени входа для графа, заданного матрицей смежности:

, , , , .

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

Получим матрицу

у которой , , , .

Так как , то в вершину D не заходит ни одна дуга и вершина D образует вторую группу. Вычёркиваем из матрицы строку, соответствующую вершине D. Получим матрицу :

у которой , , .

Так как , то в вершину Е не заходит ни одна дуга и вершина Е образует третью группу. Вычёркиваем из матрицы строку, соответствующую вершине Е. Получим матрицу :

у которой , .

Так как , то в вершину А не заходит ни одна дуга и вершина А образует четвёртую группу. Вычёркиваем из матрицы строку, соответствующую вершине А. Получим матрицу :

у которой .

Так как , то в вершину С не заходит ни одна дуга и вершина С образует пятую группу.