Теорема
Задача о наименьшем числе аварий
Пусть множество Х – множество печей для обжига кирпича, а множество У – множество платформ для сушки кирпича. Печи соединены с платформами рельсами. В месте пересечения рельсов вагонетки могут сойти с рельса. Ясно, чем меньше пересечений, тем меньше аварий. Каково наименьшее число аварий?
Поставим задачу в математическом виде.
Пусть имеется двудольный граф G
, где m и n – мощности множеств Х и У соответственно. Предположим, что вершины и ребра расположены в одной плоскости. В каждой точке, отличной от вершины пересекаются не более двух ребер. Оценим общее количество внутренних точек пересечения двудольного графа.
Введем обозначения: J(m, n) – функция, значением которой является число таких точек пересечения.
Нам известно, что граф Понтрягина – Куратоввского имеет не менее одного пересечения, т.е. J(3, 3) 
1.
Справедлива
Доказательство:
На первом этапе докажем, что эта теорема справедлива при m = 3:
m = 3, значит r = 1, и тогда должно быть
.Воспользуемся методом математической индукции:
Итак, положим s = 1.
Тогда
,что справедливо. Граф (3,2) не имеет пересечений, в чем достаточно просто убедиться (рис. 42), а граф (3,3) - это граф Понтрягина – Куратоввского, имеющий одну точку пересечения.
● ● ●
● ●
Рис. 43. Двудольный граф (3,2)
Предположим, что теорема справедлива для некоторого s и докажем, что она справедлива для s + 1. Мы должны будем получить:
= =
. (*)
Разобьем граф G
на подграфы.
:
х1 х2 х33
● ● ●
● ●
yi yj
Рис. 44. Разбиение графа на подграфы и объединения их в пары
Будем рассматривать всевозможные пары этих подграфов
G 
(i 
j):
Может оказаться, что каждая пара имеет хотя бы одну точку пересечения. Общее число пар ─ число сочетаний Cn2. Тогда
= Cn2 = 
(1)
Полагая, что s = s +1 , получим: если n ─ четное n = 2(S + 1) (2) и, если n – нечетное, то n = 2(s + 1) +1 (3)
Подставим формулу (2) в (1).
Получим:
≥
,
что совпадает с оценкой (*).
Теперь подставим (3) в (1):
, что совпадает с оценкой (*).
Предположим теперь, что имеется пара G , не имеющая точек пересечения. Тогда у нас останется n - 2 подграфа, имеющих точки пересечения. По предположению индукции граф с (n - 2) вершинами должен иметь .
Добавим вершину n + 1:
,
что совпадает с оценкой (*).
Мы доказали, что при m = 3 исходная формула справедлива.
Докажем теперь, что формула для оценки общих точек пересечения справедлива для любого m:
(4)
Воспользуемся методом индукции, т.е. докажем справедливость формулы (4) для
, 
, 
.
Рассмотрим первый случай.
При r= s= 1 формула справедлива.
Предположим, что m = 2r.
Разобьем граф G 
на подграфы и пронумеруем их:
Рис. 45. Разбиение графа на подграфы
Объединим последовательно первый и второй, третий и четвертый и т.д. : (1, 2), (3, 4),…, (2r-1, 2 r) подграфы. По индуктивному предположению формула (4) справедлива. Добавим х
вершину. Эта вершина с каждой парой подграфов образует подграф 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= rs.
Таким образом, формула (4) справедлива.
Пусть теперь m = 2r + 1 (нечетное).
Тогда при разбиении на пары подграфов последней вершине m – ой не хватает пары. Но если мы добавим (m + 1) - ую вершину, то получим подграф G
. Может оказаться, что этот подграф имеет точки пересечения или не имеет их. Если не имеет, то наша оценка не изменится, а если имеет, то только усилится.
Если добавляется вершина во множество У, то доказательство ничем отличаться не будет. Если же вершина добавляется во множества Х и У, то сначала доказывается добавление во множество Х, а потом во множество У.
Что и требовалось доказать.
Пример:m = 4, n = 4, тогда r = 2, s = 2.
J (4, 4) (2-2) ( 2-2) = 4.