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

Доказательство. Предположим, что мы начинаем цепь Z из некоторой вершины А и продоллжаем ее настолько далеко, насколько это возможно, проходя каждый раз по ребру, еще не пройденному ранее. Ввиду конечности ребер этот процесс когда-нибудь закончится. Но так как в каждой вершине четное число ребер, то из каждой вершины, за исключением начальной, будет возможен и выход. Следовательно, цепь Z должна кончаться в вершине А.

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

Теперь мы начнем новую цепь R из вершины В используя только ребра, не принадлежащие Z. Ясно, что эта цепь должна оканчиваться в точке В. Присоединяя эту цепь к предыдущему циклу, получим большой цикл. Продолжаем этот процесс до тех пор, пока не исчерпаем все ребра.

Предположим, что на графе имеется цепь Z(A,B), содержащая все его ребра в точности по одному разу. Для этого необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.

Для доказательства достаточно добавить к графу новое ребро АВ; тогда все его вершины станут четными. Новый граф, согласно предыдущей теореме, обладает некоторой эйлеровой линией Р; если ребро АВ удалить из Р, останется искомая цепь Z(AB).

Отыскание правильного пути

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

Для доказательства мы дадим общее правило построения цепи, проходящей вдоль всех ребер графа в точности по одному разу в каждом направлении. Мы начнем эту цепь из произвольной вершины А₀ и пойдем вдоль некоторого ребра Е₀=(А₀,А₁), отметив это ребро маленькой стрелкой, поставленной в точке А₁ и указывающей выбранное нами направление. Затем перейдем последовательно к другим вершинам. Одни и те же вершины можно посещать и по нескольку раз. Каждый раз, попадая в какую-нибудь вершину, мы будем ставить на соответствующем ребре стрелку, указывающую направление прибытия. Кроме того, попадая в какую-нибудь вершину впервые, мы как-нибудь особо отметим входящее ребро, так чтобы потом его можно было отличить от остальных.

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

Мы продолжаем этот путь до тех пор, пока это вообще возможно. В каждой вершине имеется одинаковое число возможностей для входа и выхода. Поэтому процесс может окончиться только в начальной вершине А₀. Остается проверить, что во всех направлениях все ребра будут пройдены в обоих направлениях.

В точке А₀ это ясно - все выходящие ребра здесь будут использованы, так как в противном случае мы могли бы двигаться дальше, поэтому и все выходящие ребра тоже будут использованы, так как их число равно числу выходящих ребер. В частности, ребро Е₀= (А₀,А₁) будет пройдено в обоих направлениях. Но это означает, что все ребра, инцидентные А₁, тоже будут пройдены в обоих направлениях, так как первое входящее в А₁ ребро А₀А₁, по условию, должно использоваться в качестве выходящего лишь в последнюю очередь. То же самое рассуждение применимо и к следующему ребру Е₁=(А₁,А₂) и к следующей вершине А₂ и т.д.

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

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

 

Упражнения

 

1. Примените изложенный здесь прием к графам, рассмотренным в § 1, гл.1.

Гамильтоновы линии

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

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

“Задача о коммивояжере” напоминает задачу о разыскании гамильтоновых линий - и снова мы не знаем никакого общего метода ее решения. Предположим, что коммивояжер, прежде чем вернуться домой, должен посетить несколько городов. Естественно, он заинтересован в том, чтобы сделать это с наименьшими затратами. Всегда можно, конечно решить эту задачу посредством последовательных испытаний, находя необходимое время, расстояние или стоимость для различных возможных порядков обхода городов. Однако для большого числа городов это становится почти невозможным. Тем не менее для некоторых достаточно громоздких примеров это сосчитано. Так, например, найденв кратчайшая циклическая аэролиния, проходящая по всем главным городам Соединенный Штатов.

 

Упражнения

 

1. Имеются ли гамильтоновы линии на графах, изображенных на рис.1 и 2?

 

2. Торговец, живущий в городе А₁, собирается посетить города А₂, А₃, А_4. Расстояния между городами таковы:

 

А₁А₂ = 120; А₁А₃ = 140; A₁А₄ = 180;

А₂А₃ = 70; А₂А₄ = 100; А₃А₄ = 110;

 

ДЕРЕВЬЯ

Деревья и леса

Деревом называется связный граф, не содержащий циклов.

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

Для того, чтобы построить дерево, выберем какую-нибудь вершину А_0.

А₀ А₃

А₁

А₁₃ А₂₁ А₂ А₂₃

А₁₂А₂₂

А₁₁

рис. 20

Из А₀ проведем ребра в соседние вершины А₁, А₂,..., из них проведем ребра к их соседям А₁₁, А₁₂,..., А₂₁, А₂₂,... и т.д., как показано на рис.20. Первоначально выбранная вершина А₀ называется корнем дерева; каждая вершина дерева может служить его корнем.

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

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

Теорема: Дерево с n вершинами имеет n-1 ребер.

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

Теорема: Лес, состоящий из К компонент и имеющий n вершин, содержит n-k ребер.

 

 

рис. 21. Лес

 

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

Циклы и деревья.

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

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

 

 

 

рис. 22.

 

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

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

Дерево Т содержит то же самое число вершин n, что и первоначальный граф G. В силу теоремы о числе ребер дерева нам из первоначального числа ребер графа G пришлось удалить

g =N-n+1

ребер. Это число называется циклическим порядком, или цикломатическим числом графа.

Проиллюстрируем это превращение графа в дерево на рис 23

 

А

 

F B

 

 

C

E D

рис. 23

Удалим сначала ребро ЕD, принадлежащее циклу EFD, затем ребро AD, принадлежащее циклу DFA, и, наконец, ребра AC и BE. Остается дерево, изображенное на рис.38. Всего мы удалили

g =9-6+1=4 ребра.

Упражнения

1. Проверьте результаты этого параграфа на графах рис.2 и 22.

2. Чему равно цикломатическое число полного графа?

 

Задача о соединении городов

Имеется несколько городов A, B, C,..., которые нужно соединить между собой сетью шоссейных или железнодорожных дорог. Для каждой пары городов А,В известна стоимость С(А,В) строительства соединяющей их дороги. Задача состоит в том, чтобы построить самую дешевую из возможных сетей дорог.

Граф наиболее дешевой соединяющей сети должен быть деревом, так как если бы он содержал цикл, можно было бы удалить одно из звеньев этого цикла и города все еще оставались бы соединенными. Следовательно, для соединения n городов нужно построить n - 1 дорог.

Моя задача-показать, что сеть минимальной стоимости можно построить, пользуясь следующим простым правилом экономичности. Прежде всего соединяю два города с наиболее дешевым звеном Е₁. На каждом из следующих шагов добавляем самое дешевое из звеньев Е_i, при присоединении которого к уже построенным ребрам не образуется никакого цикла. Если имеется несколько звеньев одной и той же стоимости, выбираем любое из них. Каждое дерево Т, построенное таким образом, мы будем называть экономичным деревом. Его стоимость равна сумме стоимостей отдельных звеньев:

с (Т) = с (Е₁ ) + с (Е₂) +... + с (Е_n-1).

 

Нам надо доказать, что никакое другое дерево F, соединяющее те же вершины, не может оказаться дешевле экономичного дерева Т. Пусть F - самое дешевое дерево, соединяющее наши вершины, а Т - любое экономичное дерево. Предположим, что ребра Е₁, Е₂,... экономичного дерева Т пронумерованы в том порядке, в котором они присоединялись при построении Т. Если самое дешевое дерево F не совпадает с Т, то Т имеет по меньшей мере одно ребро, не принадлежащее F. Пусть Е_i = (А,В) - первое такое ребро, и пусть Т (А, В)- цепь графа F, соединяющая вершины А и В (рис.24). Если ребро Е_i добавить к F, то граф F+E_i, будет содержать цикл С = Е_i + Т (А,В), а так как Т не имеет циклов, то цикл С должен содержать по меньшей мере одно ребро, не принадлежащее Т. Удалив это ребро Е_{i ,} мы получим дерево: F^’ = F + Е_i - Е^’_i, с тем же самым числом вершин, что и F, причем его стоимость равна с (F^’ ) = c (F)+ c (Е_i) - c(Е^’_i). Так как F имеет наименьшую возможную стоимость, то c(Е_i) >= c (Е^’_i )

Но Е_i было звеном наименьшей стоимости, при добавлении которого к Е₁, Е₂,..., Е_i-1 не получается циклов. Так как при добавлении ребра Е^’ _i к этим ребрам мы тоже не получим никакого цикла, то c(Е_i) = c (Е^’_i ), и следовательно, F^’ тоже имеет минимальную стоимость: с(F^’) = c (F).

Таким образом, мы нашли другое дерево F^’ минимальной стоимости, имеющее с экономичным деревом T одним общим ребром больше, чем F. Мы можем повторять эту операцию до тех пор, пока окончательно получим соединяющее дерево минимальной стоимости, совпадающее с T. Таким образом, T, а также все другие экономичные деревья имеют действительно минимальную стоимость.

 

 

Упражнение

1. Возьмите на плоскости шесть точек. Найдите дерево наименьшей общей длины, ребра которого соединяют эти вершины.

Построение экономичного дерева

Задача

 

F A

E B

D C

АВ = 10 ВС = 3 СD = 7 DE = 12

AC = 15 BD = 16 CE = 15 DF = 6

AD = 20 BE = 21 CF = 20

AE = 17 BF = 18 EF = 6

AF = 9

Потоки в сетях.

Введение.

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

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

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

Если для некоторой дуги не указана нижняя граница, то предполагается, что она равна нулю.

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

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