Проблема четырех красок В 1850 году шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков.

Презентация:



Advertisements
Похожие презентации
Проблема четырех красок В 1850 году шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков.
Advertisements

Проблема четырех красок В 1850 году шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков.
Раскрашивание карт В 1850 году шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков.
Раздел геометрии, изучающий свойства фигур и тел, которые не изменяются при их непрерывных деформациях ( растяжениях, сжатиях), как если бы они были сделаны.
ВЫПУКЛЫЕ МНОГОГРАННИКИ Многогранник называется выпуклым, если он является выпуклой фигурой, т. е. вместе с любыми двумя своими точками целиком содержит.
Двойственные многогранники Два правильных многогранника называются двойственными, если центры граней одного из них являются вершинами другого.
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
Каскады из правильных многогранников Правильные многогранники можно вписывать друг в друга. При этом возможны следующие случаи: 1.Вершинами вписанного.
Каскады из правильных многогранников Правильные многогранники можно вписывать друг в друга. При этом возможны следующие случаи: 1.Вершинами вписанного.
Начало теории графов было положено Леонардом Эйлером в его знаменитом рассуждении о Кенигсбергских мостах в 1736 году Леонард Эйлер родился 15 апреля.
Излагается история теоремы о четырех красках. Ее чрезвычайно длинное доказательство, притом использующее компьютер для проверки части утверждений, вызывает.
ПАРКЕТЫ Паркетом на плоскости называется такое заполнение плоскости многоугольниками, при котором любые два многоугольника либо имеют общую сторону, либо.
Паркеты Паркетом называется такое заполнение плоскости многоугольниками, при котором любые два многоугольника либо имеют общую сторону, либо имеют общую.
«Творчество математика в такой же степени есть создание прекрасного, как творчество живописца или поэта, - совокупность идей, подобно совокупности красок.
М НОГОГРАННИКИ. О ПРЕДЕЛЕНИЕ МНОГОГРАННИКА : Многогранник – это поверхность составленная из многоугольников, ограничивающая некоторое геометрическое тело.
ПРАВИЛЬНЫЕ МНОГОГРАННИКИ Правильные многогранники были известны еще в древней Греции. Пифагор и его ученики считали, что все состоит из атомов, имеющих.
Определение. Две прямые в пространстве называются скрещивающимися, если они не лежат в одной плоскости. СКРЕЩИВАЮЩИЕСЯ ПРЯМЫЕ.
Определение. Две прямые в пространстве называются скрещивающимися, если они не лежат в одной плоскости. СКРЕЩИВАЮЩИЕСЯ ПРЯМЫЕ.
ПРАВИЛЬНЫЕ МНОГОГРАННИКИ Выпуклый многогранник называется правильным, если его гранями являются равные правильные многоугольники и в каждой вершине сходится.
Многогранник- это тело, поверхность которого состоит из конечного числа плоских многоугольников. Многогранник- это тело, поверхность которого состоит.
Транксрипт:

Проблема четырех красок В 1850 году шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков в Лондоне, а сформулировал проблему четырех красок его брат Фрэнсис Гутри, который, раскрасив карту графств Англии четырьмя красками, выдвинул гипотезу о том, что этого количества красок достаточно для раскраски любой карты. Он привлек к проблеме внимание своего преподавателя математики А. Де Моргана, а тот сообщил о ней своему другу В. Гамильтону и тем самым способствовал ее широкому распространению.

Годом рождения проблемы четырех красок считается 1878 год (в некоторых изданиях указывается 1879). Именно тогда на одном из заседаний Британского географического общества выдающийся английский математик А.Кэли четко сформулировал поставленную задачу: "Доказать, что любую географическую карту на плоскости (или на глобусе) можно правильно закрасить четырьмя красками". Раскраска карты называется правильной, если любые две страны, имеющие на карте общую границу, окрашены в различные цвета. Именно с этого момента проблема привлекла к себе внимание многих крупных математиков. Проблема четырех красок

В 1890 году английский математик П. Хивуд доказал, что любую карту на плоскости можно раскрасить пятью красками. Однако долгое время проблема четырех красок не поддавалась решению. В 1968 году американские математики Оре и Стемпл показали, что любую карту, имеющую не более 40 стран, можно раскрасить четырьмя красками. В 1976 году американскими учеными К. Аппелем и В. Хакеном было получено решение проблемы четырех красок. С помощью компьютера они просматривали различные типы карт, и для каждого из них компьютер решал, может ли в данном типе найтись карта, которая не раскрашивается четырьмя красками. Было просмотрено почти 2000 типов карт, и для всех был получен ответ: "Нет", - что и позволило объявить о компьютерном решении проблемы четырех красок. Проблема четырех красок

Определение карты Пусть на плоскости задан связный простой граф, каждая вершина которого имеет индекс, больший двух. Этот граф разбивает плоскость на несколько областей. Области будем называть странами, а само разбиение – картой на плоскости. Примеры карт приведены на рисунке.

Поверхность многогранника Помимо плоскости, карты рассматривают и на других поверхностях, например, на сфере. На рисунке показаны карты, образованные поверхностями правильных многогранников: тетраэдра, куба, октаэдра, икосаэдра и додекаэдра. Поверхность многогранника можно рассматривать как карту, странами которой являются грани многогранника, а границами – его ребра.

Упражнение 1 Какое наименьшее число красок потребуется для правильной раскраски карты, изображенной на рисунке? Ответ: 2.

Упражнение 2 Какое наименьшее число красок потребуется для правильной раскраски карт, изображенных на рисунке? Ответ: а) 3; б) 4.

Упражнение 3 Какое наименьшее число красок потребуется для правильной раскраски карты, образованной двумя концентрическими окружностями, имеющими n перегородок? Ответ: 3, если n четно и 4, если n нечетно.

Упражнение 4 Какое наименьшее число красок потребуется для правильной раскраски карты, образованной прямыми, изображенными на рисунке? Ответ: 2.

Упражнение 5 Какое наименьшее число красок потребуется для правильной раскраски карты, образованной окружностями, изображенными на рисунке? Ответ: 2.

Упражнение 6 Докажите, что если карту можно правильно раскрасить двумя красками, то каждая ее вершина имеет четный индекс (т.е. в ней сходится четное число ребер). Доказательство. Если хотя бы одна вершина карты имела бы нечетный индекс, то для правильной раскраски такой карты потребовалось бы более двух красок. Верно и обратное. Если каждая вершина карты имеет четный индекс, то такую карту можно правильно раскрасить двумя красками. Попробуйте доказать это самостоятельно.

Упражнение 7 Докажите, что если регулярную карту (т.е. такую, в каждой вершине которой сходится три ребра), можно правильно раскрасить тремя красками, то каждая ее страна имеет четное число сторон. Доказательство. Если хотя бы одна страна карты имела бы нечетное число сторон, то для правильной раскраски такой карты потребовалось бы более трех красок. Верно и обратное. Если каждая страна регулярной карты имеет четное число сторон, то такую карту можно правильно раскрасить тремя красками. Попробуйте доказать это самостоятельно.

Упражнение 8 Какое наименьшее число красок потребуется для правильной раскраски карт, изображенных на рисунке? Ответ: а) 4; б) 4; в) 2.

Упражнение 9 Какое наименьшее число красок потребуется для правильной раскраски карт, изображенных на рисунке? Ответ: а) 3; б) 2; в) 4; г) 3.

Упражнение 10 Какое наименьшее число красок потребуется для правильной раскраски паркетов, части которых изображены на рисунке? Ответ: а) 2; б) 3; в) 3; г) 2.

Упражнение 11 Какое наименьшее число красок потребуется для правильной раскраски карт, изображенных на рисунке? Ответ: а) 3; б) 2; в) 4; г) 3.

Упражнение 12 Какое наименьшее число красок потребуется для правильной раскраски граней правильных многогранников? Ответ: а) 4; б) 3; в) 2; г) 3; д) 4.

Упражнение 13 Какое наименьшее число красок потребуется для правильной раскраски вершин карты, изображенной на рисунке? Ответ: 3. Рассмотрим вопрос о раскрашивании вершин карты на плоскости. Раскраску вершин будем называть правильной, если если любые две вершины, соединенные ребром, окрашены в различные цвета.

Упражнение 14 Какое наименьшее число красок потребуется для правильной раскраски вершин карт, изображенных на рисунке? Ответ: а) 2; б) 3.

Упражнение 15 Какое наименьшее число красок потребуется для правильной раскраски карты, образованной двумя концентрическими окружностями, имеющими n перегородок? Ответ: 2, если n четно и 3, если n нечетно.

Упражнение 16 Какое наименьшее число красок потребуется для правильной раскраски вершин карт, изображенных на рисунке? Ответ: а) 2; б) 3; в) 3; г) 4.

Упражнение 17 Какое наименьшее число красок потребуется для правильной раскраски вершин правильных многогранников? Ответ: а) 4; б) 2; в) 3; г) 4; д) 3.

Упражнение 18 Докажите, что если вершины карты можно правильно раскрасить двумя красками, то каждая ее страна имеет четное число сторон. Доказательство. Если хотя бы одна страна карты имела бы нечетное число сторон, то для правильной раскраски вершин такой карты потребовалось бы более двух красок.

Упражнение 19 Докажите, что если вершины карты, каждая страна которой имеет три стороны, можно правильно раскрасить тремя красками, то каждая ее вершина имеет четный индекс. Доказательство. Если хотя бы одна вершина карты имела бы нечетный индекс, то для правильной раскраски вершин такой карты потребовалось бы более трех красок.

Двойственные карты Две карты называются двойственными, если вершины одной карты находятся во взаимно однозначном соответствии со странами другой, при этом две вершины одной карты соединены ребром тогда и только тогда, когда соответствующие страны другой карты являются соседними. Пример двойственных карт показан на рисунке. Одинаковыми цифрами отмечены вершины карты а) и соответствующие страны карты б). Ясно, что вершины карты можно правильно раскрасить тогда и только тогда, когда страны двойственной карты можно правильно раскрасить тем же числом красок. В частности, вершины любой карты на плоскости можно правильно раскрасить не более чем четырьмя красками.

Упражнение 20 Покажите, что карты, изображенные на рисунках а) и б), являются двойственными, установив взаимно однозначное соответствие между вершинами одной и странами другой, аналогично данному ранее примеру. Ответ. Одно из возможных соответствий показано на рисунке.