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

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

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

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

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

Аналогичным образом вводится понятие упорядочения дуг. В результате упорядочения элементов получают орграф, изоморфный исходному. Упорядочение элементов выполняется графическим или матричным способом. Графический способ упорядочивание вершин, дуг орграфа носит название алгоритма Фалкерсона.

Алгоритм Фалкерсона для упорядочения вершин:

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

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

Алгоритм Фалкерсона для упорядочения дуг:

1. Найти дуги, не имеющие непосредственно предшествующих (они образуют I группу).

2. Вычеркнуть найденные дуги; после этого появится, по крайней мере, одна новая дуга, не имеющая непосредственно предшествующей (в графе без дуг I группы). Такие дуги составляют II группу. Повторять этот шаг, пока все дуги не будут разбиты на группы. В заключение упорядочения дугам присваивают новые обозначения с индексами 1, 2, ... .

__________________________________

Пример 7.11. Графическим способом упорядочить вершины и дуги заданного орграфа.

Решение. Используя алгоритм Фалкерсона, упорядочим вершины и дуги заданного орграфа.

_________________________________