Упорядоченные графы
Упорядоченные графы
Представление Lv вершин, смежных с v, в виде списка связей определяет «порядок» ребер, выходящих из v (рис. 13).
Рис. 13. Пример упорядоченного графа
Множество V = {v1, v2,…, vn} вершин вместе с множеством {Lv1, Lv2, …, Lvn} упорядоченных списков упорядоченных пар вершин называют упорядоченным графом.
"2 Основные положения конфликтологии" - тут тоже много полезного для Вас.
Для того чтобы рассматриваемые структуры являлись графами, необходимо наложить некоторые условия на списки Lv:
· (v, v) Î Lv , " v Î V;
· (w, u) Î Lw Þ (u, w) Î Lu.
Граф, изображенный на рис. 13, может быть представлен в терминах упорядоченного графа следующим образом:
({v1, v2, v3, v4}, {((v1, v2), (v1, v3), (v1, v4)), ((v2, v1), (v2, v3), (v2, v4)), ((v3, v1), (v3, v2), (v3, v4)), ((v4, v1), (v4, v2), (v4, v3))}).
Упорядоченный граф определяет единственный неупорядоченный граф. Обратное утверждение неверно, так как в общем случае возможно много способов упорядочения графа.