Смекни!
smekni.com

Пермского университета, сер. Математика. Механика. Информатика, вып. 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 А ONE PROOF OF A PLANAR'S GRAPHS 4-CHROMATI­CAL­LY

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‑ть рас­крашиваемый граф необходимо не плоский (см. текст),— прежде не использовался.