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

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

Петрянкин
Василий
ученик 8В класса
МАОУСОШ №58

Изучить правила раскрашивания географических карт и опытно – экспериментальным путем проверить задачу четырёх красок

Задачи работы:

1. Рассмотреть свойства плоских графов
2.Изучить правила раскраски графов
3.Раскраска географических карт с помощью графов
4.Разработка сборника головоломок

Леонард Эйлер(1707 – 1783гг)

Задача о кёнигсбергских мостах

Граф к задаче о кёнигсбергских мостах

Точки A, B,C,D - вершины графа
Линии – ребра графа

Свойства связного графа

Число нечётных вершин графа всегда четно.
Невозможно начертить граф, который имел бы нечетное число нечетных вершин

Свойства связного графа

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком




(Решение задачи о кёнигсбергских мостах)

Свойства связного графа

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

Свойства связного графа

Граф все вершины у которого четные, можно начертить одним росчерком, при этом можно начать с любой вершины и закончить его в той же вершине.

Формула Эйлера о плоском графе

Для любого плоского графа имеет место соотношение
В - Р + Г = 2

Граф который можно начертить одним росчерком называется
уникурсальным графом

Эскиз портрета Эйлера

Знак, состоящий из двух рогов Луны,
который Магомет описывал одним
росчерком

Эйлеровы графы

Граф все вершины которого четные
( можно начертить одним росчерком)




Эйлеровы графы применяются при составлении одностороннего
движения в городе.

Теорию графов можно использовать при раскраске географических карт

Математическая задача

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

Раскраска карты с помощью графов

Территории стран – грани графа
Границы стран – ребра графа
Точки пересечения границ – вершины графа

Правила раскраски карты

Если карта на плоскости представляет собой эйлеровый граф, то его можно раскрасить всего двумя красками.

Правила раскраски карты

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

Правила раскраски карты

Карту Северной Америки
можно раскрасить
тремя красками,
если не учесть
моря и океаны

Правила раскраски карты

Любую нормальную карту можно раскрасить пятью разными красками

Вершинная раскраска графа

Вершины графа – страны
Ребра – границы этих стран
Проблема четырёх красок :
Верно ли, что хроматическое
число любого графа,
расположенного на плоскости
не больше четырёх?

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

Карта Северной Америки в графах

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

Карта Южной Америки в графах

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

Карта Африки в графах

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

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

вывод

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

Московский метрополитен

Карта Республики Башкортостан