Одна задача о плоских графах.

Теория Графов

Оглавление

Теория Графов.................................................................................................................... 1

Оглавление......................................................................................................................... 2

ВВЕДЕНИЕ........................................................................................................................ 4

1. Что такое граф?............................................................................................................ 5

1.1. Общее определение................................................................................................ 5

1.2. Нуль-граф и полный граф..................................................................................... 7

1.3 ИЗОМОРФНЫЕ ГРАФЫ....................................................................................... 8

1.4. Плоские графы...................................................................................................... 11

1.5. Одна задача о плоских графах............................................................................ 12

1.6. ЧИСЛО РЕБЕР ГРАФА....................................................................................... 13

2. Связные графы............................................................................................................. 16

2.1. Компоненты......................................................................................................... 16

2.2. Задача о кенигсбергских мостах........................................................................ 18

2.3. Эйлеровы графы.................................................................................................. 19

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

2.5. Гамильтоновы линии.......................................................................................... 22

3. ДЕРЕВЬЯ..................................................................................................................... 24

3.1. Деревья и леса....................................................................................................... 24

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

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

4.1.Введение................................................................................................................. 31

4.2. Формальные постановки задач потокового программирования..................... 32

4.2.1. Система обозначений в потоковых задачах............................................... 32

4.3. Специальные случаи стандартной линейной задачи о потоке минимальной стоимости. 34

4.3.1.Транспортная задача....................................................................................... 34

4.3.2. Задача о назначениях..................................................................................... 35

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

4.3.4. Задача о максимальном потоке.................................................................... 35

4.4. Примеры моделей потокового программирования.......................................... 35

4.4.1. Свободный узел и его параметры................................................................ 35

4.4.2. Стандартная линейная задача о потоке минимальной стоимостью......... 36

4.4.3. Задача о назначениях..................................................................................... 39

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

4.4.5. Задача о максимальном потоке.................................................................... 46

5. ОРИЕНТИРОВАННЫЕ ГРАФЫ.............................................................................. 48

5.1 Определение ориентированного графа............................................................... 48

5.2 Одностороннее движение..................................................................................... 48

5.3. Степени вершин.................................................................................................. 51

6. ОТНОШЕНИЯ............................................................................................................. 53

6.1. Отношения и графы............................................................................................. 53

6.2. Специальные условия.......................................................................................... 53

6.3. Отношения эквивалентности.............................................................................. 54

7. ПЛОСКИЕ ГРАФЫ.................................................................................................... 57

7.1. Условия для плоских графов............................................................................... 57

8. Матричные представления..................................................................................... 60

7.2. Пример использования матрицы смежности.................................................... 60

ВВЕДЕНИЕ

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

 

Что такое граф?

 

Общее определение

Граф есть упорядоченная пара (V, E) где:

· V - непустое множество, называемое множеством вершин;

· E - неупорядоченное бинарное отношение на V (то есть если (u,v)Î (V,V), то (u,v)= (v,u)).

Говорят, что ребро, принадлежащее множеству Е, инцидентно вершинам, которые оно соединяет.

 

Пример 1.

Предположим, что шесть команд - А, В, С, Д, Е и F, - участвует в соревнованиях по футболу. Через несколько недель после начала соревнования окажется, что некоторые из команд уже сыграли друг с другом, например:

А с С, D, F,

B c C, E, F

C c A, B

D c A, E, F

E c B, D, F

F c A, B, D, E

 

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

 

 

А

F B

 

E D

рис. 1

Схема такого вида называется графом. Она состоит из нескольких точек A, B, C, D, E, F, называемых вершинами, и нескольких соединяющих эти точки отрезков, таких, как AC или EB, называемых ребрами графа.

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

 

A B

E F

H C

D C

рис. 2

Нуль-граф и полный граф

Существуют некоторые специальные графы, встречающиеся во многих приложениях теории графов. Будем пока опять рассматривать граф как наглядную схему, иллюстрирующую ход спортивных состязаний. До начала сезона, пока еще никакие игры не проводились, на графе нет никаких ребер. Такой граф состоит из одних изолированных вершин, т.е. из вершин, не соединенных никакими ребрами. Граф такого вида будем называть нуль-графом. Эти графы обычно обозначаются О_n - это нуль-граф с n вершинами, не имеющий ребер (привести примеры нуль-графов с 3 и 5 вершинами).

Рассмотрим другой крайний случай. Предположим, что по окончании сезона каждая команда сыграла по одному разу с каждой из остальных команд. Тогда на соответствующем графе каждая пара вершин будет соединена ребром. Мы обозначаем полные графы через U_n - граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Этот граф можно представить себе как n- угольник, в котором приведены все диагонали.

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

 

A

F B

C

D

рис. 3

 

Можно также отдельно начертить граф, соответсмтвующий пока еще не сыгранным, будущим играм. Для графа G при этом получится граф, изображенный на рис.4.

 

A

B

F

C

E

D

рис. 4

Этот новый граф мы называем дополнением графа G; принято обозначать его через . Взявдополнение графа , мы получим снова граф G. Ребра обоих графов G и вместе составляют полный граф с теми же вершинами.

 

 

УПРАЖНЕНИЯ.

1. Начертите дополнение графа, изображенного на рисунке 2.

2. Чему равно число ребер полного графа V?

ИЗОМОРФНЫЕ ГРАФЫ.

Заметим, что граф G (рис.1) можно изображать по-разному. Во-первых, совсем не обязательно изображать его ребра прямолинейными. Мы можем провести любые линии, соединяющие те же самые вершины, что и раньше. Так., граф G можно представить в виде, изображенном на рис.5.

 

A

F

B

C

E D

рис. 5

Во-вторых, мы можем произвольно располагать вершины на плоскости. Например, вершины графа G можно расположить так, как показано на рис.6.

 

A

D C

B

E

F

рис. 6

Если рассматривать три графа, изображенные на рис.1,5,6, как графы, описывающие ход спортивного турнира, то они будут содержать в точности одну и ту же информацию относительно того, какие именно команды уже сыграли друг с другом; в некотором смысле это один и тот же граф. Мы будем говорить, что два графа - обозначим их G1 и G2 - изоморфны, если они имеют одно и тоже число вершин и для любых двух вершин графа G1, скажем B1 и С1, соединенных ребром, соответствующие им вершины B2 и С2 графа G2 тоже соединены ребром, и обратно.

Согласно этому определению графы на рис. 1,5 и 6 - изоморфны.

Графы на рис.7 не изоморфны, потому что у них разное число вершин.

 

 

 

рис. 7

 

Не изоморфны и графы на рис.8, так как у них не одинаковое число ребер.

рис. 8

Однако для того, чтобы показать, что не изоморфны графы, изображенные на рис.9, требуется уже несколько более тонкое рассуждение.

 

1 2

5 6

8 7

4 3

рис. 9

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

(1,2); (2,3); (3,4); (4,8); (8,7); (7,6); (6,5); (5,1);

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

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

 

 

рис. 9

УПРАЖНЕНИЯ

1. Покажите, что графы, изображенные на рис.1, 2 и 4, не изоморфны между собой.

2. Обозначьте вершины двух графов рис.9 так, чтобы изоморфность этих графов стала очевидной.

Плоские графы

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

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

Плоский граф можно рассматривать как карту дорог, соединяющих между собой различные станции или деревни. Так, на карте, изображенной на рис.10, мы видим 7 станций: А, B,..., G, причем некоторые из них соединены друг с другом дорогами: AG, BC, FE и т.д. и обратно, каждую карту дорог можно рассматривать как плоский граф.

 

B

 

C

A G

F E D

рис. 10

План любого города тоже является плоским графом, где улицы служат ребрами, а площади и перекрестки - вершинами.

A B C

X Y Z

рис. 11

Эти дорожки, или ребра графа, пересекаются во многих точках, отличных от точек расположения домов A, B, C и колодцев X,Y,Z. Число лишних точек пересечения можно свести к 1, если провести дорожки так, как указано на рис.12.

 

В

А

С

Х

У

Z

рис. 12

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

ЧИСЛО РЕБЕР ГРАФА.

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

 

В

В

L

А

А А

б

рис.13

 

Вместо того, чтобы на самом деле проводить несколько ребер между одними и теми же вершинами А иВ, можно провести всего одно ребро, приписав ему кратность, показывающую сколько раз надо сосчитать это ребро (рис. 13, б).

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

р (А) = р (В) = р (D) = р (Е) = 3; р (F) = 4; р (С) = 2.

Легко видеть, что для графа G с n вершинами А1, А2,..., Аn, степени которых соответственно равны r (А1), r (А2),..., r (Аn), число N ребер равно:

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

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

Теорема. Число нечетных вершин любого графа четно.

Бывают графы, у которых степени всех вершин одинаковы:

r (A₁)= r (A₂) =...= r(A_n)= r

Такой граф называется однородным графом степени r; в силу формулы (1) число его ребер равно:

где n - число вершин.

Графы, изображенные на рис.14, являются однородными, степени их равны трем и четырем.

.

 

 

.

 

 

рис.14

В полном графе U_n c n вершинами из каждой вершины выходит n - 1 ребер, ведущих к каждой из остальных n - 1 вершин; таким образом, U_n является однородным графом степени n - 1. Нуль-граф O_n тоже является однородным по той простой причине, что для каждой его вершины r(А) = 0 .

Связные графы

Компоненты

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

Т

 

А

 

рис.15

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

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

 

 

 

А Т

рис. 16

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

A

F B

C

E D

рис. 1 (повторение)

 

Последовательность ребер AFDEFB - это цепь;

Последовательность ADFEB - дуга;

Последовательность AFEDFBCA - цикл;

Последовательность ACBFEDA - простой или элементарный цикл.

 

Если каждую вершину графа можно соединить с любой другой его вершиной некоторой цепью, то граф называется связным. У несвязного графа не все вершины можно соединить цепями с данной вершиной А и все инцидентные им ребра образуют связную компоненту вершины А.

Таким образом, весь граф распадается на связные компоненты, не соединенные между собой ни ребрами, ни цепями.

 

рис.17 Пример несвязного графа

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

Эйлеровы графы

Изложив решение задачи о кенигсбергских мостах, Эйлер перешел к следующей общей проблеме теории графов: на каких графах можно найти цикл P, содержащий все ребра графа, причем каждое ребро в точности по одному разу?

Такой цикл будем называть эйлеровой линией, и граф, обладающий эйлеровой линией - эйлеровым графом.

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

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

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

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

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

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

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

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

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

 

Упражнения

 

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

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

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

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

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

 

Упражнения

 

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

 

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

 

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

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

 

ДЕРЕВЬЯ

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

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

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

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

А₀ А₃

А₁

А₁₃ А₂₁ А₂ А₂₃

А₁₂А₂₂

А₁₁

рис. 20

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

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

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

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

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

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