AOP_Tom1 (1021736), страница 105
Текст из файла (страница 105)
упр. 9). Теорема К обнадеживает, поскольку в ней говорится, что закон Кирхгофа (который состоит из и уравнений для гп неизвестных Е,, Ег,..., Е,„) обладает лишь одной "избыточной переменной": эти и уравнений позволяют исключить и — 1 неизвестных. Однако неизвестные переменные в приведенных выше рассуждениях обозначали количество прохождений ребер, а не количество входов в каждый блок блок-схемы. В упр.
8 показано, как построить другой граф. ребра которого соответствуют блокам блок-схемы, так что описанная выше теория может быть использована для опреде. пения истинного числа избыточных переменных. Способы применения теоремы К в программном обеспечении, используемом для оценки производительности программ на языках программирования высокого уровня, рассмотрены Томасом Боллом (ТЬошаэ Ва11) и Джеймсом Р. Ларусом (Латеэ В. ) агцэ) в работе АСМ Тгапэ. Ргок, Еапйтгайев апс( Буэгетэ 16 (1994), 1319 — 1360. УПРАЖНЕНИЯ 1. [Ц] Перечислите все циклы от вершины В до вершины В, которые содержатся в графе, показанном на рис.
29. 2. [М20] Докажите, что если в графе существует путь от вершины К до вершины Ъ", то между этими вершинами также имеется простой путь. 3. [15] Какой путь от блока "Начало" до блока "Конец" является эквивалентным (в смысле теоремы К) одному проходу фундаментального пути плюс один проход цикла Сг па рис. 32? 4. [М20] Пусть С' является конечным свободным деревом, в котором стрелки нарисованы на ребрах еп...,е„ь Пусть Еь...,Е„г — это числа, удовлетворяющие закону Кирхгофа (1) в С'.
Покажите, что Е~ = = Е г = О. 5. [20] Используя уравнения (6), выразите значения А, В,..., Е, которые находятся внутри блоков иа рис. 31, с помощью независимых переменных Ег, Ег,, Егг. 6. [М27] Допустим, что граф содержит п вершин $'и..., $~„и т ребер ем...,е . Каждое ребро е между вершинами 1; и г1 представлено парой целых чисел (а,Ь). Создайте максимальлю эффективный алгоритм, который использует в качестве входного потока пары чисел (ал, Ьл), ..., (агм Ь„), а на выходе распечатывает подмножество ребер, которые образуют свободное дерево„.
Если это невозможно, алгоритм должен выдать сообщение об ошибке. 1. [22) Выполните описанное в этом разделе построение для блок-схемы используя для этого свободное поддерево из ребер ел, ез, ез, ел, ев. Найдите фундаментальные циклы и выразите Ел, Ез, Ез, Е4, Ео на основании переменных Ез, Ев, Ег и Ев. 8. (Мйб) Того, кто применяет закон Кирхгофа для программирования блок-схемы, обычно интересуют поплоки через оершинлл (оегввх /(ощл) (т. е. количество прохождений каждого блока для данной блок-схемы), а не потоки через ребра.
Например, на схеме в упр. 1 потони через вершины равны А = Ез + Ел, В = Ел, С = Ез Ч- Ет + Ев, Р = Ев + Ео. Если сгруппировать некоторые вершины, рассматривая их как одну "суперверлпину", можно объединить потоки ребер, которые соответствуют одному и тому же потоку вершины. Наприллер. в показанной выше блок-схеме ребра ез и ев можно объединить, если совместить вершины В и Рс (Здесь также от вершины "Начало" до вершины "Конец" проведено ребро ео ) Продолжая этот процесс, можно объединить сначала ребра ел+ел, затем — (ел+ел)+ев и ее+ее, пока не получится приведенная блок-схема с ребрами в = ел, а = ел+ ел, Ь = ез, с = ез + ел + ев, Ы = ел + во, л = ео, где на кажлую вершину исходной блок-схемы приходится в точности по одному ребру: По построению в приведенной блок-схеме закон Кирхгофа соблюдается.
Новыми потоками ребер здесь являются потоки вершин исходной блок-схемы. Следовательно, примення упомянутый в этом разделе анализ по отношению к рассматриваемой блок-схелле, можно получить представление о взаимосвязях между исходными потоками вершин. Докажите, что процесс приведения блок-схемы можно обратить в том смысле, что любое множество потоков (а, Ь,...), которое удовлетворяет закону Кирхгофа в приведенной блок-схеме, может быть "расщеплено" на набор потоков ребер (ео, ел,...) в исходной блок-схеме.
Эти потоки е, удовлетворяют закону Кирхгофа, и, если их объединить, мож. но получить потоки (а,Ь,...). Причем некоторые из них ллогут быть отрицательными. (Хотя здесь показан процесс приведения только для одной частной блок-схемы, данное доказательство должно выполняться в общем случае.) 9.
[ЛИ8[ Ребра е~д и еио показанные на рис. 32, расщеплены на две части, поскольку предполагается, что в графе не может быть двух ребер, которые объединяют эти же две вершины. Если взглянуть на окончательный результат построения, то расщепление на две части выглядит достаточно искусйтвенным, потому что наряду с двумя соотношениями Е,'д — — Е[д и Е[д — — Е[д в (6) содержатся две независимые переменные: Е",д и Е[д, Объясните, как это построение можно обобщить, чтобы избежать искусственного расщепления ребер. 10.
[1б[ Проектируя электрическую схему компьютера, инженер-электрик приходит к выводу, что необходимо иметь п выводов Тц Тг,..., Т„с практически одинаковыми значениями рабочего напряжения. Для этого он может спаять провода между любой парой выводов. Смысл этого действия заключается в организации достаточного колйчества соединений, чтобы существовал путь между любыми двумя выводами. Покажите, что минимальное количество соединений между парами выводов для организации такой сети выводов будет равно и — 1, причем и — 1 соединений между парами выводов позволяют создать такую сеть тогда и только тогда, когда они образуют свободное дерево (в котором выводы и соединения являются вершинами и ребрами).
11. [М37[ (В. С. Рпт. Вед Еудгет Тесй. Х 36 (1957), 1389 — 1401.) Рассмотрим задачу о соединениях из упр. 10 с дополнительным условиелк лля каждой пары д < у' задается цена с(й У), которая обозначает затраты на подключение вывода Т. к выводу Т,. Покажите, что приведенный ниже алгоритм позволяет получить дерево соединений с минимальной ценой.
"Если и = 1, ничего делать не нужно В противном случае перенумеровать выводы (1,...,п — 1) и цены так, чтобы с(п — 1, и) = пип~б,<„с(1,п); соединить выводы Тд ~ и Т„; заменить цену с(у, и — 1) ценой и~п(с(1, п — 1), с(д, и)) для 1 < 1' < и — 1 и повторить этот алгоритм для и — 1 выводов Ты..., Т„ы используя новые цены. (Алгоритм следует повторять, принимая во внимание то, что каждый раз, когда необходимо создать соединение между выводамн Т. и Т„,, соединение на самом деле задается между перенумерованными выводами Т, и Т, если такое соединение оказывается более дешевым. Тахим образом, выводы Т„д и Т„в осталыюй части алгоритма рассматриваются как один вывод.) ' Этот алгоритм можно сформулировать и так: "Сначала следует выбрать какой-то один вывод, затем создавать его самое дешевое соединение с другим выводом до тех пор, пока не будут выбраны все выводы".
3 (а) (Ь) Рис. 33. Свободное дерево с минимальной ценой. 0 1 2 3 4 Рассмотрим, например, рис. 33, (а), на котором показана некоторая сетка с девятью выводами. Пусть цена соединения двух выводов определяется его длиной, а именно— расстоянием между выводами. (Читатель может попытаться вручную найти дерево с минимальной ценой, используя интуицию вместо предложенного алгоритма.) Этот алгоритм соединит сначала выводы Тд и Тд, затем — Тд и Тд, Тд и Ть, Тг и Тд, Тк и Тг, Тд и Тп Тг и Тд и, наконец, Т4 соединит либо с Тд, либо с Тд.
Дерево с минимальной ценой (с длиной провода 7 + 2чг2 + 2 чг5 ) показано на рис. 33, (Ъ). ь 12. [Зд) Алгоритм в упр. 11 сформулирован в форме, которая не совсем пригодна для его реализации в компьютерной программе, Перефразируйте его с более подробным описанием всех операций таким образом, чтобы можно было создать компьютерную программу, которая достаточно эффективно нх бы выполняла. 13. [Мхд] Рассмотрим граф с и вершинами и т ребрами согласно обозначениям нз упр.
6. Покажите, что любую перестановку целых чисел (1,2,..., п) можно представить в виде произведения транспозиций (амЬы ) (аыЬг,)... (амЬм ) тогда и только тогда, когда граф является связным. (Следовательно, существуют множества из п — 1 транспозиций, которые генерируют все перестановки среди и элементов, но никакое множество из п — 2 транспозиций не может этого сделать.) 2.3.4.2. Ориентированные деревья. В предыдущем разделе было показано, что абстрактная блок-схема может рассматриваться как граф, если игнорировать направления стрелок на ребрах. Причем употребляемые в теории графов понятия цикла, свободного дерева и другие могут использоваться для изучения блок-схем. Егце болыпе можно сказать, если учесть направление каждого ребра, так как в этом случае получится "ориентированный граф".
Формально определим ориенгпированнмй граф (Йтесгед дгарЬ или дгдгарЬ) как множество вершин н множество дуг (агсг), каждая из которых проходит от вершины 1' до вершины Г'. Если е является дугой от вершины Г до вершины Г', назовем Г начальной (гпйга() вершиной дуги е, а Г' — конечной (дпа() вершиной и запишем 1' = [п11(е), Г' = Йп(е). При этом возможен случай, когда шй(с) = Йп(е) (хотя прн определении ребра обычного графа он исключается) и несколько различных дуг могут иметь одинаковые начальные и конечные вершины. Сгпепенью выхода (оиб дедгее) вершины Г является количество дуг, которые выходят из нее, в именно— число таких дуг е, что!п[1(е) = Г. Аналогично степень входа ([п-дедгее) вершины Г определяется как количество дуг, для которых Йп(е) =- Г Хотя понятия пути и цикла для ориентированных графов определяются так же, как и для обычных графов, все же следует рассмотреть некоторые важные новые особенности.
Если ег, ег,..., е„являются д1тами (с и ) 1), то будем считать, что (е,,ег,...,е„) являетгя ориентированным путем (опепгед рагй) длины и от вершины Г до вершины Г', если Г = шЫ(ег), Рч = Йп(е„), а Йп(еь) = [п[1(еь+~) для 1 ( й ( и. Ориентированный путь (ег, ег, е„) называется простоим (ггтр(е), если )пИ(ег), ..., 1шс(е„) различны и Йп(ег), ..., Йп(е„) различны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
