Разделы презентаций


Проблема четырех красок

Содержание

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

Слайды и текст этой презентации

Слайд 1Проблема четырех красок
В 1850 году шотландский физик Фредерик Гутри обратил

внимание на то, что задачи раскрашивания карт очень популярны среди

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

Слайд 2Проблема четырех красок
Годом рождения проблемы четырех красок считается 1878 год

(в некоторых изданиях указывается 1879). Именно тогда на одном из

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

Слайд 3Проблема четырех красок
В 1890 году английский математик П. Хивуд доказал,

что любую карту на плоскости можно раскрасить пятью красками. Однако

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

Слайд 4Что такое «карта»?
Хотя понятие карты является довольно естественным и опирается

на представления о географических картах, тем не менее, вопрос о

том, что такое карта, не такой простой, как кажется на первый взгляд.

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

Что такое «карта»?	Хотя понятие карты является довольно естественным и опирается на представления о географических картах, тем не

Слайд 5Что такое «карта»?
Многоугольной картой на плоскости будем называть разбиение многоугольника

на более мелкие многоугольники, получающиеся добавлением новых вершин и сторон

внутри данного многоугольника, причем любые два новых многоугольника или не имеют общих точек, или имеют общие вершины, или имеют общие стороны. Многоугольники называются странами, а их стороны – границами.

Пример такой карты приведен на рисунке.

Что такое «карта»?	Многоугольной картой на плоскости будем называть разбиение многоугольника на более мелкие многоугольники, получающиеся добавлением новых

Слайд 6Что такое «карта»?
Иногда к многоугольной карте в качестве дополнительных стран

присоединяют одну или несколько внешних бесконечных областей плоскости, ограниченных сторонами

исходного многоугольника и лучами.

Пример такой карты приведен на рисунке. Новые страны помечены цифрами 1, 2, 3, 4.

Что такое «карта»?	Иногда к многоугольной карте в качестве дополнительных стран присоединяют одну или несколько внешних бесконечных областей

Слайд 7Что такое «карта»?
Рассматриваются также карты, составленные из многоугольников, заполняющих всю

плоскость. Как и раньше требуется, чтобы любые два многоугольника или

не имели общих точек, или имели общие вершины, или имели общие стороны.
Примеры таких карт дают паркеты, некоторые из которых представлены на рисунке.
Что такое «карта»?	Рассматриваются также карты, составленные из многоугольников, заполняющих всю плоскость. Как и раньше требуется, чтобы любые

Слайд 8Что такое «карта»?
Заметим, что для задачи раскрашивания карты неважно, какими

являются границы стран, прямыми или нет. Карту можно немного растягивать,

сжимать, искривлять стороны, и при этом число красок, необходимых для ее правильного раскрашивания, не изменится. Мы будем рассматривать и такие карты.

На рисунке показана многоугольная карта и карта, полученная из нее искривлением сторон.

Что такое «карта»?	Заметим, что для задачи раскрашивания карты неважно, какими являются границы стран, прямыми или нет. Карту

Слайд 9Что такое «карта»?
Помимо плоскости, карты рассматривают и на других поверхностях,

например, на сфере.
На рисунке показаны карты, образованные поверхностями правильных многогранников:

тетраэдра, куба, октаэдра, икосаэдра и додекаэдра.

Поверхность многогранника можно рассматривать как карту, странами которой являются грани многогранника, а границами – его ребра.

Что такое «карта»?	Помимо плоскости, карты рассматривают и на других поверхностях, например, на сфере.	На рисунке показаны карты, образованные

Слайд 10Упражнение 1
Сколько красок требуется для правильной раскраски карты, изображенной на

рисунке?

Упражнение 1	Сколько красок требуется для правильной раскраски карты, изображенной на рисунке?

Слайд 11Упражнение 2
Сколько красок требуется для правильной раскраски карт, изображенных на

рисунке?
Ответ: а) 3; б) 4.

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

Слайд 12Упражнение 3
Сколько красок потребуется для правильной раскраски карты, образованной двумя

концентрическими окружностями, имеющими n перегородок?
Ответ: 3, если n четно и

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

Слайд 13Упражнение 4
Сколько красок требуется для правильной раскраски карты, образованной прямыми,

изображенными на рисунке?

Упражнение 4	Сколько красок требуется для правильной раскраски карты, образованной прямыми, изображенными на рисунке?

Слайд 14Упражнение 5
Сколько красок требуется для правильной раскраски карты, образованной окружностями,

изображенными на рисунке?
Ответ: 2.

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

Слайд 15Упражнение 6
Докажите, что если карту можно правильно раскрасить двумя красками,

то каждая ее внутренняя вершина имеет четный индекс (т.е. в

ней сходится четное число сторон).

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

Упражнение 6Докажите, что если карту можно правильно раскрасить двумя красками, то каждая ее внутренняя вершина имеет четный

Слайд 16Упражнение 7
Докажите, что если регулярную карту (т.е. такую, в каждой

вершине которой сходится три стороны), можно правильно раскрасить тремя красками,

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

Слайд 17Упражнение 8
Сколько красок потребуется для правильной раскраски карт, изображенных на

рисунке?

Упражнение 8Сколько красок потребуется для правильной раскраски карт, изображенных на рисунке?

Слайд 18Упражнение 9
Сколько красок потребуется для правильной раскраски карт, изображенных на

рисунке?

Упражнение 9Сколько красок потребуется для правильной раскраски карт, изображенных на рисунке?

Слайд 19Упражнение 10
Сколько красок потребуется для правильной раскраски паркетов, части которых

изображены на рисунке?
Ответ: а) 2; б) 3; в) 3;

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

Слайд 20Упражнение 11
Сколько красок потребуется для правильной раскраски граней призмы (рис.

а) и антипризмы (рис. б)?
Ответ: а) 3; б) 2.

Упражнение 11	Сколько красок потребуется для правильной раскраски граней призмы (рис. а) и антипризмы (рис. б)? Ответ: а)

Слайд 21Упражнение 12
Сколько красок потребуется для правильной раскраски граней правильных многогранников?


Ответ: а) 4; б) 3; в) 2; г) 3; д)

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

Слайд 22Упражнение 13
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине многогранника сходится

три ребра и каждая его грань имеет четное число сторон, то для правильной раскраски граней этого многогранника потребуется три краски.
Упражнение 13	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 23Упражнение 14
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится три ребра и его гранями являются пятиугольники и шестиугольники, то для правильной раскраски граней этого многогранника потребуется четыре краски.
Упражнение 14	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 24Упражнение 15
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится три ребра и его гранями являются треугольники и восьмиугольники, то для правильной раскраски граней этого многогранника потребуется четыре краски.
Упражнение 15	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 25Упражнение 16
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится три ребра и его гранями являются треугольники и десятиугольники, то для правильной раскраски граней этого многогранника потребуется четыре краски.
Упражнение 16	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 26Упражнение 17
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится четыре ребра, то для правильной раскраски граней этого многогранника потребуется две краски.
Упражнение 17	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 27Упражнение 18
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится четыре ребра, то для правильной раскраски граней этого многогранника потребуется две краски.
Упражнение 18	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 28Упражнение 19
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине этого многогранника

сходится четыре ребра, то для правильной раскраски граней этого многогранника потребуется две краски.
Упражнение 19	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 29Упражнение 20
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине многогранника сходится

три ребра и все его грани имеют четное число сторон, то для правильной раскраски граней этого многогранника потребуется три краски.
Упражнение 20	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 30Упражнение 21
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине многогранника сходится

три ребра и все его грани имеют четное число сторон, то для правильной раскраски граней этого многогранника потребуется три краски.
Упражнение 21	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Слайд 31Упражнение 22
Сколько красок потребуется для правильной раскраски граней многогранника, изображенного

на рисунке?
Решение: Так как в каждой вершине многогранника сходится

четыре ребра, то для правильной раскраски граней этого многогранника потребуется две краски.
Упражнение 22	Сколько красок потребуется для правильной раскраски граней многогранника, изображенного на рисунке? Решение: Так как в каждой

Теги

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика