ПРЕДУВЕДОМЛЕНИЕ РЕДАКЦИИ
Для обеспечения свободного доступа к статье воспроизводится публикация автора в малотиражном журнале, оригинальный печатный текст:
Чечулин В. Л., Об одном варианте доказательства теоремы о 4-раскрашиваемости плоских графов // Вестник Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86–87. (прореферировано в РЖ Математика, РАН, реферат № 07.08.‑13В.231)
Шкарапута А. П., к. ф.-м. н.
УДК 519.17
ОБ ОДНОМ ВАРИАНТЕ ДОКАЗАТЕЛЬСТВА
4-РАСКРАШИВАЕМОСТИ ПЛОСКИХ ГРАФОВ
Чечулин В. Л. 1 chechulinvl@rambler
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-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..
© 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‑ть раскрашиваемый граф необходимо не плоский (см. текст),— прежде не использовался.
Другие работы по теме:
экзамен
Выписка из учебного плана по спец. 080105 ФИНАНСЫ И КРЕДИТ Срок обучения – 3,5 года (заочное отделение) V семестр № п/п Наименование дисциплины Всего Учебных занятий
«Горе от ума»
«Евгений Онегин» роман не только о любви. Философский аспект содержания романа
контр
Учебный график 2010/2011 учебный год Наименование дисциплин Форма контроля Кол-во часов Преподаватель Примеча-ние зачет экзамен реферат контр.раб.
а и собеседования
Поступающие в магистратуру, имеющие степень бакалавра образования или диплом специалиста по соответствующему направлению, сдают вступительные испытания по профильному предмету в форме реферата и собеседования
работа
План-график учебного процесса МИНСКИЙ ФИЛИАЛ МЭСИ УТВЕРЖДАЮ Зам. директора ___________ В.Н.Кривцов «____» _____________ 200__ г. ПЛАН-ГРАФИК учебного процесса
Выпускная
Проблема обучения математике в профильных классах на примере темы «Логарифмические уравнения»
9. работа по общей геологии
Зачеты Экзамены Бакалавры 1 курс Зимняя сессия 1. Иностранный язык 2. Физическая культура 3. Высшая математика 4. Общая геология 5. Введение в специальность?
работа
Челябинский институт путей сообщения – филиал государственного образовательного учреждения
2. работа
Соответствие систем оценок (используемых ранее оценок итоговой академической успеваемости, оценок ects и балльно-рейтинговой системы (брс) оценок текущей успеваемости) (В соответствии с Приказом Ректора №996 от 27. 12. 2006 г.)
«Эконом теория»
Окуу методикалык иштер боюнча башкармалык Академиялык суроолор ж-а илим боюнча проректору
: «Фузионизм в преподавании геометрии»
Актуальные проблемы обучения математике (К 150-летию со дня рождения А. П. Киселева). Т. 1: Материалы Всероссийской научно практической конференции. Орел: Изд-во огу, 2002. – 351 с
Вероятность
Кажется, как можно «предвидеть» наступление случайного события? Ведь оно может произойти, а может и не сбыться! Но математика нашла способы оценивать вероятность наступления случайных событий.
Длина окружности и площадь круга
Ознакомление с формулами длины окружности, площади круга (частью плоскости, ограниченной окружностью) и исходящими из них формулами расчета радиуса, диаметра. Получение навыков применения формул, закрепление полученных знаний в ходе выполнения упражнений.
Десять правил выживания при изучении математики
Получите от предмета все, пока он не вытянул все силы из Вас. Да, математика является одним из тех предметов, которые основываются на предварительных знаниях. Однако многие учащиеся изучают материал только для того, чтобы сдать экзамен.
Математика
Математика и информатика. Решение системы линейных алгебраических уравнений методом Крамера. Работа в текстовом редакторе MS WORD. Рисование с помощью графического редактора. Определение вероятности. Построение графика функции с помощью MS Excel.
Иероглифическая запись уравнения
Древнейшие древнеегипетские математические тексты относятся к началу II тысячелетия до н. э. Математика тогда использовалась в астрономии, мореплавании, землемерии, при строительстве домов, плотин, каналов и военных укреплений. Денежных расчётов, как и самих денег, в Египте не было. Египтяне писали на папирусе, который сохраняется плохо, и поэтому в настоящее время знаний о математике Египта существенно меньше, чем о математике Вавилона или Греции.
Мой любимый предмет - математика сочинение-рассуждение
Автор: Сочинения на свободную тему Я часто думаю, что было бы, если бы мы до сих пор не умели писать и считать. Наверное, жизнь была бы очень скучной и однообразной. Например, я очень люблю головоломки, разные математические задачи. Они помогают мне развиваться, и я всегда радуюсь, когда нахожу правильное решение.
Ламберт, Иоганн Генрих
Введение 1 Философия 2 Математика 3 Сочинения 5 Источник Введение Иоганн Генрих Ламберт (нем. Johann Heinrich Lambert; 26 августа 1728, Мюлуз, Эльзас — 25 сентября 1777, Берлин) — физик, философ, математик; был академиком в Мюнхене и Берлине.
Закуто, Авраам
Введение 1 Биография 2 Математика и астрономия Список литературы Введение Авраам Бен Шмуэль Заку́то (ивр. אברהם זכות, порт. Abraгo ben Samuel Zacuto, (1450, Саламанка, Испания — 1515, Турция) — известный астроном, первый сконструировал металлическую астролябию, позволявшую более точные измерения, чем деревянная.
Работа с табличным процессором Exce
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ Мценский филиал образовательного учреждения высшего профессионального образования «Орловский государственный технический университет»
Встроенные функции Excel
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РФ НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ЯРОСЛАВА МУДРОГО ИНСТИТУТ ЭКОНОМИКИ И УПРАВЛЕНИЯ КАФЕДРА СЭММ ЛАБОРАТОРНАЯ РАБОТА № 5
Организация циклов в системе Паскаль
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ........................................
Перечень вступительных испытаний
Перечень вступительных испытаний в образовательные учреждения высшего профессионального образования (проект) № п/п Перечень вступительных испытаний
Ададуров Василий Евдокимович
Математик и писатель. В 1727 г. был студентом Академии и обратил на себя внимание математика Бернулли. Занимался также переводом древней истории Байера и статей для академических изданий.