Пусть множество Х – множество печей для обжига кирпича, а множество У – множество платформ для сушки кирпича. Печи соединены с платформами рельсами. В месте пересечения рельсов вагонетки могут сойти с рельса. Ясно, чем меньше пересечений, тем меньше аварий. Каково наименьшее число аварий?
Поставим задачу в математическом виде.
Пусть имеется двудольный граф G 
, где m и n – мощности множеств Х и У соответственно. Предположим, что вершины и ребра расположены в одной плоскости. В каждой точке, отличной от вершины пересекаются не более двух ребер. Оценим общее количество внутренних точек пересечения двудольного графа.
Введем обозначения: J(m, n) – функция, значением которой является число таких точек пересечения.
Нам известно, что граф Понтрягина – Куратоввского имеет не менее одного пересечения, т.е. J(3, 3) 
1.
Справедлива
Теорема
. 
Доказательство:
На первом этапе докажем, что эта теорема справедлива при m =3:
m=3, значит r=1, и тогда должно быть
.
Воспользуемся методом математической индукции:
|
,что справедливо. Граф (3,2) не имеет пересечений, в чем достаточно просто убедиться (рис. 21), а граф (3,3) - это граф Понтрягина – Куратоввского, имеющий одну точку пересечения.
 |
● ● ●
● ●
Рис. 21. Двудольный граф (3,2.
Предположим, что теорема справедлива для некоторого s и докажем, что она справедлива для s+1. Мы должны будем получить:
= 
. (*)
Разобьем граф G 
на подграфы.
:
х1 х2 х33
● ● ●
● ●
yi yj
Рис. 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). Если каждому ребру этого графа поставлено в соответствие некоторое число, то граф называется взвешенным.
При задании взвешенных графов в матрицу смежности (или список) заносятся веса.