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

Остальные рефераты » Пермского университета, сер. Математика. Механика. Информатика, вып. 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

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

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

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

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

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

Всякий плоский граф 4-раскрашиваем
(G — плоский,  (G)  4).2

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

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

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

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

ABOUT А ONE PROOF OF A PLANAR'S GRAPHS 4-CHROMATICALLY

Chechulin V. L., chechulinvl@rambler

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..

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