Предуведомление редакции



Скачать 28.31 Kb.
Дата30.12.2012
Размер28.31 Kb.
ТипДокументы


ПРЕДУВЕДОМЛЕНИЕ РЕДАКЦИИ
Для обеспечения свободного доступа к статье воспроизводится публикация автора в малотиражном журнале, оригинальный печатный текст:

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


Похожие:

Предуведомление редакции iconПредуведомление редакции
...
Предуведомление редакции icon2 Редакция газеты «Молодой ленинец» в фонде редакции газеты «Молодой ленинец»
В фонде редакции газеты «Молодой ленинец» хранятся документы за 1950-1991 годы. До 1956 года документы представлены в основном планами...
Предуведомление редакции iconЗакон изложен в новой редакции См текст Закона в предыдущей редакции
Законом Краснодарского края от 11 апреля 2002 г. N 466-кз настоящий Закон изложен в новой редакции
Предуведомление редакции iconЗакон изложен в новой редакции См текст Закона в предыдущей редакции
Федеральным законом от 13 января 1996 г. N 12-фз настоящий Закон изложен в новой редакции
Предуведомление редакции iconВопросы к экзамену Функции журналистики по классификации Е. П. Прохорова Техническая часть редакции Устав редакции

Предуведомление редакции iconРусская Правда Краткой редакции (статьи 1-18). См. Задера А. Г., Пронштейн А. П. практикум
Общая характеристика Русской Правды – первого русского свода законов (история открытия и изучения, редакции и списки)
Предуведомление редакции iconФинал эпилога к «Жизни за царя»: «Славься!»
Запись сделана с постановки оперы в советской редакции, в которой все призывы к «царю» были устранены из либретто. Здесь воспроизводится...
Предуведомление редакции iconКраткое предуведомление к списку учеников
После переезда на улицу Лукса она тоже несколько раз переименовывалась. Сейчас, если судить по её
Предуведомление редакции iconПредуведомление автора
...
Предуведомление редакции iconВ. Н. Татищев. История Российская Предуведомление. Об истории всеобщей и собственно русской
Из Константина Порфирогенита о Русии и близких к ней пределах и народах, собранное Сигфридом Беером
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org