Д. Кнут - Искусство программирования том 1 (1119450), страница 101

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 101)

Циклом называется простой путь длиной, большей или равной трем, от некоторой вершины к ней самой. Рис. 29. Граф. Рис. 30. Свободное дерево. Эти определения проиллюстрированы на рис. 29, на котором изображен связный граф с пятью вершинами и шестью ребрами. Вершина С является смежной с А, ио оиа не смежная с вершиной В. От вершины В к вершине С есть два пути длиной два: (В,А,С) и (В,Р,С). В этом графе имеется несколько циклов, например (В, Р, Е, В). Свободное дерево (угее !гес), или дерево без корня (рис. 30), определяется как связный граф без циклов. Это определение применимо как для бесконечных графов, так и для конечных, хотя в компьютерных приложениях обычно используются только конечные деревья.

Можно привести несколько эквивалентных способов определения свободного дерева, например некоторые из пих представлены в следующей хорошо известной теореме. Теорема А. Если С вЂ” граф, то для него буаут эквивалентными следующие утверждения. а) С вЂ” свободное дерево. Ь) С вЂ” связный граф, который при удалении произвольного ребра пересэает быть связным. с) Если Г и à — различные пер~инны графа С, то существует единственный простой путь от вершины 1" к вершине Г( Более того, если граф С конечен и содержит в точности и > 0 вершин, следующие утверждения также будут эквивалентны утверждениям (а) -(с). о) С не содержит циклов п имеет и — 1 ребер. е) С вЂ” связный граф, который имеет и — 1 ребер.

Доказатсльсшво. Из (а) следует (Ь), так как при удалении ребра à — Г', при котором граф С остается связным, должен существовать простой путь (1', Ры..., 1") длины два или более (см. упр. 2), а тогда (Г 1 ы..., 1', \') будет циклом в С. Из (Ь) следует (с), так как есть по крайней мере один путь от вершины Г к вершине Г'. И, если бы существовало два таких пути (\; Гы ..,, Г') и (1г,1",',..., Г'), можно было бы найти такое наименьшее к, для которого Гь ф 1',,' прн удалении ребра Гь ~ — !'ь граф оставался бы связным, так как все еще существует путь (1ь „Г,',...,Г',...,Гь) от вершины Гь э к вершине Гь, который пе включает удаленное ребро.

Из (с) следует (а), так как если С содержит цикл (1', !'~,..., 1'), то существует два простых пути от вершины Г к вершине Ъ~. Чтобы показать, что (с!) и (е) также эквивалентны (а) — (с), сначала докажем вспомогательный результат: в конечном графе С без циклов и хотя бы с одним ребром существует по крайней мере одна вершина, которая является смежной в точности для одной другой вершины. Дьокажем это, рассмотрев некоторую вершину 1ь и смежную с цей другую вершину 1з. Для )г ) 2 вершина!'ь является смежной либо для верьпины 1'ь ь и никакой другой, либо для какой-то другой, например с вершиной Ъгьь.ь ф )ьь ь. Поскольку в этом графе нет циклов, вершины 1 ь, ь'з,..., 1ььь должны быть различными, а потому данный процесс должен в конечном итоге завершиться.

Предположим теперь, что С вЂ” это дерево с и ) 1 вершинами, а 1'„— вершина, смежная тоььько для какой-то одной другой вершины, яапример для вершины Кв ПРи Удалении веРшины 1Г„и РебРа )ьп ь — )ьп полУченный в РезУльтате гРаф С' является деревом, так как вершина 1г„может находиться в простом пути графа С только в качестве начального или конечного элемента. Таким образом, доказано (методом индукции по п), что С имеет п — 1 ребер, а значит, из (а) следует (г)). Предположим, что С удовлетььоряет угловию (г)) и величины 1'ь, К, ь и С' имеют тот же смыгл, что н в предыдущем абзаце. Тогда граф С является связным, поскольку вершина рп связана с вершиной 1ьп ь, которая (по индукции по и) связана со всеми другими вершинами графа С'.

Таким образом, нз (г1) следует (е). Наконец, предположим, что граф С удовлетворяет условию (е). Если граф С содержит цикл, то можно удалить лкьбгк' ребро этого цикла, не нарушая связность графа С. Следовательно, продолжая такиль образом удалять ребра, получим связный граф С' с и — 1 — ьс ребральи и без циклов. Но поскольку из (а) следует (й), то ьс=б,т.е.С=С'. 1 Понятие свободного дерева можно непосредственно использовать для анализа компьютерных алгоритмов. В разделе 1.3.3 уже рассматривалось ььрименелие первого закона Кирхгофа для решения задачи о подсчете числа выполнений каждого шага алгоритма.

В результате было найдено, что закон Кирхгофа не позволяет полностью подсчитать это количество, но с сто помощью можно сокразить число неизвестных, значения которых еще потребуется особым образом интерпретировать. Благодаря теории деревьев можно установить количество оставшихся независимых неизвестных и предложить метод их поиска. Рис. 31. Абстрактная блок-схема программы 1.3.3А. Этот метод легче понять на конкретном примере, который впоследствии будет еще не раз использоваться для иллюстрации результатов применения данной теории.

На рис, 31 показана абстрактная блок-схема программы 1.3.3А после ее анализа на основе закона Кирхгофа из раздела 1.3.3. Каждый квадратик (т. е. блок) на рис. 31 представляет отдельный шаг вычислений, а буква или число внутри него — количество вычислений, которые выполнялись на этом шаге во время работы программы, согласно обозначениям из раздела 1.3.3. Стрелка между блоками указывает на возможность перехода в программе.

Все они отмечены символами емет,...,евт. Теперь задача заключается в том, чтобы на основе закона Кирхгофа найти все отношения между величинами Л, В, С, П, Е, Г, С, Н, 1 К, Т,, Р, ф В и 5, а также глубоко проникнуть в суть общей задачи.

(Замечание. Некоторые упрощения этой задачи уже внесены непосредственно на рис. 31. Например, блок между С и Е уже содержит число "1", что является следствием закона Кирхгофа.) Пусть Е, обозначает количество попыток обхода ветви е, во время выполнения данной программы, По закону Кирхгофа сумма величин Е на входе в блок = значение внутри блока = сумма величин Е на выходе из блока.

Например, для блока К получим (2) Еш + Ело = К = Еьа + Еш . В дальнейшем иелзвестнымп будем считать Еы Ет,..., Еэг, а не Л, В,..., Я. Блок-схему на рис. 31.можно представить в егце более абстрактном виде, т. е. в виде графа С, как показано на рис. 32. Блоки превратились в вершины, а стрелки емет,... теперь предгтавляют собой ребра графа. (Строго говоря, ребра графа не указывают направления, а потому направление стрелок следует игнорировать при рассмотрении теоретических свойств графа С.

Однако, как будет показано ниже, стрелки понадобятся при использовании закона Кирхгофа.) Дополнительно ребро ео, которое проходит от вершины "Начало" до вершины "Конец', вводится для удобства, чтобы закон Кирхгофа был одинаково применим для всех частей графа. В схеме на рис. 32 также внесено несколько изменений по сравнению г блоксхемой, показанной на рис. 31. Дополнительная вершина и ребро добавлены для разбиения стрелки еы на две, е~з и е~з, чтобы соблюдалось основное опргдсление графа (две вершины могут соединяться только одним ребром).

Такому же разбиению подверглась и стрелка е~э. Аналогичную модификацию схемы следовало бы сделать также для любой вершины со стрелкой, указывающей на эту же вершину. Некоторые ребра, представленные на рис. 32, выделены более жирным начертанием по сравнению с остальными. Они образуют свободное поддерево данного графа, соединяющее все его вершины. В графе блок-схемы всегда можно найти свободное поддерево, поскольку такие графы должны быть связными и согласно п. (Ъ) теоремы А, если связный граф С не является свободным деревом, в нем можно удалить ребро и получить граф без потери связности. Этот процесс можно повторять до тех пор, пока не будет получено искомое поддерево. Другой алгоритм поиска свободного поддерева рассматривается в упр.

6. В любом случае прежде всего следует устранить ребро ее (которое проходит от вершины "Начало" до вершины "Конец" ). Таким образом, можно пр( дположить, что ео в выбранном поддереве отсутствует. Пусть С' — свободное поддерево графа С, найденное таким образом. Рассмотрим произвольное ребро 1 — Г графа С, которое огпсутпстлвует в графе С'. Тогда можно отмстить важное следствие из теоремы А: граф С' и его новое ребро 1' — 1" содержат цикл.

Действительгю, имеется в глочиосгии один цикл вида (1', Г,..., 1'), Рнс. 32. Граф со свободным поддеревом, соответствующий блок-схеме на рнс. 31. поскольку существует уникальный простой путь от вершины Ъ' до вершины 1' в графе С'. Например, если С' является свободным деревом, показанным на рис. 32, то, добавив ребро ег, получим цикл, который сначала проходит через ребро ег., а затем (в противоположном направлении по отношению к указанным стрелкам) через ребра е4 и ез. Этот цикл можно записать в алгебраическом виде "ег — е4 — ез", используя знаки "плюс" и "минус" для обозначения направления обхода, когда он совпадает или не совпадает с направлением стрелок. Если выполнить этот процесс для каждого ребра, которое не входит в свободное дерево, получатся так называемые фундаментальные циклы (Зипдатепга! сус!сз), которые для схемы, показанной на рис.

32, выглядят так: Со: ео+е!+ез+е4+еб+е7+еб+езо+е!!+ест+е!4, Сг: ег — е4 — ез, С5. '85 — 87 — еб, Сз. ез + ез + 84 + еб + е7, С1з: е1з + 812 + е!з С!7! 'езг + егг + е24 + егг + е!! + е!5 + еш, а а ! С!9! '819 + 1'18 + е!9 Сго' его + е!8 + егг + егз, С21.' е21 — е!б — 815 — 81! — 827 — 824 — 822 — е!8, Сгз: егз+ егб — еш, (3) Очевидно, что ребро е,, которое не входит в свободное поддерево, будет представлено только в фундаь!ентальных циклах, а именно — в циклах С . Теперь мы вплотную приблизились к кульминационному моменту этого построения. Каждый фундаментальный цикл представляет решение уравнений Кнрхгофа.

Например, решение, соответствующее циклу Сг, выглядит как Ег = +1, Е4 = — 1, Ез = — 1, а соответствующие всем остальным циклам — как Е = О. Ясно, что коэффициенты вдоль цикла в графе всегда удовлетворяют условию (1) закона Кирхгофа. Более того, уравнения Кчгрхгофа являются "однородными', так, что сумма или разница решений уравнений (1) также является решением.

Характеристики

Список файлов книги