Реферат: Математические основы информатики

Теорема Эйлера. Для любого плоского графа | V(G) | – | R(G) | + | D(G) | = 2.

Заметим, что если не учитывать внешнюю бесконечную область, то формула Эйлера для триангуляции конечного плоского графа имеет вид | V(G ) | – | R(G ) | + + | D(G ) | = 1.

Теорема 2. Любой плоский граф допускает правильную 5-раскраску.

Доказательство. Сначала упростим граф. Если есть несколько ребер, соединяющих некоторую пару вершин (такая ситуация может возникнуть, если две страны имеют несколько несвязанных между собой кусков границы, например как у России и Китая), то оставим только одно ребро: правильность раскраски такого уменьшенного графа все равно гарантирует правильную раскраску исходного.

Проведем теперь индукцию по числу вершин графа. Для графа с тремя вершинами утверждение теоремы очевидно. Пусть оно справедливо для всех графов с n – 1 вершиной.

Пусть D1 , D2 , ..., Dm – полный набор всех m = D(G ) областей графа, а N(Di) – число ребер, составляющих границу i-й области графа. При этом N(Di) ³ 3 для любого i. Любое ребро входит в границу в точности двух областей, поэтому

N(D1) + N(D2)+ ... +N(Dm) = 2R(G ).

Вследствие неравенств N(Di) ³ 3 имеем

2R(G ) = N(D1) + N(D2) + ... + N(Dm) ³ 3m = 3D(G ),

откуда 2R(G ) ³ 3D(G ).

По формуле Эйлера | V(G ) | – 2 + | D(G ) | = | R(G ) |, откуда

3 | R(G ) | = 3 | V(G ) | – 6 + 3 | D(G ) | £ 3 | V(G ) | – 6 + 2 | R(G ) |

и, следовательно,

| R(G ) | £ 3 | V(G ) | – 6.

Заметим, что удвоенное число ребер можно отождествить и с другой характеристикой графа. Пусть a1 , a2 , ... ..., an есть полный набор n = V(G ) вершин графа, а M(aj) – число ребер, сходящихся в вершине с номером j. Но каждое ребро заканчивается двумя вершинами, поэтому

2R(G) = M(a1) + M(a2) + ... + M(an).

Кроме того, как это следует из неравенства (1), 2 | R(G ) | £ 6 | V(G ) | – 12. Следовательно,

M(a1) + M(a2) + ... + M(an) £ 6 | V(G ) | – 12.

Из последнего неравенства можно вывести, что существует по крайней мере одна вершина, в которой сходится не более пяти ребер. Действительно, предположим противное, то есть "j M(aj) ³ 6. Тогда

M(a1) + M(a2) + ... + M(an) ³ 6n = 6V(G ),

что противоречит (2).

Перенумеруем вершины так, что в вершине a = an сходится не более пяти ребер.

Если в вершине a сходятся не более четырех ребер, то рассмотрим граф G \ a, который получается из G устранением вершины a и всех оканчивающихся в ней ребер. Граф G \ a допускает правильную 5-раскраску по предположению индукции. А так как ребра соединяют вершину a не более чем с четырьмя вершинами этого меньшего графа, то для правильной раскраски a остается по крайней мере один цвет (из пяти).

Пусть теперь в a сходится ровно пять ребер. Рассмотрим граф H É G, состоящий из тех пяти вершин, куда приходят ребра, выходящие из a и соединяющих их (в G) ребер. В графе H обязательно найдутся две вершины, не соединенные ребром. Действительно в противном случае в пятиугольнике H будет C₅ ² = 10 ребер (это нетрудно посчитать и непосредственно). Однако в силу (1)

| R(H ) | £ 3| V(H ) | – 6 = 3 " 5 – 6 = 9,

и мы приходим к противоречию.

Пусть b и g суть те вершины H, которые не соединены между собой. Не соединены они и в G \ a. Рассмотрим граф G ', который получается из G \ a при помощи деформации, которая отождествляет (совмещает) b и g. Граф G ' – это плоский граф, так как при отождествлении вершин в этой ситуации не может возникнуть петли. Но для G ' справедливо предположение индукции, и существует некоторая его правильная 5-раскраска j. Разъединим в этом раскрашенном графе вершины b и g. Тогда правильную 5-раскраску получает и граф G \ a, причем такую, что j(b) = j(g). Иными словами, b и g раскрашены одинаково и, следовательно, раскраска пяти соседних с a вершин графа H использует не более четырех цветов.

Используем оставшийся цвет для раскраски вершины a и получим правильную 5-раскраску G!

Проблема четырех красок кажется на первый взгляд изолированной задачей, мало связанной с другими разделами математики и практическими задачами. На самом деле это не так. Известно более 20 ее переформулировок, которые связывают эту проблему с задачами алгебры, статистической механики и задачами планирования. И это тоже характерно для математики: решение задачи, изучаемой из чистого любопытства, оказывается полезным в описании реальных и совершенно различных по своей природе объектов и процессов. Здесь мы рассмотрим одну задачу, эквивалентную проблеме четырех красок.