Порядковая функция графа

Пусть G = (V, E) – ориентированный граф. Наличие дуги, идущей из вершины u в вершину v, можно интерпретировать как доминирование u над v (в содержательных моделях – превосходство или предпочтительность в некотором смысле). Для вершины u обозначим через G(u) множество всех вершин, над которыми u доминирует, т.е. множество концевых вершин дуг, начинающихся в вершине u. Если U ⊂ V – некоторое множество вершин, обозначим через G(U) объединение всех множеств G(u), где u∈U. Таким образом, v∈G(U) тогда и только тогда, когда над вершиной v доминирует хотя бы одна вершина из U.

Теорема.В непустом ацикличном орграфе G имеется вершина, из которой не исходит ни одна дуга.

До каз а тельст во . Предположим противное. Это означает, что для любой вершины v множество G(v) не пусто. Тогда, выбрав произвольно вершину v0, можно построить сколь угодно длинную цепочку вершин v0, v1∈G(v0), v2∈G(v1), … . Поскольку число вершин графа G конечно, в этой цепочке некоторые вершины будут повторяться. Но цепочка вида vs, vs+1, …, vt = vs является циклом, что противоречит ацикличности графа G.

Условимся обозначать через L0(G) множество всех вершин графа G, из которых не исходит ни одна дуга. В соответствии с предыдущей теоремой L0(G) не пусто, если G – непустой ацикличный граф.

Обозначим через G–1 граф, полученный из графа G

изменением направлений всех дуг на противоположные. Для любой вершины v множество G–1(v) содержит все те вершины, из которых в вершину v ведет некоторая дуга графа G. Множество L0(G–1) состоит из всех тех вершин, в которые не заходит ни одна дуга графа G.

В 13.6 было доказано, что отношение R на конечном множестве V ациклично тогда и только тогда, когда каждому элементу v множества V можно приписать натуральное число ϕ(v) (оценку элемента v) так, что xRy влечет ϕ(x) < ϕ(y) для любых x,y∈V. В этом пункте мы рассмотрим один из алгоритмов «оценивания» вершин ацикличного орграфа, при котором оценки согласуются с отношением доминирования: если вершина u доминирует над вершиной v, то оценка u будет выше, чем оценка v.

Предполагая, что граф G не содержит циклов, разобьем множество его вершин на так называемые уровневые множества (или просто уровни). Уровневые множества строятся рекурсивно:

L0 = { v∈V | G(v) = ∅ } = L0(G);

L1 = { v ∈ V \ L0 | G(v) ⊂ L0 };

L2 = { v ∈ V \ (L0 ∪ L1)| G(v) ⊂ L0 ∪ L1 };

L3 = { v ∈ V \ (L0 ∪ L1 ∪ L2)| G(v) ⊂ L0 ∪ L1 ∪ L2 };

………………………………………………………….

Так как граф G ацикличен, множество L0 не пусто. Обозначим через G′ граф, полученный из графа G отбрасыванием вершин из L0 и входящих в них дуг. Заметим, что L1 = L0(G′). Если V0 ≠ V, граф G′ не пуст и не содержит циклов. Следовательно, множество L1 = L0(G′) не пусто.

Продолжаем аналогичным образом. Если

L0 ∪ L1 ∪…∪ Lk–1 ≠ V,

обозначим через G(k) граф, полученный из графа G отбрасыванием всех вершин из L0 ∪ L1 ∪…∪ Lk–1 и водящих в них дуг. Тогда Lk = L0(G(k)) ≠ ∅. Так как множество вершин графа конечно, в ряду уровневых множеств L0, L1, …, найдется такое множество Lr, что Lr ≠ ∅, а Lr+1 = ∅. Все множества L0, L1, …, Lr не пустые, не пересекаются, а их объединение равно V.

Каждая вершина графа попадает в свое уровневое множество. При этом, если вершина u доминирует над вершиной v, то u окажется на уровне, имеющем больший номер, чем уровень, на котором находится v.

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

L2

L1

L0

Рис. 1

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

L0 ∪L1 ∪…∪Lk–1 ≠ V, и L0(G(k)) = ∅.