ortheos (ortheos) wrote,
ortheos
ortheos

Category:

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


Простое доказательство теоремы четырех красок.

-----------------------------------------------

Определения:

0) Областью называется часть плоскости, ограниченная замкнутой кривой без пересечения последней самой себя.

1) Границей двух областей является часть кривой, принадлежащая им обоим , при этом не являющаяся точкой.

2) Группой областей называется множество областей на плоскости, каждая из которых  имеет границу хотя бы с одной другой областью из этого множества.

3) Тесной группой областей размерности N называется группа областей, каждая из которых граничит с N-1 остальными областями

------------------------------------------------

Лемма ( о невозможности существования тесной группы размерности 5 на плоскости)

1. На плоскости возможно существование тесной группы размерности 4.

2. Из определения тесной группы размерности 5 следует, что каждая область в этой группе одновременно входит в тесную группу размерности 4 ( из того, что каждая область граничит с каждой из 4 оставшихся областей следует, что каждая область граничит с каждой из трех любых областей в этой группе)

3. Создание тесной группы размерности 5 возможно только добавлением одной и только одной кривой без самопересечения ( в противном случае образуется больше пяти областей, из которых по крайней мере одна из них не входит в тесную группу размерности 5, и следовательно — исключается из доказательства)

4. Добавление кривой к существующим областям на плоскости возможно в следующих вариантах:

5. Количество внутренних границ между областями в тесной группе очевидно равно (N-1)*N/2 ( коэффициент 2 означает, что граница области А с областью Б — та же самая, что граница области Б с областью А)

Для тесной группы размерности 4 это 6 общих внутренних  границ (3*4/2) , для тесной группы размерностью 5 — это 10 общих границ (4*5/2).

6. Из п.4 следует , что при образовании новой тесной группы размерности 5 возможно максимум 3 новых границы. То есть в получившейся группе должно быть 9 внутренних границ. В то время как по определению, в тесной группе размерности 5 должно быть 10 внутренних границ.

Таким образом, мы пришли к выводу, что невозможно существование на плоскости тесной группы размерности 5.

-----------------------------------------------------

Теорема 4 красок.

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

Доказательство.

Примем, что существует какая-либо карта на плоскости, которая требует для своего раскрашивания по указанному условию 5 красок. Это означает, что при любом варианте раскрашивания этой карты существует по крайней мере одна область, для которой необходима 5 краска, то есть она граничит минимум с четырьмя областями, каждая из которых окрашена в иной цвет.

1. Очевидно, что каждая из этих областей в данном варианте раскраски необходима окрашена именно в этот цвет. В противном случае одна из этих областей могла быть окрашена в другой цвет, и тогда исходная область не нуждается в 5-й краске.

2. Очевидно, что тезис 2 справедлив для всех вариантов раскрашивания карты.

3. Поскольку 5 краску мы выбрали произвольно, «пятой краской» мы можем назвать любую краску из пяти. Соответственно для любой из минимум четырех областей, соседствующих с областью, которая необходимо окрашена в пятый цвет, справедливы рассуждения, справедливые для этой области. То есть, каждая из этих областей необходимо окрашена в свой цвет, поскольку граничит минимум с четырьмя другими областями, каждая из которых необходимо окрашена в свой цвет. Отсюда вывод.

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

5. Примем, что на карте существует N областей , необходимо окрашенных в свой цвет при конкретном варианте раскрашивания.

6. Из пункта 4 следует, что в то же время на той же карте должно быть минимум  N+4N областей , необходимо окрашенных в свой цвет при конкретном варианте раскрашивания.

7.Это возможно в одном единственном случае. Если все эти области образуют тесные группы размерности не меньше 5, существование которых на плоскости опровергнуто в лемме. (существование тесных групп размерности большей, чем 5, на плоскости невозможно без существования тесных групп размерности 5)

Следовательно, исходное предположение о существовании на плоскости карты, для окрашивания которой необходимо не менее 5 красок — неверное.

Теорема доказана.

Следствия.

А.  Доказательство справедливо для бесконечных карт, исключая фрактальные и карт областей бесконечно малого размера.

Б. Алгоритм раскрашивания любой карты на плоскости 4мя красками.

1. Случайная область раскрашивается в цвет n.

Переход на следующую по часовой стрелке область

2. Любая соседняя область раскрашивается в цвет n+1.

3. Область , соседняя с двумя областями , окрашивается в цвет mod((n(1)+n(2))/4) (то есть цвет, равный остатку от деления суммы соседних областей на 4) , если n(2)=n(1)+1 или n(1)=n(2)+1 . В противном случае она окрашивается в цвет mod(|n(1)-n(2)|/4)

4. Если существует область , соседняя с областями 1,2 и 3, она окрашивается в оставшийся цвет 4.

5. См. 1.


Tags: Секретные материалы, нанотехнологии, нафталин
Subscribe

  • Цыгачесса и кузина Лилибет.

    Мухосранская самозванка решила пропиариться на смерти летального принцовируса Филиппа. И сделала это одновременно и хитрожопо, и предельно тупо. (…

  • Не издевайтесь над чемпионами по каратэ.

    Мужик делал харрасмент и абьюз чемпионке мира по каратэ путем размахивания бамбуковым мечом, а она плакала и не хотела ходить на тренировки. Япония…

  • Самая человечная религия в мире.

    Во время президентства Зьема (Вьетнам) общество подверглось реформам, соответствующим ценностям католицизма и конфуцианства. Были закрыты бордели,…

promo ortheos september 18, 2014 10:40 25
Buy for 10 tokens
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments

  • Цыгачесса и кузина Лилибет.

    Мухосранская самозванка решила пропиариться на смерти летального принцовируса Филиппа. И сделала это одновременно и хитрожопо, и предельно тупо. (…

  • Не издевайтесь над чемпионами по каратэ.

    Мужик делал харрасмент и абьюз чемпионке мира по каратэ путем размахивания бамбуковым мечом, а она плакала и не хотела ходить на тренировки. Япония…

  • Самая человечная религия в мире.

    Во время президентства Зьема (Вьетнам) общество подверглось реформам, соответствующим ценностям католицизма и конфуцианства. Были закрыты бордели,…