Презентація на тему Проблема чотирьох фарб У 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 Покажіть, що карти, зображені на малюнках а) та б), є двоїстими, встановивши взаємно однозначну відповідність між вершинами однієї та країнами іншої, аналогічно даному раніше прикладу. Відповідь. Одне з можливих відповідностей показано малюнку.