9. [М22] Ребра ei3 и eig, показанные на рис. 32, расщеплены на две части, поскольку предполагается, что в графе не может быть двух ребер, которые объединяют эти же две вершины. Если взглянуть на окоцчательный результат построения, то расщепление на две части выглядит достаточно искусственным, потому что наряду с двумя соотношениями Е[з = Ei3 и Е[д = Elg в (6) содержатся две независимые переменные: Е[з и Е"д. Объясните, как это построение можно обобщить, чтобы избежать искусственного расщепления ребер.

10. [16] Проектируя электрическую схему компьютера, инженер-электрик приходит к выводу, что необходимо иметь п выводов Ti, Г2,..., Гп с практически одинаковыми значениями рабочего напряжения. Для этого он может спаять провода между любой парой выводов. Смысл этого действия заключается в организации достаточного количества соединений, чтобы существовал путь между любыми двумя вывода.ми. Покажите, что минимальное количество соединений между парами выводов для организации такой сети выводов будет равно п - 1, причем п - 1 соединений между парами выводов позволяют создать такую сеть тогда и только тогда, когда они образуют свободное дерево (в котором выводы и соединения являются вершинами и ребрами).

11. [М27] (R. С. Prim, ВеН System Tech. J. 36 (1957), 1389-1401.) Рассмотрим задачу о соединениях из упр. 10 с дополнительным условием: для каждой пары i < j задается цена с(г, j), которая обозначает затраты на подключение вывода Г к выводу Tj. Покажите, что приведенный ниже алгоритм позволяет получить дерево соединений с минимальной ценой. "Если п = 1, ничего делать не нужно. В противном случае перенумеровать выводы {1,..., п - 1} и цены так, чтобы с(п - 1, п) = mini<i<n с{г, п); соединить выводы Гп-i и Тп; заменить цену c{j, п - 1) ценой min(c(j, п - 1), c{j, п)) для 1 < j < п - 1 н повторить этот алгоритм для 71 - 1 выводов Г1,... ,Гп 1, используя новые цены. (Алгоритм следует повторять, принимая во внимание то, что каждый раз, когда необходимо создать соединение между выводами Г, и Tn-i, соединение на самом деле задается между перенумерованными выводами Tj и Гп, если такое соединение оказывается более дешевым. Таким образом, выводы Гп-1 и Гп в остальной части алгоритма рассматриваются как один вывод.)" Этот алгоритм можно сформулировать и так: "Сначала следует выбрать какой-то один вывод, затем создавать его самое дешевое соединение с другим выводом до тех пор, пока не будут выбраны все выводы".

Рис. 33. Свободное дерево с минимальной ценой.

0 1 2 3 4 5

Рассмотрим, например, рис. 33, (а), на котором показана некоторая сетка с девятью выводами. Пусть цена соединения двух выводов определяется его длиной, а именно - расстоянием между выводами. (Читатель может попытаться вручную найти дерево с минимальной ценой, используя интуицию вместо предложенного алгоритма.) Этот алгоритм соединит сначала выводы Га и Гэ, затем ~ Ге и Ге, Г5 и Ге, Г2 и Ге, Г1 и Г2, Гз и Г1, Г7 и Гз и, наконец, Г4 соединит либо с Гг, либо с Ге. Дерево с минимальной ценой (с длиной провода 7 + 2V2 + 2VE) показано на рис. 33, (Ь).

► 12. [29] Алгоритм в упр. 11 сформулирован в форме, которая не совсем пригодна для его реатизации в компьютерной программе. Перефразируйте его с более подробным описанием всех операций таким образом, чтобы можно было создать компьютерную программу, которая достаточно эффективно их бы выполняла.

13. [М24] Рассмотрим граф с п вершинами и тп ребрами согласно обозначениям из упр. 6. Покажите, что любую перестановку целых чисел {1,2, ...,п} можно представить в виде произведения транспозиций (пкЬк) (oitjb/fcj) • {ок,Ьк,) тогда и только тогда, когда граф является связным. (Следовательно, существуют множества из п - 1 транспозиций, которые генерируют все перестановки среди п элементов, но никакое множество из 7i - 2 транспозиций не может этого сделать.)

2.3.4.2. Ориентированные деревья. В предыдущем разделе было показано, что абстрактная блок-схема может рассматриваться как граф, если игнорировать направления стрелок на ребрах. Причем употребляемые в теории графов понятия цикла, свободного дерева и другие могут использоваться для изучения блок-схем. Еп;е больше можно сказать, если учесть направление каждого ребра, так как в этом случае получится "ориентированный граф".

Формально определим ориентированный граф (directed graph или digraph) как множество вершин и множество дуг (arcs), каждая из которых проходит от вершины V до вершины V. Если е является дугой от вершины V до вершины V, назовем

V начальной (initial) вершиной дуги е, а V - конечной (final) врршиной и запишем

V = init(e), V = fin(e). При этом воз.можен случай, когда init(e) = fin(e) (хотя при определении ребра обычного графа он исключается) и несколько различных дуг могут иметь одинаковые начальные и конечные вершины. Степенью выхода (out-degree) вершины V является количество дуг, которые выходят из нее, а именно - число таких дуг е, что init(e) = V. Аналогично степень входа (in-degree) вершины V определяется как количество дуг, для которых fin(e) = V.

Хотя понятия пути и цикла для ориентированных графов определяются так же, как и для обычных графов, все же следует рассмотреть некоторые важные новые особенности. Если ei,e2,. -. ,е„ являются дуг&ми (с п > 1), то будем считать, что (ei,e2,... ,е„) является ориентированным путем (oriented path) длины п от вершины V до вершины V, если V - init(ei), V = fin(e„), а йп(ек) = init(e)fc+i) для 1 < к < п. Ориентированный путь (ci, 62,..., е„) называется простым (simple), если init(ei), init(e„) различны и fin(ei), fin(e„) различны. Ориентированный цикл (oriented cycle)-это простой ориентированный путь от некоторой верпшны до нее са.мой. (Ориентированный цикл может иметь длину 1 или 2, хотя такие короткие циклы были исключены из определения цикла в предыдущем разделе. Может ли читатель объяснить, зачем это было нужно?)

Для демонстрации данных определений рассмотрим рис. 31 из предыдущего раздела. Блок с ярлыком "J" является вершиной со степенью входа 2 (в нее входят две дуги 616, 621) и степенью выхода 1. Последовательность (617,619,618,622) является ориентированным путем длины 4 от вершины J до вершины Р. Однако этот путь не является простым, например, потому что init(6i9) = L = init(622). Такая схема не содбржит ни одного ориентированного цикла длины 1, но (618,619) является ориентированным циклом длины 2.

Ориентированный граф называется строго связным (strongly connected), если существует ориентированный путь от вершины V до вершины V для любых двух

вершин Уф V. Он является корневым (rooted), если существует хотя бы один корень (root), т. е. по крайней мере одна такая вершина R, при наличии которой существует ориентированный путь от V к.К для всех V ф R. "Строго связный" граф всегда является "корневым", но обратное утверждение не верно. Блок-схема, показанная на рис. 31 в предыдущем разделе, является примером корневого диграфа (т. е. корневого ориентированного графа), корень R которого соответствует вершине-блоку "Начало". Причем, добавляя дугу от блока "Конец" до блока "Начало" (см. рис. 32), получим строго связный граф.

Каждый ориентированный граф G, очевидно, соответствует обыкновенному графу Go, если игнорировать ориентации и исключить двойные ребра или циклы. Формально выражаясь, граф Go содержит ребро от вершины V до вершины V тогда и только тогда, когда УфУ п граф G имеет дугу от вершины V до вершины V или от вершины V до вершины V. Рассматривая (неориентированные) пути и циклы в графе G, мы подразумеваем, что они являются путями и циклами графа Go. При этом граф G назовем связным, если соответствующий граф Go является связным (т. е. рассматриваемое свойство не только "слабее" свойства "строго связный", но и еще слабее, чем свойство "корневой").

Ориентированное дерево (oriented tree) (рис. 34), иногда называемое некоторыми автора.ми корневым деревом, представляет собой ориентированный граф с такой вершиной R, что:

a) каждая вершина V ф R является начальной вершиной в точности одной дуги, которая обозначается как e[V];

b) R не является начальной вершиной ни одной из дуг;

c) R является корнем в указанном выше смысле (т. е. для каждой вершины V ф R существует ориентированный путь otV к R).

Отсюда немедленно следует, что для каждой вершины V ф R существует единственный ориентированный путь от У к i?, а значит, ориентированных циклов не существует.

Легко видеть, что предыдущее определение ориентированного дерева (приведенное в начале раздела 2.3), не противоречит новому определению только в том случае, когда имеется конечное множество вершин. При этом вершины отвечают узлам, а дуга е\у] - это связь между V и PARENT [V].

Соответствующий ориентированному дереву (неориентированный) граф является связным вследствие свойства (с). Более того, он не имеет циклов. Действительно, если (Vo,Vi,... ,Vn) является неориентированным циклом с п > 3 и если e[Fi]-это ребро между Vq и Т, то е[2]-это ребро между Vi и V2 и аналогично е[Т4] - это ребро между Т4 1 и Т4 для \ < к < п, что противоречит отсутствию ориентированных циклов. Если ребро между Vq и Vi не равно e[Fi], то оно должно быть равно e[Vo]. Тот же аргумент относится к циклу

Рис. 34. Ориентированное дерево.

(Vi,Vo,Vn-u...,Vi),