Задача о наименьшем числе аварий.

Пусть множество Х – множество печей для обжига кирпича, а множество У – множество платформ для сушки кирпича. Печи соединены с платформами рельсами. В месте пересечения рельсов вагонетки могут сойти с рельса. Ясно, чем меньше пересечений, тем меньше аварий. Каково наименьшее число аварий?

Поставим задачу в математическом виде.

Пусть имеется двудольный граф G , где m и n – мощности множеств Х и У соответственно. Предположим, что вершины и ребра расположены в одной плоскости. В каждой точке, отличной от вершины пересекаются не более двух ребер. Оценим общее количество внутренних точек пересечения двудольного графа.

 Введем обозначения: J(m, n) – функция, значением которой является число таких точек пересечения.

Нам известно, что граф Понтрягина – Куратоввского имеет не менее одного пересечения, т.е. J(3, 3) 1.

 Справедлива

Теорема

 

     .

Доказательство:

На первом этапе докажем, что эта теорема справедлива при m =3:

m=3, значит r=1, и тогда должно быть

.

 

Воспользуемся методом математической индукции:

если

Итак, положим s=1, тогда

,что справедливо. Граф (3,2) не имеет пересечений, в чем достаточно просто убедиться (рис. 21), а граф (3,3) - это граф Понтрягина – Куратоввского, имеющий одну точку пересечения.

 

                                        ●      ●       ●

 

                                               ●        ●

 

                                      

 

                                 Рис. 21. Двудольный граф (3,2.

 

Предположим, что теорема справедлива для некоторого s и докажем, что она справедлива для s+1. Мы должны будем получить:

= . (*)

Разобьем граф G  на подграфы. 

:                                                                                       

                                                                                   х₁     х₂       х₃₃

                                                                                    ●  ●    ●

 

 

                                                                                         ●   ●

                                                                                         y_i   y_j

 

                                                                                                

 

Рис. 22. Разбиение графа на подграфы и пример объединения их в пары.

 

Будем рассматривать всевозможные пары этих подграфов

 G (i j):

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

 

= =     (1),

Полагая, что S=S+1, получим n=2(S+1), если n - четное  (2),

n=2(S+1) +1, если n – нечетное.        (3)

Подставим формулу (2) в (1): Получим:

 

= , что совпадает с оценкой (*).

Теперь подставим (3) в (1):

, что совпадает с оценкой (*).

 

Предположим теперь, что имеется пара G , не имеющая точек пересечения. Тогда у нас останется n-2 подграфа, имеющих точки пересечения. По предположению индукции граф с (n-2) вершинами должен иметь . Добавим вершину n+1: , что совпадает с оценкой (*).

Мы доказали, что при m=3 исходная формула справедлива.

Докажем теперь, что формула для оценки общих точек пересечения справедлива для любого m:

.    (5)

Воспользуемся методом индукции, т. докажем справедливость формулы (5) для 

, , .

Рассмотрим первый случай. При r=s=1 формула справедлива.

Предположим, что m=2r. Разобьем граф G  на подграфы и пронумеруем их:

 

Рис. 23. Разбиение графа на подграфы.

 

Объединим последовательно 1 – ый и 2 – ой, 3 – ий и 4 – ый…: (1,2), (3,4),…, (2r-1,2 r) подграфы. По индуктивному предположению формула (5) справедлива. Добавим х  вершину. Эта вершина с каждой парой подграфов образует подграф G , а для него доказано, что число точек пересечения равно (s -s), если n=2s, и s , если n=2 s+1. Тогда общее число пересечений (у нас r пар)

= J(m,n)+ r(s - s) или = J(m,n)+ r s .

Получим:

=(r -r) (s -s) +r(s -s) =r (s -s)

или

=(r -r)s +rs =r s , т.о. формула (5) справедлива.

Пусть теперь m=2r+1 (нечетное). Тогда при разбиении на пары подграфов последней вершине m – ой не хватает пары. Но если мы добавим (m+1) – ую вершину, то получим подграф G . Может оказаться, что этот подграф имеет точки пересечения или не имеет их. Если не имеет, то наша оценка не изменится, а если имеет, то только усилится.

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

Что и требовалось доказать.

Пример:

m=4, n=4, тогда r=2, s=2.

J (4, 4) (2 -2) (2 -2) = 4.

 

Взвешенный граф.

      Пусть задан граф G(V,E). Если каждому ребру этого графа поставлено в соответствие некоторое число, то граф называется взвешенным.

При задании взвешенных графов в матрицу смежности (или список) заносятся веса.

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

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

	…
	…
		…

 

Рис. 24. Пример дорожного графа.

 

Обозначим l  - расстояние от i– той до смежной с ней j – той вершины. Задача о нахождении кратчайшего расстояния может быть решена прямым перебором всевозможных расстояний. Кроме кратчайшего расстояния нам необходимо еще и знание промежуточных вершин, через которые пролегает маршрут. Если n – велико, то эта задача становится трудно разрешимой. Возникает необходимость в разработке более компактного алгоритма.

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

 

Сущность этого алгоритма заключается в том, что каждой i – той вершине ставится в соответствие некоторое число , значение которого зависит от значения  предыдущей вершины и расстояния между ними. Сначала объявляется  - 0, а все остальные =   ∞:

			…
0	∞	∞	∞	∞

 

Обозначим через l  расстояние между i – той и j – той вершинами.

Пусть назначена  i – той вершине (i=0,1,…, n). Рассмотрим все  j – ые вершины, смежные с i – той. Если - > l (1),

то полагаем = + l    (2)

И так до тех пор, пока не дойдем до . Значение  и будет значением кратчайшего пути.

 

Обратный ход:

Мы получили = +l      (1*)                                                  

Среди расстояний, соединяющих х  со смежными вершинами, ищем    l = - .

Затем ищем вершину х , у которой = +l . Затем переходим в х  и так далее пока не доберемся до х .

Замечание 1:

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

Замечание 2:

Изменение значения  происходит только тогда, когда выполняется неравенство (1), то есть > +l . Заменяя значение  по формуле (2), мы тем самым уменьшаем его. Так как граф связный, то висячих вершин нет, и, следовательно, каждая вершина получит значение .

      Обоснование алгоритма:

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

 

Пример:

 

 

Рис. 25. Пример взвешенного графа.

 

1) i=0, j=1,2,3;

j=1: - =∞-0, ∞>l ; = +l =5; заносим в таблицу.

j=2: - =∞-0, ∞>l ; = +l =6; заносим в таблицу.

j=3: - =∞-0, ∞>l ; = +l =4; заносим в таблицу.

2) i=1, j=0,2,4 (0 –уже не рассматриваем)

j=2: - =1 , < +l ; значит не меняем   

j=4: > +l , = 5+8 = 13; заносим в таблицу.

3) i=2, j=0, 1, 3, 4.

j=0; не рассматриваем

j=1: < +l ; значит не меняем         

j=3: < +l ; значит не меняем

j=4: > +l , =6+2=8; заносим в таблицу.

4) i=3, j=0,2,5,6;

j=0; не рассматриваем

j=2: < +l ; значит не меняем

j=5: =4+6=10; заносим в таблицу.

j=6: = +l , =4+110=14; заносим в таблицу.

5) i=4, j=1,2,5,7;

j=1: < +l ; значит не меняем

j=2: < +l ; значит не меняем

j=5: < +l ; значит не меняем

j=7: = +l , =10; заносим в таблицу.

6) i=5, j=3,4,6,7;

j=3: < +l ; значит не меняем

j=4: < +l ; значит не меняем

j=6: = +l , =14; заносим в таблицу.

j=7: < +l ; значит не меняем

7) i=6, j=3,5,7;

j=3: < +l ; значит не меняем

j=5: < +l ; значит не меняем

j=7: < +l ; значит не меняем

8) i=7, j=4,5,6;

j=4; не рассматриваем

j=5; не рассматриваем

j=6: < +l ; значит не меняем

 

 Получили схему:

 

0	∞	∞	∞	∞	∞	∞	∞
0	5	6	4	13
				8	10	14	10
Итого	5	6	4	8	10	14	10

 

Обратный ход:

Начиная с последней вершины, проверяем все ей смежные на выполнение условия: l = - . 

Получим кратчайший путь хПоучаем: х х х х .