logo
Математика_Лекции(4семОЗО)

Упорядочение элементов орграфа. Алгоритм Фалкерсона

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

Вершина xi предшествует вершине xj, если существует путь из xi в xj (xj называется последующей).

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

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

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

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

Аналогично вводится понятие упорядочения дуг.

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

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

  1. Находят вершины, в которые не входит ни одна дуга (I группа). Нумеруют их в натуральном порядке.

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

  3. В полученном графе находят вершины, в которые не входит ни одна дуга (II группа). Их нумеруют соответствующими номерами.

  4. И т.д., пока не будут пронумерованы все вершины.

Аналогично упорядочивают дуги орграфа:

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

  2. Вычеркивают найденные дуги.

  3. Находят дуги, которые не имеют непосредственно предшествующих (без дуг I группы). Они составляют II группу.

  4. И т.д. пока все дуги не будут разбиты на группы.

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

Решение.

В вершину х6 не входит ни одна дуга, т.е. х6 не имеет предшествующих вершин. Поэтому относится к I группе.

Исключаем х6 и дуги, исходящие из нее.

Далее х2 и х4 не имеют предшествующих вершин – II группа.

х3, х5 – III группа.

х1 – IV группа;

х7 – V гр.

Строим новый граф.