Глава 19. Орграфы и ориентированные ациклические графы. сивно, если sRs справедливо для всех s

сивно, если sRs справедливо для всех s. Симметричные отношения соответствуют неори­ентированным графам. Рефлексивные отношения соответствуют графам, в которых в каж­дой вершине есть петли; отношения, соответствующие графам, в котором ни у одной из вершин нет петель, называются нерефлексивными.

Говорят, что отношение транзитивно, когда из sRt и tRu следует sRu для всех s, t и и. Транзитивное замыкание (transitive closure) того или иного отношения представляет собой четко определенное понятие; однако вместо того, чтобы давать его определение в кон­тексте теории множеств, мы обратимся к определению орграфов, данному в разделе 19.3. Любое отношение эквивалентно некоторому орграфу, а транзитивное замыкание этого отношения эквивалентно транзитивному замыканию орграфа. Транзитивное замыкание любого отношения само транзитивно.

В контексте алгоритмов на графе особый интерес вызывает у нас два специальных транзитивных отношения, которые определяются дальнейшими ограничениями. Эти два типа отношений, получивших широкое применение, известны как отношения эквивален­тности (equivalence relations) и частичные порядки (partial orders).

Отношение эквивалентности (=) есть транзитивное отношение, которое к тому же реф­лексивно и симметрично. Обратите внимание на тот факт, что симметричное и транзитив­ное отношение, которое помещает каждый объект в некоторую упорядоченную пару, дол­жно быть отношением эквивалентности: если s = t, то t = s (по симметричности) и s = s (по транзитивности). Отношение эквивалентности разносит объекты множества по под­множествам, известным как классы эквивалентности (equivalence class). Два объекта s и t со­держатся в одном и том же классе эквивалентности тогда и только тогда, когда s = t. Ти­пичными примерами эквивалентности могут служить следующие отношения:

Арифметика над абсолютными значениями чисел. Любое положительное целое к оп­ределяет на множестве целых чисел отношение эквивалентности, т.е. s = t (mod к) тогда и только тогда, когда остаток от деления s на к равен остатку от деления t на к. Очевид­но, что это отношение симметрично, несложное доказательство показывает, что оно еще и транзитивно (см. упражнение 19.67) и в силу этого обстоятельства это отношение есть отношение эквивалентности.

Связность в графах. Отношение " содержится в той же связной компоненте, что и...", связывающее вершины, есть отношение эквивалентности, ибо оно симметрично и тран­зитивно. Классы эквивалентности соответствуют связным компонентам в графах.

Когда мы выполняем построение АТД графа, который предоставляет клиентам воз­можность проверки, находятся ли две какие-либо вершины в одной и той же связной компоненте, мы реализуем АТЖ отношения эквивалентности, который предоставляет кли­ентам возможность проверки эквивалентности двух объектов. На практике это соответ­ствие имеет большое значение, поскольку граф есть сжатая форма представления отно­шения эквивалентности (см. упражнение 19.71). Фактически, как мы видели в главах 1 и 18, чтобы построить такой АТД, мы должны поддерживать только один вектор, индек­сированный именами вершин.

Частичный порядок (partial order) < есть транзитивное нерефлексивное отношение. Нетрудно доказать, что из нерефлексивности и транзитивности вытекает тот факт, что частичные порядки асимметричны. Если s < t и t < s, то s < s (по транзитивности), что противоречит нерефлексивности, т.е. s < t и t < s одновременно выполняться не могут.

Часть 5. Алгоритмы на графах

Более того, используя ту же аргументацию, легко показать, что в условиях частичного порядка циклы, такие как s < t, t•< и и и < s, невозможны. Следующие примеры представ­ляют собой типичные частичные порядки:

Включение подмножеств. Отношение " включает, но не равно" (с), определенное на множестве подмножеств дан­ного множества есть частичный порядок — естественно, он нерефлексивен, и если s с t и t с и, то s с и.

Пути в графах DAG. Отношение " достижим посредством непустого пути из..." есть частичный порядок на множестве вершин графа DAG без петель, поскольку оно транзитивно и нерефлексивно. Подобно отношению эквивалентности и неориентированным графам, этот конкретный частичный порядок важен для многих приложений, поскольку DAG представляет собой неявное представление частичного поряд­ка в сжатой форме. Например, рис. 19.17 служит иллюстра­цией графа DAG частичных порядков включения под­множеств, количество ребер которых составляет лишь небольшая часть мощности частичного порядка (см. упраж­нение 19.73).

В самом деле, мы редко определяем частичные порядки посредством перечисления всех упорядоченных пар, по­скольку таких пар очень много. Вместо этого мы в общем случае определяем нерефлексивное отношение (граф DAG) и рассматриваем его транзитивное замыкание. Такое его ис­пользование является для нас основной причиной изучения АТД, реализующих абстрактное транзитивное замыкание графов DAG. Работая с графами DAG, мы рассмотрим при­меры частичных порядков в разделе 19.5.

Полный порядок (total order) T есть частичный порядок, при котором выполняется либо sTt, либо tTt, s ≠ t. Знакомы­ми нам примерами полного порядка являются отношение " меньше чем" на множествах целых или вещественных чисел или лексикографический порядок на множестве строк сим­волов. Наши исследования алгоритмов поиска и сортиров­ки в частях 3 и 4 основывались на реализации полностью

РИСУНОК 19.17. ГРАФ DAG ВКЛЮЧЕНИЯ МНОЖЕСТВ

В графе DAG, показанном в верхней части рисунка, вершины представляют некоторое подмножество множества, состоящего из трех элементов в соответ­ствии с таблицей, приведен­ной в нижней части рисунка. Транзитивное замыкание этого графа представляет собой порядок включения подмножеств: существует ориентированный путь между двумя узлами в том и только том случае, когда подмножество, представляе­мое первым узлом, содержит­ся в подмножестве, пред­ставленном вторым узлом.

Глава 19. Орграфы и ориентированные ациклические графы 193

■ Отношения и орграфы.

■ Симметричные отношения и неориентированные графы.

■ Транзитивные отношения и пути в графах.

■ Отношения эквивалентности и пути в неориентированных графах.

■ Частичные порядки и пути в графах DAG.

Из изложенного выше следует, что все типы графов и алгоритмов, которые мы изу­чаем, имеют хорошую перспективу и снабжают нас дополнительной мотивацией для изу­чения базовых свойств графов DAG и алгоритмов их обработки.