![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 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 и алгоритмов их обработки.
|