Понятие графа. Задача Эйлера. Задача Гамильтона

Лемма о рукопожатиях

Подозреваемый рассказал Шерлоку Холмсу о произошедшем на зва­ном приеме, начав с утверждения: «Нас было пятнадцать человек, и каж­дый из нас за этот вечер познакомился с пятерыми...» Однако Холмс пре­рвал его речь: «Этого просто не могло быть! Вы лжете!» В итоге подозре­ваемый сознался в совершении преступления. После Ватсон поинтересовался у Холмса: «Но как вы узнали, что он лжет?» «Элемен­тарно, Ватсон, - ответил Холмс, - все дело в лемме о рукопожатиях»...

Лемма о рукопожатиях.Сумма степеней вершин графа всегда четна и равна удвоенному числу ребер, то есть , где d_i – степень i-ой вершины графа.

Доказательство.Поскольку каждое ребро графа имеет две вершины, степень каждой вершины увеличивается на единицу за счет одного ребра. Таким образом, в сумму степеней всех вершин каждое ребро вносит две едини­цы, поэтому сумма должна в два раза превышать число ребер. Следова­тельно, сумма является четным числом.

Действительно, если вернуться к истории с Холмсом и подозревае­мым, то пятнадцать присутствующих на приеме человек можно ассоциировать с вершинами графа, а их новые знакомства - с ребрами. Если ве­рить подозреваемому, то степень каждой вершины графа должна быть равна пяти. Следовательно, сумма степеней всех вершин графа с 15 вер­шинами степени 5 равна 75. Получено нечетное число, значит, такого графа не существует. Этот факт и навел Холмса на мысль, что свидетель лжет.

Следствие. Влюбом графе количество вершин нечетной степени четно.

Доказательствопроведем методом от противного. Предположим, что утверждение не верно, и найдем противоречие, из которого будет сле­довать, что теорема справедлива. Если теорема не верна, то имеется не­четное количество вершин, степени которых нечетны. Но сумма степеней вершин с четными степенями четна. Сумма степеней всех вершин есть сумма степеней вершин с нечетными степенями плюс сумма степеней вершин с четными степенями. Поскольку сумма нечетного числа и четно­го числа есть число нечетное, то сумма степеней всех вершин нечетна. Но это противоречит лемме о рукопожатиях. Имеем противоречие. Следова­тельно, делаем вывод, что утверждение справедливо.

Например, проверим выполнение соотношения (1) для графа,

Рис. 6.

изображенного на рис. 6. Для этого подсчитаем число инцидентных ребер для каждой из вершин:

А₁=2, А₂=4, А₃=3, А₄=5, А₅=3, А₆=4, А₇=3.

Тогда

.

Число дуг в этом графе равно 12, то есть m=12. Таким образом, соотношение (1) выполняется.

Эйлер установил, что граф, в котором существует путь, перемещаясь по которому можно пройти все его ребра, проходя по каждому ребру графа ровно один раз, должен иметь либо только четные вершины, либо ровно две нечетных (все остальные вершины графа должны быть четными). Такой граф стали называть эйлеровым. Во всех других случаях обойти граф целиком возможно, лишь проходя по некоторым ребрам не один раз.

Более того, если в графе ровно две нечетные вершины, то такой путь должен непременно начинаться в одной из этих вершин, а заканчивать­ся в другой. Если же все вершины графа четны, то начало и конец пути непременно должны совпадать, иными словами, искомый путь должен быть замкнутым.

Полученное Эйлером решение может быть применено к известным задачам-головоломкам: нарисовать некую фигуру не отрывая руки и не проходя дважды по уже нарисованной линии. Например, изобразить подобным образом прямоугольник с диагоналями, приведенный на рис. 4 не возможно.

Рис. 4

Для доказательства этого факта будем рассматривать фигуру, изображенную на рис. 4 как граф. Таким образом, все четыре угловые вершины графа являются нечетными (из них выходит по три дуги) и только одна, центральная вершина будет являться четной, так как из нее выходит четырем дуги, что будет противоречить условию, полученному Эйлером. И, таким образом, оказывается, что фигуру, изображенную на рис. 4 не возможно изобразить не отрывая руки и проводя каждую линию только один раз.

В тоже время, фигура, изображенная на рис. 5, удовлетворяет условиям, полученным Эйлером, так как у этой фигуры четыре вершины четные и две, лежа-

Рис. 5

щие внизу, нечетные. Следовательно, для выполнения поставленной задачи необходимо начинать изображение фигуры с нижних вершин.

Таким образом, если указанные выше условия выполнены, то задача имеет, как правило, не одно решение — обходов графа может быть довольно много, но число пройденных при этом ребер будет всегда одним и тем же.

Известен простой алгоритм построения подобного обхода в тех си­туациях, когда этот обход возможен.

Свои выводы Эйлер сформулировал в виде следующей теоремы

Теорема Эйлера. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Обозначим n_k – число вершин, имеющих степень k. Известно, что

= 2 m. (2)

Уравнения (1) и (2) принадлежат классу диофантовых уравнений (то есть алгебраических уравнений, решение которых ищется в целых числах), что является одним из свидетельств глубокой взаимосвязи между теорией графов и теорией чисел. Отметим, что существование решений этих уравнений является необходимым, но не достаточным условием существования соответствующих графов.

Для ориентированных графов для каждой вершины можно ввести два числа – полустепень исхода (число выходящих из нее вершин) и полустепень захода (число входящих в нее вершин). В дальнейшем, если не оговорено особо, будем рассматривать графы без петель, то есть без дуг, у которых начальная и конечная вершины совпадают.

Определим матрицу смежности графа как квадратную матрицу n ´ n, элемент a_ij которой равен единице, если (i, j) Î V, и нулю, если (i, j) V, i, j Î X. Для неориентированного графа матрица смежности всегда симметричная.

Определим матрицу инциденций для ребер графа как прямоугольную матрицу n ´ m, элемент r_ij которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = , j = . Аналогично определяется матрица инциденций для дуг графа - как прямоугольная матрицу m ´ n, элемент r_ij которой равен плюс единице, если дуга U_j исходит из вершины i, минус единице, если дуга U_j заходит в вершину i, и нулю в остальных случаях, i = , j = .

Пути и маршруты в графах

Существует большое разнообразие задач, связанных с пу­тями и маршрутами в графе, начиная от стандартных задач на существование, пересчет и перечисление и кончая задачами поиска путей, отвечающих определенным требованиям. Таки­ми требованиями могут быть максимальность или минималь­ность длины, пропускной способности или надежности пути требования к множеству вершин, принадлежащих или не при­надлежащих пути, и т.п. Кроме того, сами графы могут иметь определенные свойства, например быть или не быть ориенти­рованными, циклическими, взвешенными и т.д. Наконец один и тот же граф может быть описан по-разному.

Рассмотрим задачу пересчета путей и маршрутов.

Следует отметить, что задача определения числа путей (маршру­тов) длины 2 между всеми парами вершин графа может быть решена простым возведением в квадрат его матрицы смежности. Аналогично, количество маршрутов длины 3 может быть получено из матрицы A³ и вообще количество маршрутов длины l между вершинами v_i и v_j равно соответствующему элементу матриц A^l. Наконец количество маршрутов длиной не более p между всеми парами вершин определяется как сумма

Пример. В качестве примера приведем решение задачи пересчета маршрутов графа, приведенного ниже при l=1,2,3,4.

Рис. 1.

Информацию о путях в одну дугу для графа изображенного на рис. 1 несет матрица смежности А, остальные матрица получаем простым умножением:

Непосредственной проверкой по изображению графа убеждаемся, что, например, между cиe есть

1 маршрут (путь) длины 2: c→b→e;

1 маршрут длины 3: c→e→c→e;

4 маршрута длины 4: c→b→e→c→e, c→b→d→c→e, e→a→b→e→c,

e→c→b→d→c.

К сожалению, таким образом определяется число маршрутов связывающих пару вершин, а не число путей, которые представляют наибольший интерес Количество путей можно определить если найти все маршруты и отбросить те из них, где есть повторяющиеся фрагменты, т.е. необходимо решать задачу перечисления маршрутов. Прежде чем перейти к этой задаче, отметим два факта касающихся задачи пересчета:

1. Отличные от нуля диагональные элементы матриц указывают на присутствие в графе соответствующего количества циклов длины l. Например, в матрице A³ диагональный элемент . Это значит, что в графе есть три цикла длины 3, включающие вершину b. Непосредственно по рисунку находим: b→d→c→b, b→e→c→b и b→e→a→b.

2. Поскольку длина пути в графе не может превышать
n—1,не имеет смысла возводить A в более высокую степень

Перечисление маршрутов и путей

Матричный подход, использованный в предыдущих разделах, легко адаптируется к задаче о перечислении маршрутов

Пусть - матрица всех маршрутов с l промежуточны­ми вершинами (длины l+1), элементы которой определяются как

где v_kl это l-япо порядку промежуточная вершина маршрута связывающего v_i и v_j, a q - ко­личество таких маршрутов. Если маршрутов длины l+1 меж­ду v_i и v_j нет, то . Слагаемые v_k1 v_k2 … v_kl представляют собой "произведения" вершин, лежащих на некотором маршруте между v_i и v_j. Их можно рассматривать как размещения без повторений или с повторениями из n элементов по l в зависимости от того, является маршрут путем или нет

Например, для графа на рис. 4. и значит из v_i в v_j есть три маршрута: c→b→e→a→d, c→e→a→b→d и c→e→c→b→d, два из которых являются путями, так как не содержат повторяющихся вершин. В наличии указанных маршрутов легко убедиться непосредственно по графу, а их количество равно значению элемента в матриц A⁴. Кроме P^(l), используем вспомогательную матриц , в которой элемент равен v_j, если в графе есть дуга v_iv_j, и 0, еcли дуга отсутствует. Поскольку j-столбец P^(l-1) отражает все маршруты длины l, с началом в v_k (k=1,2,…,n)и концом в v_j, а i-строка - концы всех дуг вида v_iv_k (k=1,2,…,n), то сумма

,

отражает все маршруты из v_i в v_j длины l+1. Следовательно, матрица маршрутов P^(l)может быть получе­на как х P^(l-1), при этом сомножители в произведениях не переупорядочиваются и не используется степенная запись повторяющихся сомножителей, чтобы не потерять инфор­мацию о порядке следования вершин. Таким образом, может быть сформирован ряд матриц P⁽¹⁾, P⁽²⁾, P⁽³⁾, ..., P^(q-1), в совокупности определяющих все маршруты длины не больше q для любой пары вершин.

В качестве примера выполним расчеты для графа, предс­тавленного на рис. 1 используя соотношения:

P⁽¹⁾= P⁽⁰⁾, P⁽²⁾= P⁽¹⁾, P⁽³⁾ = P⁽²⁾.

За матрицу P⁽⁰⁾ (пути без промежуточных вершин), необхо­димую для получения P⁽¹⁾, примем матрицу смежности.

Наконец для P⁽³⁾ = P⁽²⁾ матрица принимает вид

	a	b	c	d	e
a	dce	bea+bdc+bec	dce	bea+dcb	dcb+bdc+bec
b	dce+ece	0	ead+dce+ece	eab+dcb+ecb	eab+dcb+ecb
c	ece	bea+bdc+bec	ead+ece	bea+eab+ecb	eab+ecb+ +bdc+bec
d	cbe	cea+cec	cbd+cbe	cea	cec
e	abe+cbe	cea+adc+cec	abd+cbd+ +abe+cbe	cea	adc+cec

К видно из примера, уже при небольших значениях l матрицы могут быть весьма громоздкими. Однако, если цель поиска - пути, объем вычислений можно существенно умень­шить, отбрасывая произведения с повторяющимися вершина­ми. Очевидно также, что в этом случае l ≤ (n—2), так как путь в графе не может содержать более чем n—2 промежуточных вершин. Кроме того, с увеличением длины количество путей в общем случае должно сокращаться.

Задача Гамильтона

В 1859 году Гамильтон предложил вла­дельцу фабрики игрушек в Дублине необычную головоломку, основной частью которой был деревянный додекаэдр (правильный двенадцатигранник, имеющий 20 вершин и тридцать ребер. Каждая грань представляет собой правильный пятиугольник.). В каждую вершину додекаэдра, поме­ченную названием одного из известных горо­дов (Брюссель, Дели, Франкфурт и т. д.), был вбит гвоздик и к одному из них была привяза­на нить. Требовалось соединить вершины додекаэдра этой нитью так, чтобы она прохо­дила вдоль его ребер, обвивая каждый гвоздик ровно один раз, и чтобы полученный в результате ниточный маршрут был замкнутым (циклом).

Владелец фабрики принял предложение Гамильтона и выплатил ему 25 гиней.

Гамильтон рассматривал задачу, в которой нужно было, проходя по ребрам додекаэдра, посетить все его вершины.

Ясно, что минимальное число вершин додекаэдра, которые нужно посетить, проходя по его ребрам с тем, чтобы пройти все, не меньше числа его вершин.

Гамильтон показал, что для додекаэдра эти числа равны. Однако описать все множество графов, допускающих существование путей, пе­ремещаясь по которым можно обойти все узлы, побывав в каждом ровно один раз, не удалось до сих пор. Нет и эффективного алгоритма.

Конечно, задача может быть решена перебором, так как обычно речь идет о графах с конечным числом вершин, но объем вычислений в по­давляющем большинстве случаев слишком велик.

С этой задачей тесно связана проблема моряка, часто называемая так­же задачей о странствующем торговце (коммивояжере), который должен посетить определенный набор городов и вернуться домой как можно скорее. Довольно большой пример определения замкнутой воздушной линии, соединяющей столицы 48 штатов США и имеющей наименьшую возможную длину, был просчитан до конца.

Интересно отметить, что обе эти разделенные более чем столетием задачи являются оптимизационными.

Отдавая дань уважения Эйлеру и Гамильтону, всякий граф, у кото­рого есть замкнутый путь, проходящий через каждое его ребро в точно­сти по одному разу, стали называть эйлеровым, а всякий граф, у которого есть замкнутый путь, проходящий через каждую его вершину в точности один раз, гамильтоновым.

Примеры приложений теории графов

Приведем ряд примеров приложений теории графов (более подробное описание перечисляемых и других задач приводится ниже и в литературе, указанной в соответствующих ссылках).

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках [5, 8, 20].

2. Задача о спросе и предложении. Оптовый торговец в каждый из N последо­вательных интервалов может покупать, продавать и хранить (чтобы продать позже) некоторый товар. Причем в каждый i период задаются: верхняя граница а_i- коли­чества товара, больше которого торговец купить не может: верхняя граница С_j-количества товара, которое он может хранить, и нижняя граница b_i количества товара, которое он может продать. Заданы стоимости покупки, продажи и храпе­ния is каждый 1-й период. Требуется определить оптимальную стратегию торговца, при которой он получит максимальную прибыль за N периодов.

3. Задача об оптимальном использовании дорог. Из различных городов Xi (i= 1, 2, ..., n) в пункт назначения у отправляются машины (при заданном начальном количестве a_i- машин в пункте x_i). Заданы продолжительности t_ijдвижения автомобплей по дорогам между пунктами x_iи х_j, максимальное ко­личество машин Cij, которое может пропустить эта дорога; максимальное коли­честв) машин Сii, которое может находиться в пункте хi. Требуется составить оптимальный план движения автомобилей таким образом, чтобы в течение вре­мен Т в пункт назначения у прибыло максимальное число автомашин.

4. Задача о кратчайшем пути. Пусть задана транспортная сеть, в которой имеются исток и сток. Дли каждой дуги указаны стоимости проезда (может быть указан километраж или время проезда).

Требуется найти путь, соединяющий начальною и конечную точки, суммар­ная стоимость проезда, по которому была бы минимальна.

5. Задача об оптимальной па значении. Требуемся распределить п рабочих по m машинам при известной производительности труда каждого рабочего на каждой машине таким образом, чтобы общая производительность труда была максимальной.

6. Задача о складе. Пусть задана емкость склада: количество товара, помещен­ное вначале; цены на товары, покупаемые и продаваемые в каждый i-й период времени, и расходы в этот период, связанные с храпением единицы товара. Тре­буется определить оптимальные количества товара, которые должны быть куп-лены и проданы в разные периоды времени таким образом, чтобы суммарная прибыль за N периодов была максимальна. Причем считается, что количества товара па складе в начале и в конце процесса купли — продажи равны между собой.

7. Задача о поставщике. Поставщик салфеток точно знает, сколько ему потре­буется свежих салфеток на каждый из последующих дней. Он может выбрать одну из двух или обе следующие стратегии: покупать новые салфетки или поль­зовался салфетками, выстиранными в прачечной. В прачечной бывает срочное обслуживание и обычное, причем последнее при большей длительности стирки стоит меньше, чем первое. Зная цену новых салфеток и стоимость стирки, тре­буется при каком-то начальном количестве салфеток определить оптимальную стратегию, при которой поставщик будет обеспечивать потребителей необходимым числом салфеток при минимальных издержках в течение N дней.

8. Задача об оптимальном по стоимости сетевом графике. Задай сетевой график работы с общей продолжительностью t_n. Считаем, что для каждой работы, которая представляется дугой, зависимость ее стоимости от продолжительности линейна. Требуется минимизировать полную стоимость проекта при заданной общей про­должительности работ.

9. «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги – потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков [15, 20, 24].

10. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями [7, 12, 18].

11. Управление проектамиУправление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений). С точки зрения теории графов проект – совокупность операций и зависимостей между ними (сетевой график - см. ниже). Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

12. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности взаимодействия, и др.

Задача почтальона.Пусть G связный граф, имеющий k вершин нечетной сте­пени и заданный матрицей весов ребер. Требуется найти крат­чайший замкнутый маршрут проходящий по всем ребрам графа. В качестве приложений где может потребоваться решение этой или сходной задачи, можно указать контроль различных коммуникационных сетей (дорожных, электрических, газовых и т.п.), когда необходимо проверять все протяженные компо­ненты сети В литературе по теории графов сформулирован­ная выше задача называется задачей почтальона. Последнему далеко не безразлично знание наиболее короткого замкнутого маршрута обхода всех улиц своего участка (или некоторого их подмножества). Аналогичная задача стоит и перед курьером большого учреждения, доставляющим документы от одного источника к различным получателям.

Понятие дерева

Важный класс графов составляют графы, называемые деревьями. Дерево — это связный граф, который вовсе не имеет замкнутых путей (рис. 7).

Этот граф обладает следующим оптимальным свойством: среди всех связных графов с данным числом вершин дерево имеет наименьшее число ребер, а именно: число n вершин дерева и число m его ребер различаются на единицу

m = n - 1. (3)

Рис. 7

Если граф — конечный и связный, то легко построить дерево (и, как правило, не одно), множество вершин которого совпадало бы с множе­ством всех вершин заданного графа, а все ребра дерева одновременно были бы ребрами этого графа.

Это можно сделать, например, так. Пометим произвольную вершину графа, выберем какое-нибудь исходящее из нее ребро графа и пометим вершину, в которую это выбранное ребро входит. Если пара помеченных вершин не исчерпывает множества всех вершин графа, выбираем ребро графа, выходящее из одной из двух этих вершин в какую-нибудь третью непомеченную вершину этого графа, и помечаем ее. В случае если полу­ченная тройка помеченных вершин не исчерпывает множества всех вер­шин графа, выбираем ребро графа, выходящее из одной из трех этих вершин в какую-нибудь четвертую непомеченную вершину этого графа, и помечаем ее. Продолжая описанную процедуру далее, мы неизбежно придем к ситуации, когда все вершины заданного графа окажутся помеченными. Напомним, что число вершин графа конечно, и если оно равно п, то потребуется ровно п — 1 шаг, на каждом из которых (кроме первого) помечается ровно одна новая (непомеченная) вершина графа. Множество выбранных ребер и помеченных вершин будет искомым де­ревом.

Всякое такое дерево называют деревом, порождающим граф, или по­рождающим деревом графа, или остовом графа, или его стягивающим ос­товом.

На рис. 8 последовательно (шаг за шагом) показано построение по­рождающего дерева для графа с семью вершинами.

Рис.8

Ясно, что порождающих деревьев у конечного связного графа может быть много. В частности, если граф — полный (любые две вершины соединены ребром), то число порождающих деревьев равно п^n-2, где n—число его вершин.

Часто приходится рассматривать задачи, в которых каждому ребру заданного графа приписано некоторое положительное (неотрицатель­ное) число (его вес). Обычно граф, нагруженный подобным образом, называют сетью, его вершины узлами, а ребра дугами.

В зависимости от приложений описанная числовая нагрузка дуги графа может иметь разный смысл и обозначать длину, стоимость, про­пускную способность, временную протяженность и т. д.

Алгоритма Прима

Опишем алгоритм, предложенный Примом [8], считая, что число вершин заданного графа п > 2. Этот алгоритм приводит к искомо­му результату за п — 1 шаг.

1-й шаг. Пометим произвольную вершину графа. Из ребер инцедентных этой вершине, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, и которую входит это выбранное ребро. В результате две вершины графа оказываются помеченными.

Если других вершин в графе нет, то искомое порождающее дерево построено (обозначим его через Т)и поставленная задача решена. И противном случае потребуется новый шаг.

2-й шаг. Рассмотрим все ребра инцедентные помеченным вершинам, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наи­меньшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результа­те выделенными оказываются два ребра графа, а помеченными уже три его вершины. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребу­ется новый шаг.

3-й шаг. Рассмотрим все ребра инцедентным помеченным вершинам, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наи­меньшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате выделенными оказываются три ребра графа, а помеченными уже четыре его вершины.

Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребу­ется новый шаг.

На каждом шаге и число выделенных ребер графа, и число помеченных вершин увеличиваются ровно на единицу. Тем самым, по­сле п — 1-го шага количество выбранных ребер станет равным п — 1 и все п вершин графа окажутся помеченными.

Первый шаг можно начинать с ребра наименьшей длины. Его легко найти путем простого перебора всех ребер графа. Если таких ребер несколько, выберем любое из них и пометим концы выбранного ребра. В результате две вершины графа окажутся помеченными. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребуется новый шаг, совпадающий со 2-м шагом алгоритма, предложенного выше [9].

Задача о кратчайшем пути

Пусть задана сеть из n+1 вершины, то есть ориентированный граф, в котором выделены две вершины - вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.

Теорема 1 [8]. Для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной.

Известно, что в сети без контуров всегда существует правильная нумерация.

Обозначим l_ij – длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

Шаг 0: Помечаем нулевую вершину индексом l₀ = 0;

Шаг k: помечаем вершину k индексом l_k = (l_i + l_ik).

Индекс выхода l_n будет равен длине кратчайшего пути.

Пример Рассмотрим работу алгоритма определения кратчайшего пути для сети изображенной на рис. 12 (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).

Шаг 0. Вершине 0 присваиваем индекс равный 0.

Шаг 1. Рассматриваем вершину 1. Индекс вершины равен

λ₁ =min(λ₀ +l₀₁)=0+3=3

Рис. 12. Поиск кратчайшего пути

Шаг 2. Рассматриваем вершину 1. Индекс вершины равен

λ₁ =min(λ₀+l₀₁)=0+3=3

Шаг 3. Рассматриваем вершину 3. Индекс вершины равен

λ₃ =min(λ₁+l₁₃; λ₂+l₂₃)=min(3+8;8+2)=10

Шаг 4. Рассматриваем вершину 4. Индекс вершины равен

λ₄ =min(λ₂ +l₂₄)=8+1=9

Шаг 5. Рассматриваем вершину 5. Индекс вершины равен

λ₅ =min(λ₃ +l₃₅; λ₄ +l₄₅)=min(10+4;9+6)=14

Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь m = (0; i₁; i₂; ...; i_n-1; n), такой, что = l_n - l_n-1 и т.д.

Осуществляя обратный ход для рассматриваемого примера получаем:

λ₅= λ₃+l₃₅;

λ₃= λ₂+l₂₃;

λ₂= λ₁+l₁₂;

λ₁= λ₀+l₀₁;

Таким образом, кратчайший путь проходит через вершины:

0→1→2→3→5

и имеет длину равную 14.

Следующий алгоритм дает возможность определять кратчайший путь в общем случае (то есть при произвольной нумерации вершин).

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом l₀ = 0, все остальные вершины индексами l_i = +¥, i = ;

Шаг k: Рассматриваем все дуги. Для дуги (i; j), если l_j - l_i >l_ij, то вычисляем новое значение = l_i + l_ij.

Индексы устанавливаются за конечное число шагов. Обозначим { } – установившиеся значения индексов, которые обладают следующим свойством: величина равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

Пример. Рассмотрим пример работы алгоритма Форда для сети с произвольной нумерацией вершин для сети изображенной на рис. 13.

Рис. 13. Поиск кратчайшего пути для алгоритма Форда

Шаг 0. λ₀=0; λ₁=∞; λ₂=∞; λ₃=∞; λ₄=∞; λ₅=∞.

Шаг 1. Рассматриваем дугу (0;1). Вычисляем соотношение λ₁ – λ₀=∞. Проверяем выполнение условия (λ₁ – λ₀)>l₀₁. Соотношение выполняется, поэтому вычисляем новое значение λ₁

λ₁=(λ₀ +l₀₁)=0+3=3

Шаг 2. Рассматриваем дугу (0;2). Вычисляем соотношение λ₂ – λ₀=∞. Проверяем выполнение условия (λ₂ – λ₀)>l₀₁. Соотношение выполняется, поэтому вычисляем новое значение λ₂: λ₂=(λ₀ +l₀₂)=0+9=9

Шаг 3. Рассматриваем дугу (1;3). Вычисляем соотношение λ₃ – λ₁=∞. Проверяем выполнение условия (λ₃ – λ₁)>l₁₃. Соотношение выполняется, поэтому вычисляем новое значение λ₃: λ₃=(λ₁ +l₁₃)=3+8=11

Шаг 4. Рассматриваем дугу (3;2). Вычисляем соотношение λ₂ – λ₃=9 – 11= - 3 . Проверяем выполнение условия (λ₂ – λ₃)>l₃₂. Соотношение не выполняется, поэтому новое значение λ₂ не вычисляется.

Шаг 5. Рассматриваем дугу (2;1). Вычисляем соотношение λ₁ – λ₂=3 – 9= - 6. Проверяем выполнение условия (λ₁ – λ₂)>l₂₁. Соотношение не выполняется, поэтому новое значение λ₁ не вычисляется.

Шаг 6. Рассматриваем дугу (2;4). Вычисляем соотношение λ₄ – λ₂=∞. Проверяем выполнение условия (λ₄ – λ₂)>l₂₄. Соотношение выполняется, поэтому вычисляем новое значение λ₄: λ₄=(λ₂ +l₂₄)=9+1=10

Шаг 7. Рассматриваем дугу (3;5). Вычисляем соотношение λ₅ – λ₃=∞. Проверяем выполнение условия (λ₅ – λ₃)>l₃₅. Соотношение выполняется, поэтому вычисляем новое значение λ₅: λ₅=(λ₃ +l₃₅)=11+4=15

Шаг 8. Рассматриваем дугу (4;5). Вычисляем соотношение λ₅ –λ₄=15 – 10 =5. Проверяем выполнение усло