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

Задача о 4 красках

Это одна из самых знаменитых задач теории графов и математики вообще.

Достаточно ли четырех красок для раскраски любой политической карты мира так, чтобы два государства, имеющие общую границу, были раскрашены в разные цвета?

В качестве иллюстрации можно взять произвольную "карту". Для облегчения анализа представим государства в виде вершин графа. "Раскраску" отобразим цифрами.

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

1 2 1

1 2 1

1 1 4 2 1 4

Так что задачу можно переформулировать так:

Сколько необходимо красок в планарном графе, чтобы любые две смежные вершины были раскрашены различными цветами?

Теорема: Трех красок мало.

1

Пример доказывает, что 3-х красок мало

2 3

Теорема: Для раскраски любого планарного графа достаточно 5-ти красок

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

1) Для любого планарного графа с n<=5 теорема справедлива.

2) Пусть любой планарный граф с n вершинами 5-раскрашиваемый.

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

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

3 3

1 3

1 3

2

5

n

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

Таким образом, то, что пяти красок достаточно, доказано.

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

a b

g

c

f

e d

Требуемые результаты получаются путем перемножения матриц смежности графа.

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

	a	b	c	d	e	f	g
a
b
c
d
e
f
g

M M

Матрица M² дает все пути длиной в 2

Матрица Мⁿ - пути длиной в n.

Если Мⁱ - нулевая матрица, то наибольший путь в графе имеет длину i - 1.

Для определения наличия путей между двумя вершинами можно использовать «транзитивное замыкание» матриц

M^* = M¹ È M² È M³ ...

Непустая клеточка ij будет говорить о наличии пути из i-ой вершины в j-ую.