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