Гипотеза четырех красок: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Гипотеза четырех красок''' (''Graph colouring conjecture'') - ''каждый планарный граф 4-ра...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Гипотеза четырех красок''' (''Graph colouring conjecture'') | '''Гипотеза четырех красок''' (''[[Graph colouring conjecture]]'') — ''каждый [[планарный граф]] 4-раскрашиваем''. | ||
''каждый планарный граф 4-раскрашиваем''. | |||
Первоначальная формулировка гипотезы гласит: любая карта на | Первоначальная формулировка гипотезы гласит: любая карта на плоскости или на сфере может быть раскрашена четырьмя красками так, что никакие две смежные страны не были одного и того же | ||
плоскости или на сфере может быть раскрашена четырьмя красками | цвета. Гипотеза имеет интересную историю, но в ее появлении остается много непонятного. Имеются сообщения, что А. Мебиус был знаком с этой проблемой в 1840 г., но точно известно лишь то, что о | ||
так, что никакие две смежные страны не были одного и того же | |||
цвета. Гипотеза имеет интересную историю, но в ее появлении | |||
остается много непонятного. Имеются сообщения, что А. Мебиус был | |||
знаком с этой проблемой в 1840 г., но точно известно лишь то, что о | |||
данной проблеме Гутри сообщал О. де Моргану примерно в 1850 г. | данной проблеме Гутри сообщал О. де Моргану примерно в 1850 г. | ||
Сформулировал гипотезу британский математик А. Кэли в 1879 г. в | Сформулировал гипотезу британский математик А. Кэли в 1879 г. в статье, посвященной проблеме раскраски карт в первом томе Трудов Лондонского географического общества. | ||
статье, посвященной проблеме раскраски карт в первом томе Трудов | |||
Лондонского географического общества. | |||
Первое из многих ошибочных "доказательств" было дано А. Кемпе в 1879 г. | Первое из многих ошибочных "доказательств" было дано А. Кемпе в 1879 г. Новую фазу в истории гипотезы открыло машинное доказательство В. Хакена и К. Апеля, появившееся в 1976 г. Это доказательство не было принято математической общественностью и породило новую проблему — проблему методологии и корректности доказательств математических теорем с помощью ЭВМ. | ||
Новую фазу в истории гипотезы открыло машинное доказательство | |||
В. Хакена и К. Апеля, появившееся в 1976 г. Это доказательство не | |||
было принято математической общественностью и породило новую | |||
проблему | |||
математических теорем с помощью ЭВМ. | |||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 16:50, 9 декабря 2010
Гипотеза четырех красок (Graph colouring conjecture) — каждый планарный граф 4-раскрашиваем.
Первоначальная формулировка гипотезы гласит: любая карта на плоскости или на сфере может быть раскрашена четырьмя красками так, что никакие две смежные страны не были одного и того же цвета. Гипотеза имеет интересную историю, но в ее появлении остается много непонятного. Имеются сообщения, что А. Мебиус был знаком с этой проблемой в 1840 г., но точно известно лишь то, что о данной проблеме Гутри сообщал О. де Моргану примерно в 1850 г.
Сформулировал гипотезу британский математик А. Кэли в 1879 г. в статье, посвященной проблеме раскраски карт в первом томе Трудов Лондонского географического общества.
Первое из многих ошибочных "доказательств" было дано А. Кемпе в 1879 г. Новую фазу в истории гипотезы открыло машинное доказательство В. Хакена и К. Апеля, появившееся в 1976 г. Это доказательство не было принято математической общественностью и породило новую проблему — проблему методологии и корректности доказательств математических теорем с помощью ЭВМ.
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.