Структуры данных и алгоритмы (1021739), страница 50
Текст из файла (страница 50)
Такие дуги, ведущие к новым вершинам, называются дугами дерева и формируют для данногографа остовный лес, построенный методом поиска в глубину, или, сокращенно, глубинный остовный лес. На рис. 6.17 показан глубинный остовный лес для графа изрис. 6.16. Здесь сплошными линиями обозначены дуги дерева. Отметим, что дугидерева формируют именно лес, т.е. совокупность деревьев, поскольку методом поискав глубину к любой ранее не посещавшейся вершине можно придти только по однойдуге, а не по двум различным дугам.В добавление к дугам дерева существуют еще три типа дуг, определяемых в процессе обхода орграфа методом поиска в глубину. Это обратные, прямые и поперечныедуги. Обратные дуги (как дуга С -»А на рис.
6.17) — такие дуги, которые в остовном лесе идут от потомков к предкам. Отметим, что дуга из вершины в саму себятакже является обратной дугой. Прямыми дугами называются дуги, идущие отпредков к истинным потомкам, но которые не являются дугами дерева. На рис. 6.17прямые дуги отсутствуют.Дуги, такие как D —> С и G -» .D на рис. 6.17, соединяющие вершины, не являющиеся ни предками, ни потомками друг друга, называются поперечными дугами. Ес198ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫли при построении остовного дерева сыновья одной вершины располагаются слеванаправо в порядке их посещения и если новые деревья добавляются в лес также слева направо, то все поперечные дуги идут справа налево, что видно на рис. 6.17. Такое взаимное расположение вершин и деревьев выбрано не случайно, так как это помогает формировать остовный лес.Рис.
6.17. Глубинный остовный лес для орграфаиз рис. 6.16Как можно различить эти четыре типа дуг? Легко определить дуги дерева, таккак они получаются в процессе обхода графа как дуги, ведущие к тем вершинам, которые ранее не посещались. Предположим, что в процессе обхода орграфа его вершины нумеруются в порядке их посещения. Для этого в листинге 6.8 после строки (1)надо добавить следующие строки:dfnirnibertv] := count;count:= count + 1;Назовем такую нумерацию глубинной нумерацией ориентированного графа.
Отметим, что эта нумерация обобщает нумерацию, полученную при прямом обходе дерева(см. раздел 3.1).Всем потомкам вершины v присваиваются глубинные номера, не меньшие,чем номер, присвоенный вершине v. Фактически вершина w будет потомкомвершины v тогда и только тогда, когда выполняются неравенства dfnumber(v) <dfnumber(w) < dfnumber(v) + количество потомков вершины v1. Очевидно, чтопрямые дуги идут от вершин с низкими номерами к вершинам с более высокиминомерами, а обратные дуги — от вершин с высокими номерами к вершинам с более низкими номерами.Все поперечные дуги также идут от вершин с высокими номерами к вершинам сболее низкими номерами.
Чтобы показать это, предположим, что есть дуга ж -»у ивыполняется неравенство dfnumber(x) < dfnumber(y). Отсюда следует, что вершина жпройдена (посещена) раньше вершины у. Каждая вершина, пройденная в промежуток времени от вызова dfs(x) и до завершения dfs(y), становится потомком вершиных в глубинном остовном лесу. Если при рассмотрении дуги х —> у вершина у еще непосещалась, то эта дуга становится дугой дерева. В противном случае дуга х —> у будет прямой дугой. Таким образом, если для дуги х -» у выполняется неравенствоdfnumber(x) < dfnumberiy), то она не может быть поперечной дугой.В следующих разделах этой главы мы рассмотрим применения метода поиска вглубину для решения различных задач на графах.1Для истинных потомков вершины v первое из приведенных неравенств должно бытьстрогим.
— Прим. ред.6.5. ОБХОД ОРИЕНТИРОВАННЫХ ГРАФОВ1996.6. Ориентированные ациклические графыОриентированный ациклический граф — это орграф, не имеющий циклов. Можносказать, что ациклический орграф более общая структура, чем дерево, но менее общая по сравнению с обычным ориентированным графом. На рис. 6.18 представленыдерево, ациклический орграф и ориентированный граф с циклом.Рис. 6.18. Три ориентированных графаАциклические орграфы удобны для представления синтаксических структурарифметических выражений, имеющих повторяющиеся подвыражения.
Например,на рис. 6.19 показан ациклический орграф для выражения((о + Ь)*с + ((а + Ь) + е) * (е + /)) * ((а + Ь)*с).Подвыражения а + Ь и (а + Ь)*с встречаются в выражении несколько раз, поэтомуони представлены вершинами, в которые входят несколько дуг.Рис. 6.19. Ориентированный ациклический граф для арифметического выраженияАциклические орграфы также полезны для представления отношений частичныхпорядков. Отношением частичного порядка R, определенным на множестве S, называется бинарное отношение, для которого выполняются следующие условия.1.2.200Ни для какого элемента а из множества S не выполняется aRa (свойство антирефлексивности).Для любых а, Ь, с из S, таких, что aRb и ЬВс, выполняется aRc (свойство транзитивности).ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫДвумя естественными примерами отношений частичного порядка могут служитьотношение "меньше чем" (обозначается знаком "<"), заданное на множестве целыхчисел, и отношение строгого включения (с) множеств.Пример 6.14. Пусть S = {1, 2, 3} и P(S) — множество всех подмножеств множества S, т.е.
P(S) = {0, {!}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Отношение строгоговключения (с) является отношением частичного порядка на множестве P(S). Очевидно, включение А с А не выполняется для любого множества А из Р(антирефлексивность), и при выполнении А с В и В с: С выполняется А с С(транзитивность). ПАциклические орграфы можно использовать для графического изображения отношения частичного порядка между какими-либо объектами. Для начала можнопредставить отношение R как одноименное множество пар (дуг) таких, что пара (а, Ь)принадлежит этому множеству только тогда, когда выполняется aRb. Если отношение R определено на множестве элементов S, то ориентированный граф G = (S, R) будет ациклическим. И наоборот, пусть G = (S, R) является ациклическим орграфом, аЛ+ — отношение, определенное следующим образом: aR+b выполняется тогда и только тогда, когда существует путь (длиной не менее 1) от вершины а к вершине Ь.
Тогда R+ — отношение частичного порядка на S. (Отношение R+ является транзитивным замыканием отношения R.)Пример 6.15. На рис. 6.20 показан ациклический орграф CP(S), R), где S = {1, 2, 3}.Здесь Д+ — отношение строгого включения на множестве P(S). DРис. 6.20. Ациклический орграф,представляющий отношение строгого включенияПроверка ацикличности орграфа• ..Предположим, что есть ориентированный граф G = (V, Е) и мы хотим определить,является ли он ациклическим, т.е. имеет ли он циклы.
Чтобы ответить на этот вопрос, можно использовать метод поиска в глубину. Если при обходе орграфа G методом поиска в глубину встретится обратная дуга, то ясно, что граф имеет цикл. С другой стороны, если в орграфе есть цикл, тогда обратная дуга обязательно встретитсяпри обходе этого орграфа методом поиска в глубину.Чтобы доказать это, предположим, чт9 орграф G имеет цикл.
Пусть при обходеданного орграфа методом поиска в глубину вершина v имеет наименьшее глубинноечисло среди всех вершин, составляющих цикл. Рассмотрим дугу и —> и, принадлежащую этому циклу. Поскольку вершина и входит в цикл, то она должна быть потомком вершины и в глубинном остовном лесу. Поэтому дуга и -» и не может бытьпоперечной дугой. Так как глубинный номер вершины и больше глубинного номеравершины v, то отсюда следует, что эта дуга не может быть дугой дерева и прямой дугой.
Следовательно, дуга и —> v является обратной дугой, как показано на рис. 6.21.6.6. ОРИЕНТИРОВАННЫЕ АЦИКЛИЧЕСКИЕ ГРАФЫ201Топологическая сортировкаБольшие проекты часто разбиваются на совокупность меньших задач, которыевыполняются в определенном порядке и обеспечивают полное завершение целогопроекта. Например, план учебного заведения требует определенной последовательности в чтении учебных курсов. Ациклические орграфы могут служить естественноймоделью для таких ситуаций.
Например, мы создадим дугу от учебного курса С кучебному курсу D тогда, когда чтение курса С предшествует чтению курса D.Пример 6.16. На рис. 6.22 показан ациклический орграф, представляющийструктуру предшествований пяти учебных курсов. Чтение учебного курса СЗ, например, требует предварительного чтения курсов С1 и С2. ПРис. 6.21. Каждый циклсодержит обратную дугуРис. 622. Ациклический орграф, представляющий структуру предшествованийТопологическая сортировка — это процесс линейного упорядочивания вершинациклического орграфа таким образом, что если существует дуга от вершины i квершине j, то в упорядоченном списке вершин орграфа вершина i предшествует вершине j.
Например, для орграфа из рис. 6.22 вершины после топологической сортировки расположатся в следующем порядке: С1, С2, СЗ, С4, С5.Топологическую сортировку легко выполнить с помощью модифицированнойпроцедуры листинга 6.8, если в ней после строки (4) добавить оператор выводана печать:procedure topsort ( v: вершина ) ;{ печать в обратном топологическом порядке вершин,достижимых из вершины v }varw: вершина;beginmark[v]:= visited;for каждая вершина w из списка L[v] doif mark[w] = unvisited thentopsort (iv) ;writeln (v)end; { topsort }Когда процедура topsort заканчивает поиск всех вершин, являющихся потомкамивершины и, печатается сама вершина и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
