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

Подобни презентации

Презентация по темата: „Проблемът с четири цвята През 1850 г. шотландският физик Фредерик Гатри обърна внимание на факта, че проблемите с оцветяването на картите са много популярни сред студентите по математика“. - Препис:

1 Проблемът с четири цвята През 1850 г. шотландският физик Фредерик Гутри обърна внимание на факта, че проблемите с оцветяването на картите са много популярни сред студентите по математика в Лондон, а брат му Франсис Гатри формулира проблема с четири цвята, които след като рисуваха карта на графствата на Англия с четири цвята, изложи хипотеза, че това количество цветове е достатъчно, за да оцвети всяка карта. Той насочи вниманието на своя учител по математика А. Де Морган към проблема и информира за това приятеля си У. Хамилтън и по този начин допринесе за широкото му разпространение.

2 Годината на раждане на проблема с четири цвята се счита за 1878 г. (в някои публикации е посочена 1879 г.). Тогава, на една от срещите на Британското географско общество, изключителният английски математик А. Кейли ясно формулира задачата: „Да докаже, че всяка географска карта на равнина (или на глобус) може да бъде правилно боядисана с четири цвята . " Оцветяването на картата се нарича правилно, ако две държави, които имат обща граница на картата, са оцветени в различни цветове. От този момент нататък проблемът привлече вниманието на много видни математици. Четирицветният проблем

4 Определение на картата Нека дадена свързана проста графика бъде дадена на равнина, всеки връх на която има индекс по-голям от два. Тази графика разделя равнината на няколко области. Регионите ще се наричат ​​държави, а самият дял ще се нарича карта на равнина. Примери за карти са показани на фигурата.

5 Повърхност на многоъгълник В допълнение към равнината картите се разглеждат и на други повърхности, например върху сфера. Фигурата показва картите, образувани от повърхностите на правилни многогранници: тетраедър, куб, октаедър, икозаедър и додекаедър. Повърхността на многоъгълник може да се разглежда като карта, чиито държави са лицата на многогранника, а границите са неговите ръбове.

6 Упражнение 1 Кой е най-малкият брой цветове, необходими за правилното оцветяване на картата, показана на фигурата? Отговор: 2.

7 Упражнение 2 Кой е най-малкият брой цветове, необходими за правилното оцветяване на картите, показани на снимката? Отговор: а) 3; б) 4.

8 Упражнение 3 Кой е най-малкият брой цветове, необходими за правилното оцветяване на картата, образувана от два концентрични кръга с n дяла? Отговор: 3, ако n е четно и 4, ако n е нечетно.

9 Упражнение 4 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на картата, образувана от линиите, показани на фигурата? Отговор: 2.

10 Упражнение 5 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на картата, образувана от кръговете, показани на фигурата? Отговор: 2.

11 Упражнение 6 Докажете, че ако картата може да бъде правилно оцветена с два цвята, тогава всеки от нейните върхове има четен индекс (т.е. четен брой ръбове се сближават в нея). Доказателства. Ако поне един връх на картата имаше нечетен индекс, тогава за правилното оцветяване на такава карта ще са необходими повече от два цвята. И обратното също е вярно. Ако всеки връх на картата има четен индекс, тогава такава карта може да бъде правилно оцветена с два цвята. Опитайте се да го докажете сами.

12 Упражнение 7 Докажете, че ако една обикновена карта (т.е. една с три ръба, сходящи се във всеки връх) може да бъде оцветена правилно с три цвята, тогава всяка от нейните държави има четен брой страни. Доказателства. Ако поне една държава от картата имаше нечетен брой страни, тогава за правилното оцветяване на такава карта ще са необходими повече от три цвята. И обратното също е вярно. Ако всяка държава от обикновена карта има четен брой страни, тогава такава карта може да бъде оцветена правилно с три цвята. Опитайте се да го докажете сами.

13 Упражнение 8 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на картите, показани на снимката? Отговор: а) 4; б) 4; в 2.

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

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

16 Упражнение 11 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на картите, показани на снимката? Отговор: а) 3; б) 2; на 4; г) 3.

17 Упражнение 12 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на лицата на правилните многогранници? Отговор: а) 4; б) 3; в 2; г) 3; д) 4.

18 Упражнение 13 Кой е най-малкият брой цветове, необходими за правилното оцветяване на върховете на картата, показани на фигурата? Отговор: 3. Помислете за въпроса за оцветяването на върховете на карта в равнина. Оцветяването на връх се нарича правилно, ако всеки два върха, свързани с ръб, са оцветени в различни цветове.

19 Упражнение 14 Кой е най-малкият брой цветове, необходим за правилното оцветяване на върховете на картите, показани на фигурата? Отговор: а) 2; б) 3.

20 Упражнение 15 Кой е най-малкият брой цветове, необходими за правилното оцветяване на картата, образувана от два концентрични кръга с n дяла? Отговор: 2, ако n е четно и 3, ако n е нечетно.

21 Упражнение 16 Какъв е най-малкият брой цветове, необходими за правилното оцветяване на върховете на картите, показани на фигурата? Отговор: а) 2; б) 3; в 3; г) 4.

22 Упражнение 17 Кой е най-малкият брой цветове, необходими за правилното оцветяване на върховете на правилните многогранници? Отговор: а) 4; б) 2; в 3; г) 4; д) 3.

23 Упражнение 18 Докажете, че ако върховете на картата могат да бъдат правилно оцветени с два цвята, тогава всяка от нейните държави има четен брой страни. Доказателства. Ако поне една държава от картата имаше нечетен брой страни, тогава за правилното оцветяване на върховете на такава карта ще са необходими повече от два цвята.

24 Упражнение 19 Докажете, че ако върховете на карта, всяка държава от която има три страни, могат да бъдат оцветени правилно с три цвята, тогава всеки връх има четен индекс. Доказателства. Ако поне един връх на картата имаше нечетен индекс, тогава за правилното оцветяване на върховете на такава карта ще са необходими повече от три цвята.

25 Двойни карти Две карти се наричат ​​двойни, ако върховете на едната карта са в едно-към-едно съответствие със страните на другата, докато два върха на едната карта са свързани с ребро, ако и само ако съответните страни на другата карта са съседни. Пример за двойни карти е показан на фигурата. Същите числа маркират върховете на картата а) и съответните държави на картата б). Ясно е, че върховете на картата могат да бъдат оцветени правилно тогава и само ако страните от двойната карта могат да бъдат правилно оцветени със същия брой цветове. По-специално, върховете на всяка карта на равнината могат да бъдат правилно оцветени с не повече от четири цвята.

26 Упражнение 20 Покажете, че картите, показани на фигури а) и б), са двойни, като се установи едно към едно съответствие между върховете на единия и страните на другия, подобно на примера, даден по-рано. Отговор. Едно от възможните съвпадения е показано на фигурата.