Специальная математика. Соловьев А.Е. - 55 стр.

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

                                                           Если эта вершина имеет степень не
       3           3                                     больше четырех , то 5 красок хватит.
                                        1   3            Но если степень пять, то из 1-ой
                                                         вершины строим все возможные
           1                        3                    цепи , где чередуются вершины 1 и
                   2                                     3:
   5                                                      Здесь возможны два случая:
                                     1                    1). Ни одна из цепей не замкнулась
                       3                                 на третью вершину. Тогда меняем
       4                                                 цветами все 1-ые и 3-ие вершины и
                           n                             n+1 -ю вершину красим в 3-ий цвет ;


2.) Одна из цепочек замкнулась на 3, тогда из вершины с номером 2 строим цепь 2-4. Ни
одна из этих цепей не замкнется на 4-ю вершину (т.к. граф планарный!). Меняем цвета 2 и 4
в этой цепи. И красим n+1-ю вершину в цвет 2.
Таким образом, то, что пяти красок достаточно, доказано.

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




                                   4.8. Определение путей в графе


               a               b
   g

                                     c
  f
               e           d

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


                                                — 55 —