На головну

Завдання про 4 фарбах

  1.  Апроксимації В ЗАДАЧАХ МОДЕЛЮВАННЯ
  2.  Б) Завдання визначення кінематичних характеристик руху точки - швидкості точки і прискорення точки.
  3.  Ваше завдання - змусити підлеглих працювати якнайкраще
  4.  Взаємозв'язок між вихідної і двоїстої завданнями.
  5.  Друге завдання (зворотна) - визначити рух, яке буде здійснювати точка маси m під дією заданих сил.
  6.  Г., марта 2. - Указ про завдання Сенату в відсутності царя.
  7.  Геометричне тлумачення рішень Поле напрямків. Інтегральні криві. завдання Коші

Це одна з найзнаменитіших завдань теорії графів і математики взагалі.

Чи достатньо чотирьох фарб для розмальовки будь-якої політичної карти світу так, щоб дві держави, які мають спільний кордон, були розфарбовані в різні кольори?

Як ілюстрацію можна взяти довільну "карту". Для полегшення аналізу представимо держави у вигляді вершин графа. "Розмальовку" відобразимо цифрами.

Дуги будуть говорити про наявність спільних кордонів. Не повинно бути дуг, що з'єднують вершини з однаковими цифрами.

1 2 1

1 2 1

 1 1 4 2 1 4

Так що завдання можна переформулювати так:

Скільки необхідно фарб в планарном графі, щоб будь-які дві суміжні вершини були розфарбовані різними кольорами?

теорема: Трьох фарб мало.

1

Приклад доводить, що 3-х фарб мало

2 3

теорема: Для розмальовки будь-якого планарного графа достатньо 5-ти фарб

Доведення:

1) Для будь-якого планарного графа з n <= 5 теорема справедлива.

2) Нехай будь-який планарний граф з n вершинами 5-розфарбовувати.

Доведемо справедливість цього і для графа з n + 1 вершинами, спираючись на доведений факт, що в будь-якому плоскому графі є хоча б одна вершина ступеня не вище п'яти. Оголосимо таку вершину n + 1-им.

       
   
 Якщо ця вершина має ступінь не більш чотирьох, то 5 фарб вистачить. Але якщо ступінь п'ять, то з 1-ої вершини будуємо всі можливі ланцюга, де чергуються вершини 1 і 3: Тут можливі два випадки: 1). Жодна з ланцюгів не замкнулася на третю вершину. Тоді міняємо квітами все 1-і і 3-ие вершини і n + 1 -ю вершину фарбуємо в 3-ий колір;


3 3

 1 3

 1 3

2

5

n

2.) Одна з ланцюжків замкнулася на 3, тоді з вершини з номером 2 будуємо ланцюг 2-4. Жодна з цих кіл не замкнеться на 4-ю вершину (тому що граф планарний!). Міняємо кольору 2 і 4 в цьому ланцюзі. І фарбуємо n + 1-ю вершину в колір 2.

Таким чином, те, що п'яти фарб досить, доведено.

Повертаючись до чотирьох фарб слід сказати, що американськими математиками була доведена теорема, про те, що чотирьох фарб досить. Однак, в цьому доказі є кроки, пов'язані з дуже великими переборами варіантів, виконані з використанням комп'ютера (піди перевір). Так що з точки зору «пуританської» математики можна вважати, що теорема поки не доведена ...

 




 Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |  теорія графів |  теорема Ейлера |  Повні графи і дерева |  дерева |

© um.co.ua - учбові матеріали та реферати