Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86-87. (прореферировано в рж математика, ран, № 07. 08. 13В. 231) Шкарапута А. П., к ф. м н

ПРЕДУВЕДОМЛЕНИЕ РЕДАКЦИИ

Для обеспечения свободного доступа к статье воспроизводится публикация автора в малотиражном журнале, оригинальный печатный текст:

Чечулин В. Л., Об одном варианте доказательства теоремы о 4-раскрашиваемости плоских графов // Вестник Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86–87. (прореферировано в РЖ Математика, РАН, реферат № 07.08.‑13В.231)

Шкарапута А. П., к. ф.-м. н. УДК 519.17

ОБ ОДНОМ ВАРИАНТЕ ДОКАЗАТЕЛЬСТВА 4-РАСКРА­ШИ­ВА­­­ЕМОС­ТИ ПЛОСКИХ ГРАФОВ

Чечулин В. Л. 1
chechulinvl@rambler.ru

1
Россия, 618419, Пермская обл., г. Березники, ул. Пятилетки 50-22

Описан вариант доказательства известной теоремы о 4-раскрашиваемости плоских графов.

© Чечулин В. Л., 2005-2009.

Как известно, каждый связный 4-раскра­ши­ва­емый граф стягиваем к К4
[1, с. 264, теорема 60.1], выберем в произвольном 5-рас­кра­ши­ва­е­мом графе (G, c(G) ≥ 5) произвольную 5-рас­кра­ши­ва­емую область (G5
), часть которой (вся 4-рас­кра­ши­ваемая, G4
) стягиваема в К4
, тогда, поскольку эта стянутая область (G5
*, содержащая G4
, стянутую в К4
) 5-раскрашиваема, то, очевид­но, в ней можно выделить подграф К5
[1]
, од­нако граф К5
— не плоский, значит, 5-рас­­кра­шиваемый граф (G) тоже не плоский; ввиду произвольности выбранного 5-рас­кра­ши­ваемого графа получаем утверждение:

Всякий минимально 5-раскраши­ва­емый граф — не плоский (c(G) ³ 5, Þ G — не плоский);

из которого следует решение проблемы 4-х красок:

Всякий плоский граф 4-раскра­ши­ваем (G — плоский, Þ c(G) £ 4).[2]

Библиографический список

1. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.
, М.: «Наука», гл. ред. физ.-мат. лит., 1990.— 384 с.

2. Харари Ф.
, Лекции по теории графов, , М.: «Мир», 1973.— 304 с., пер. с англ. Козырев В. В.
, ред. Гаврилов Г. П..

3. Самохин А. В.
, Проблема 4-х красок: неоконченная история доказательства // Соросовский образовательный журнал, №7, 2000 г., сс. 91-96.

ABOUT А
<

Chechulin V. L., chechulinvl@rambler.ru

Russia, Perm region, Berezniki, 618419, Pyatyletka st., 50-22.

The proof of the "4-colors" theorem in a graph theory about а
planar's graphs 4-chromatically was described..

© Chechulin V. L., 2005-2009.

[1]
Получаемый (в G5
*) из выделенного всего 4-рас­кра­шиваемого подграфа (G4
), стянутого в K4
, присоединением одной 5-ой (5-раскрашиваемой вершины), по 5-ть раскрашиваемости подграфа (G5
), в нём найдётся такая вершина, соединённая рёбрами со всеми вершинами K4
. Предположения о стягиваемости 5-рас­кра­шиваемой области (G5
) в К5
— не требуется (гипотезы Хадвиггера не требуется, см. [1, с. 264], [2, с. 161-162] ).

5-раскрашиваемая область (G5
) выбирается так, что в ней есть некоторая вершина раскрашенная 5‑м цветом, соединённая рёбрами с вершинами связной 4-раскрашиваемой области (G4
), которая и стягиваема в К4
. (Если такого выбора сделать нельзя, то изначальный граф (G) — менее чем 5‑рас­­крашиваем, и проблема уже решена.)

[2]
Исторически попытки доказательства теоремы 4- красок (Мёбиус, 1840, Кемпе, Kempe
A.
B.
, On geographical problem of four colors, Amer. J. Math., 2 (1879), 193–204; Хивуд, Heawood
P.
J.
, Map color theorems, Quart. J. Math., 24 (1890), 332–338 (ссылки по [2])) заключались в прямом способе доказательства: попытке установить достаточное условие,— сколько цветов достаточно для раскрашивания плоской карты (получалось не менее 5-ти), позже Xeeш Х., 1969, и другие поступая так же свели исследование проблемы к исследованию сложных, т. н. неустранимых, конфигураций, 1492‑х, в 1976 г. посредством ЭВМ коллективу математиков при руководстве Аппеля К. и Хейкена В. удалось раскрасить все эти кон­фигурации 4‑мя цветами, на что потребовалось ок. 2000 часов компьютерного времени (Appel
K.
, Haken
W.
, Every Planar Map Is Four Colorable., Contemporary Mathematics. Providense (R. I.): Amer. Math. Soc., 1989., Vol 98. 308 p. Cсылки по [1], [3], там же указывалось на сложность проверки такого "доказательства", см. тж. краткий историч. обзор в [3]); логический же ход доказательства необходимости 4-х красок для раскраски плос­кого графа: 5‑ть рас­крашиваемый граф необходимо не плоский (см. текст),— прежде не использовался.