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

Пусть 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) не пусто. Тогда, выбрав произвольно вершину v 0, можно построить сколь угодно длинную цепочку вершин v 0, v 1∈ G (v 0), v 2∈ G (v 1), …. Поскольку число вершин графа G конечно, в этой цепочке некоторые вершины будут повторяться. Но цепочка вида vs, vs +1, …, vt = vs является циклом, что противоречит ацикличности графа G.

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

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

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

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

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

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

L 1 = { v ∈ V \ L 0 | G (v) ⊂ L 0 };

L 2 = { v ∈ V \ (L 0 ∪ L 1)| G (v) ⊂ L 0 ∪ L 1 };

L 3 = { v ∈ V \ (L 0 ∪ L 1 ∪ L 2)| G (v) ⊂ L 0 ∪ L 1 ∪ L 2 };

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

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

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

L 0 ∪ L 1 ∪…∪ Lk –1 ≠ V,

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

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

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

L 2

L 1

L 0

Рис. 1

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

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

Не нашли, что искали? Воспользуйтесь поиском: