AOP_Tom1 (1021736), страница 103
Текст из файла (страница 103)
Если следовать терминологии, предлагаемой некоторыми авторами работ по теории графов, то следовало бы вместо термина "дерево" использовать термин "конечное упорядоченное дерево с указанным корнем", а вместо термина "бинарное дерево" — "топологическая раздвоенная древовидность"! 2.3.4.1. Свободные деревья. Граф (дгарЬ) обычно определяется как множество точек (называемых вершинами (иегйсез)) вместе с набором линий (называемых ребрами (еадез)), которые соединяют определенные пары вершин.
Каждая пара вершин соединяется не более чем одним ребром. Две вершины называются смежными (алуасся!), если их соединяет ребро. Если И и )г' являются вершинами и я > О, то (Иа, Уь...,1'„) называется путем длины и от вершины )г к вершине $", если )г = )га, вершина )гз является смежной для вершины )гз г1 для О ~ а ( и, а 1"„= 1". Путь называется простлмм (зипр!е), если различны вершины !ге, )гы, .., Р„1 и если различны вершины )гы...,)г„ы$г„. Граф называется связным (сояпес!ед), если существует путь между любыми двумя его вершинами.
Циклом называется простой путь длиной, большей или равной трем, от некоторой вершины к ней самой. Рис. 29. Граф. Рис. 30. Свободное дерево. Эти определения проилл|острированы на рис. 29, на котором изображен связный граф с пятью вершинами и шестью ребрами. Вершина С является «нежной с А, по она не смежная с вершиной В. От вершины В к вершине С ««ть два пути длиной два: (В,А,С) н (В,Р,С).
В этом графе имеется несколько циклов, например (В, Р, Е, В). Свободное дерева (~«ее нее), или дерево без корня (рис. 30), опред«ляется как связный граф без циклов. Это определение применимо как для бесконечных графов, так и для конечных, хотя в компьютерных приложениях обычно используются только конечные деревья. Можно привести несколько эквивалентных способов определения свободного дерева, например некоторые из них представлены в следующей хорошо известной теореме.
Теорема А. Если С вЂ” граф, то дл» него будут эквпвалептпымп следующие утвейя ждення. а) С вЂ” свободное дерево. Ь) С вЂ” связный граф, который прн удалешш произвольного ребра перестает быть связным. с) Если Г п Г' — различные вершины графа С, то существует единств«нный простой путь от вершины 1' к вершине 1''( Более того, е«лн граф С конечен п содержит в точности и > 0 вершин, «ледуюгдп« утверждения также будут эквивалентны утверждениям (а)-(с). д) С не содержит циклов и имеет и — 1 ребер. е) С вЂ” связный граф, который имеет и — 1 ребер. Докаэашельство. Из (а) следует (Ь), так как нри удалении ребра à — 1' ', при котором граф С остается связным, должен существовать простой путь (1', 1',,..., 1") длины два или более (см.
упр. 2), а тогда (1; 1'~,..., 1", Г) будет циклом в С. Из (Ь) следует (с), так как есть по крайней мере один путь от вершины Г к вершине 1". И„если бы существовало два таких пути (1', 1'~,..., Г') и (Г, 1",,..., Г'), можно было бы найти такое наименьшее к, для которого Гт Ф Г~( прн удалении ребра Гв 1 — 1ь граф оставался бы связным, так как все еще существует путь (1 ь,, Г,',,1',..., Гь) от вершины Гь 1 к вершине Гь, который пе включает удаленное ребро. Из (с) следует (а), так как если С содержит цикл (1;1'ы, ..,1 ), то существует два простых пути от вершины Г к вершине 1'и Чтобы показать, что (д) и (е) также эквивалентны (а) — (с), сначала докажем вспомогательный результат: в конечном графе С без циклов и хотя бы с одним ребром суще»'твует по крайней мере одна вершина. которая является смежной в точности для одной другой вершины.
Докажем это, рассмотрев некоторую вершину 1'» и смежную с цей друтую вершину 1»». Для )» > 2 вершина 1'» является смежной либо для вершины Г»» и никакой другой, либо для какой-то другой, например с вершиной К, >» ф 1»». ». Поскольку в этом графе нет циклов., вершины Г»,Гэ,..., Ъь~» должны быть различными, а потому данный процесс должен в конечном итоге завершиться. Предположим теперь, что С вЂ” это дерево с и ) 1 вершинами, а Ä— вершина, смежная только для какой-то одной другой вершины, напри»»ер для вершины Г„ При удалении вершины !'„и ребра Г„» — 1в полученный в результате граф С' является деревом, так как вершина 1'„может находиться в простом пути графа С только в качестве начального или конечного элемента. Таким образом, доказано (методом индукции по и), что С имеет п — 1 ребер, а значит, из (а) следует (»)).
Предположим, что С удовлетворяет условию (»)) и величины Г„1;, » и С' имеют тот же смысл, что и в предыдущем абзаце, Тогда граф С является связным, поскольку вершина Г„связана с вершиной Г„», которая 1по индукции по и) связана со всеми друтими вершинами графа С'. Таким образом, из»с1) следует»е). Наконец, предположим, что граф С удовлетворяет условию»»»). Если граф С содержит цикл, то можно удалить любое ребро этого цикла, не нарушая связность графа С. Следовательно, продолжая таким образом удалять ребра, получим связный граф С' с и — 1 — и ребрами и без циклов.
Но поскольку из (а) следует (»)), то й=б,т. е, С=С'. 1 Понятие свободного дерева можно непосредственно использовать для анализа компьютерных алгоритмов. В разделе 1.3.3 уже рассматривалось применение первого закона Кирхгофа для решения задачи о подсчете числа выполнений каждого шага алгоритма. В результате было найдено, что закон Кирхгофа не позволяет полностью подсчитать это количество, но с его помощью можно сократить число неизвестных, значения которых еще потребуется особым образом интерпретировать. Благодаря теории деревьев можно установить количество оставшихся независимых неизвестных и предложить метод их поиска.
Рис. 31. Абстрактная блок-схема программы 1,З.ЗА. Этот метод легче понять на конкретном примере, который впоследствии будет еще не раз использоваться для иллюстрации результатов применения данной теории. На рис. 31 показана абстрактная блок-схема программы 1.3.3А после ее анализа на основе закона Кирхгофа из раздела 1.3.3. Каждый квадратик (т. е. блок) на рис. 31 представляет отдельный шаг вычислений, а буква или число внутри него — количество вычислений, которые выполнялись на этом шаге во время работы программы, согласно обозначениям из раздела 1.3.3. Стрелка между блоками указывает на возможность перехода в программе, Все они отмечены символами еыег,...,егт.
Теперь задача заключается в том, чтобы на основе закона Кирхгофа найти все отношения между величинами А, В, С, Р, Е, Е, С, Н, 1, К, Т,, Р, Я, В и Я, а также глубоко проникнуть в суть общей задачи. (Замечание. Некоторые упрощения этой задачи уже внесены непосредственно на рис. 31.
Например, блок между С и Е уже содержит число "1", что является следствием закона Кирхгофа.) Пусть Е. обозначает количество попыток обхода ветви ег во время выполнения данной программы. По закону Кирхгофа сумма величин Е на входе в блок = значение внутри блока = сумма величин Е на выходе из блока. Например, для блока К получим Еш+ Его = К = Егв+ Егы (2) В дальнейшем непзвестнымп будем считать Еы Ег,..., Егг, а не А, В,..., 5.
Блок-схему иа рис. 31 можно представить в еще более абстрактном виде., т. е. в виде графа С, как показано на рис. 32. Блоки превратились в вершины, а стрелки еыег,.., теперь представляют собой ребра графа. (Строго говоря, ребра графа не указывают направления, а потому направление стрелок следует игнорировать при рассмотрении теоретических свойств графа С. Однако, как будет показано ниже, стрелки понадобятся при использовании закона Кирхгофа.) Дополнительно ребро ео, которое проходит от верппшы "Начало" до вершины "Конец", вводится для удобства, чтобы закон Кирхгофа был одинаково применим для всех частей графа. В схеме на рис.
32 также внесено несколько изменений по сравнению с блоксхемой, показанной на рис. 31. Дополнительная вершина и ребро добавлены для разбиения стрелки еш на две, е'. и е,", чтобы соблюдалось основное определение графа (две вершины могут соединяться только одним ребром). Такому же разбиению подверглась и стрелка еш. Аналогичную модификацию схемы следовало бы сделать также для любой вершины со стрелкой, указывающей на эту же вершину. Некоторые ребра, представленные на рис. 32, выделены более жирным начертанием по сравнению с остальными, Они образуют свободное поддерево данного графа, соединяющее все его вершины. В графе блок-схемы всегда можно найти свободное поддерево, поскольку такие графы должны быть связными и соглагно и. (Ь) теоремы А, если связный граф С не является свободным деревом, в нем можно удалить ребро и получить граф без потери связности.
Этот процесс можно повторять до тех пор, пока не будет получено игкомое поддерево. Другой алгоритм поиска свободного поддерева рассматривается в упр. 6. В любом случае прежде всего следует устранить ребро ео (которое проходит от вершины "Начало" до вершины "Конец" ). Таким образом, можно предположить, что ео в выбранном поддереве отсутствует. Пусть С' — свободное поддерево графа С, найденное таким образом. Рассмотрим произвольное ребро à — Г' графа С, которое отсушствует в графе С'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
