Реферат: Пермского университета, сер. Математика. Механика. Информатика, вып. 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) Шкарапута А. П., к. ф.-м. н. ОБ ОДНОМ ВАРИАНТЕ ДОКАЗАТЕЛЬСТВА Чечулин В. Л. 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-раскрашиваемый граф — не плоский из которого следует решение проблемы 4-х красок: Всякий плоский граф 4-раскрашиваем Библиографический список 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.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‑ть раскрашиваемый граф необходимо не плоский (см. текст),— прежде не использовался. |