Теорема о четырёх красках

Август 19, 2022

Главная
Культурология
Теорема о четырёх красках

Содержание

2. Цель: узнать, что такое теорема о четырех красках
3. Задачи: ·Изучить историю теоремы о четырех красках. ·Преобразовать теорему в графы. ·Познакомиться с инструкцией игры “Четыре
4. Проблема четырех красок заключается в том, чтобы закрасить области любой карты максимум в 4 цвета, причем
5. Когда появились первые географические карты, появился вопрос о том, как их лучше всего раскрашивать.
6. (1831-1899) В 1852 году при раскрашивании карты Британии студент Френсис Гутри выдвинул эту гипотезу: любую карту
7. Альфред Кемпе в 1879 опубликовал решение проблемы по его мнению Перси.Дж.Хивуд. В 1889 опровергнул это решение
8. В 1880 предложил еще одно доказательство проблемы четырёх красок, которое опровергли в 1891 Питер Тэйт
9. Кеннет Аппель и Вольфганг Хакен В 1971 окончательно доказали теорему при помощи компьютера
10. Теорему о четырех красках можно представить как граф Для этого достаточно ужать все области до кругов
11. Обязательное условие: граф должен быть плоским( ребра не должны пересекаться)
12. Рассмотрим эти графы Почему для раскраски первого хватает всего 2 цвета, а для второго 4?
13. Назовем сложностью графа количество цветов для раскраски. Чем больше цветов тем граф сложнее. Граф упорядочен в
15. На самом деле увеличивают количество цветов в графе компоненты с большим количеством связей. Чтобы доказать это,
16. Здесь мы как бы ограничили доступ второму графу к первому(ромбу)
17. Во втором графе узлы 1, 2 и 4 имеют соединения с более крупным подграфом. В этом
18. Граф можно покрасить в 4 цвета из-за сильной взаимосвязности его компонентов
19. Также хочу рассказать об игре “Четыре краски”, которую придумал популяризатор науки Стивен Барр
20. В первой партии выиграл первый игрок благодаря охвату всех цветов, причём неповторяющихся, на 5 ход Я
21. В следующей партии за второго игрока я пробовал при любой возможности закрашивать в цвета, которые уже
22. В третьей партии оба игрока делали так, чтобы область могла охватить только 3 цвета, то есть
23. В итоге в игру ‘четыре краски’ можно играть бесконечно при соблюдении одного условия: Начиная со второго
24. В заключение я решил попробовать теорему о четырех красках на практике
26. Скачать презентацию

Слайд 2

Цель:
узнать, что такое теорема о четырех красках

Слайд 3

Задачи:
·Изучить историю теоремы о четырех
красках.
·Преобразовать теорему в графы.
·Познакомиться с инструкцией

игры
“Четыре краски”.

Слайд 4

Проблема четырех красок заключается в том, чтобы закрасить области любой карты

максимум в 4 цвета, причем чтобы никакая область одного цвета не имела границу с областью такого же цвета

✔ ?

Слайд 5

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

лучше всего раскрашивать.

Слайд 6

(1831-1899)
В 1852 году при раскрашивании карты Британии студент Френсис Гутри выдвинул

эту гипотезу:
любую карту можно раскрасить четырьмя цветами, при условии, чтобы никакие две смежные области (имеющие общую границу) не оказались окрашенными в один и тот же цвет
Проблема возникла в том, чтобы решить, верна ли гипотеза.

Слайд 7

Альфред Кемпе
в 1879 опубликовал решение проблемы по его мнению
Перси.Дж.Хивуд.
В 1889 опровергнул

это решение

Слайд 8

В 1880 предложил еще одно доказательство проблемы четырёх красок, которое опровергли

в 1891

Питер Тэйт

Слайд 9

Кеннет Аппель и Вольфганг Хакен
В 1971 окончательно доказали теорему при помощи

компьютера

Слайд 10

Теорему о четырех красках можно представить как граф
Для этого достаточно ужать

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

Слайд 11

Обязательное условие: граф должен быть плоским( ребра не должны пересекаться)

Слайд 12

Рассмотрим эти графы
Почему для раскраски первого хватает всего 2 цвета, а

для второго 4?

Слайд 13

Назовем сложностью графа количество цветов для раскраски. Чем больше цветов тем

граф сложнее.

Граф упорядочен в соответствии с определёнными логическими правилами, количество узлов, соединённых с каждым узлом не важно, как и количество элементов в графе

Слайд 14

Слайд 15

На самом деле увеличивают количество цветов в графе компоненты с большим

количеством связей.

Чтобы доказать это, мы объединим эти графы, окрашенные в 3 цвета, без увеличения общей сложности и с увеличением:

Слайд 16

Здесь мы как бы ограничили доступ второму графу к первому(ромбу)

Слайд 17

Во втором графе узлы 1, 2 и 4 имеют соединения с более крупным подграфом. В этом

случае нет одного узла, ограничивающего доступ к ромбу; более крупный граф имеет возможность соединяться с несколькими узлами в ромбе. Это привело к увеличению сложности всей системы.

Слайд 18

Граф можно покрасить в 4 цвета из-за сильной взаимосвязности его компонентов

Слайд 19

Также хочу рассказать об игре “Четыре краски”,
которую придумал популяризатор науки Стивен

Барр

Слайд 20

В первой партии выиграл первый игрок благодаря охвату всех цветов, причём

неповторяющихся, на 5 ход

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

Слайд 21

В следующей партии за второго игрока я пробовал при любой возможности

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

Теперь выиграл 2 игрок благодаря тому, что 1 игрок
допустил ошибку.

Слайд 22