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

Автор темы sukhikh 
ОбъявленияПоследний пост
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
ОбъявлениеHuawei - Research scientist (math)22.06.2021 11:25
ОбъявлениеPostdoc: Stochastics and algorithmics behind network problems (Netherlands)08.10.2021 08:36
29.08.2021 15:47
Теорема о четырёх красках
Теорема.
Если некоторая фигура разделена на части любым способом и её части раскрашены по-разному так, что фигуры с общей границей в виде линии любой длины окрашены в разные цвета, то для этого может потребоваться четыре краски, но не больше.
Доказательство.
Рассмотрим область 1 на плоскости. Пусть она окружена со всех сторон n областями, которые имеют с ней общую границу в виде линии. Пусть каждая из этих n областей имеет общую границу в виде линии со всеми другими из этих n областей. Нам надо определить максимальное значение n(max) при этих условиях. (Вся остальная часть плоскости нас не интересует, так как она не имеет границы с областью 1).
Каждая из этих n областей может иметь границу с двумя другими из этих n областей, которые могут иметь границу между собой. Таким образом, n может быть равно 3.
Может ли быть n>3 ? Пусть n = 4. В этом случае области 2 и 4, а также 3 и 5 не имеют общей границы, так как между ними лежит область 1.
Пусть области 3 и 5 имеют общую границу. Но и в этом случае области 2 и 4 не имеют общей границы, так как между ними продолжает лежать область 1. Области 2 и 4 могут иметь общую границу только за счёт исчезновения общей границы у областей 1 и 3, или у областей 1 и 5, или у областей 3 и 5.
Значит, n не может быть равно 4.
Рассуждения для более высоких значений n аналогичные.
Значит, n(max) = 3 . Добавление внутренней области 1 даёт в сумме 4 краски.
29.08.2021 18:34
.
Отсутствие $K_5$ в графе смежности не доказывает, что Вам глобально удастся раскрасить весь граф четырьмя красками.
29.08.2021 20:58
А 3 краски
А чтобы хватило 3 краски, то надо разрезать так, чтобы одна наружная часть касалась только одной из оставшихся частей. То есть нарезать на 3 полосы , одна из которых, крайняя, разделена пополам.
А чтобы хватило 2 красок надо нарезать на 4 полосы.
То есть сколько фигур касается в одной точке, столько красок и получится.



Редактировалось 3 раз(а). Последний 29.08.2021 21:07.
29.08.2021 22:56
.
Цитата
alexx223344
То есть сколько фигур касается в одной точке, столько красок и получится.

Это не так. Если рассмотреть в качестве карты поверхность тетраэдра, а в качестве фигур - его грани, то окажется, что в одной точке сходятся не более трех фигур, но тремя красками все равно не обойтись.
30.08.2021 12:26
Топология иная.
Так это топология другая, то было для конечной фигуры на плоскости. А у описанной вами, если ее развернуть в плоскость, появится отверстие в середине.
30.08.2021 13:05
.
Цитата
alexx223344
Так это топология другая, то было для конечной фигуры на плоскости. А у описанной вами, если ее развернуть в плоскость, появится отверстие в середине.

Ну проколите одну из граней посередине и разверните на плоскость, в чем проблема?
Все равно будет выполняться условие, что в одной точке сходится не более трех фигур. Но тремя цветами Вы эту конструкцию не раскрасите.
30.08.2021 21:54
Тетраэдр.
Ну эту да, кто же спорит.
Тетраэдр это по топологии та же сфера. ее эквивалент это нарезанные ломти, посередине которые представляют кольца, а 2 крайних окружности. Дальше смотрите на сколько частей нарезано каждое кольцо и окружности. Окружности как частный случай красите так как я описал вначале для конечной фигуры на плоскости. Потом промежуточные.
Для более изощренной нарезки иные закономерности. Для них даже есть разница с какой именно грани начинаете красить.
31.08.2021 16:36
еще раз
Цитата
alexx223344
То есть сколько фигур касается в одной точке, столько красок и получится.

посмотрите, например, на такую картинку
http://900igr.net/up/datas/117703/013.jpg - карта справа.

В каждой точке этой карты касается не более трех фигур. Однако трех красок для раскраски не достаточно. Ваше утверждение ложно.



Редактировалось 1 раз(а). Последний 31.08.2021 16:36.
31.08.2021 17:11
Кольцо + площадь.
Данная фигура представляет собой кольцо разделенное на 3 части, это уже 3 краски. И дополнительная фигура, касающаяся одной стороны кольца. Это еще одна краска. Также отсутствует фигура последняя, касающаяся кольца по наружке, но оно может быть также окрашено как и внутреннее, тем же цветом. Итого 4 краски минимум. В первом случае же рассматривалось не кольцо, а фигура как на вашем левом рисунке, и не было речи о замкнутых линиях. Было указано о линиях любой длины, но не замкнутые бесконечные линии в виде окружности. Вы точку заменили окружностью. Конечно ее надо тоже красить. Далее, если кольцо состоит из более чем 3 частей, то может хватить и 3 красок для например 4 частей в кольце.
Итого. Для четного количества в кольце надо 3 краски. Для нечетного и больше трех частей в нем - 4 краски.
Для окружности вписанной в другую - 2 краски.
Вот и весь закон для вашей фигуры. Можно писать прогу расчета числа красок для такого типа.
31.08.2021 17:29
.
Цитата
alexx223344
Данная фигура представляет собой кольцо разделенное на 3 части, это уже 3 краски. И дополнительная фигура, касающаяся одной стороны кольца. Это еще одна краска. ... Итого 4 краски минимум.

Это и показано на картинке.
И это есть контрпример к Вашему утверждению:

Цитата
alexx223344
То есть сколько фигур касается в одной точке, столько красок и получится.

Потому что фигур касается не более 3, а красок все равно надо 4.
understand?
31.08.2021 17:47
Не все равно , а при данном случае.
Цитата
alexx223344
То есть сколько фигур касается в одной точке, столько красок и получится.

Потому что фигур касается не более 3, а красок все равно надо 4.
understand?[/quote]

Не все равно, а при данном случае. А в данном случае образовано кольцо, то есть замкнутая на себя фигура. А речь была о левом рисунке.
Вы понимаете что такое эквивалент в представлении. Он нужен для упрощения понимания при создании алгоритмов расчета например. Я его вижу так.
Больше вам скажу что ваша правая фигура представляет шар. И топологически она трехмерна.
31.08.2021 18:05
.
Цитата
alexx223344
Больше вам скажу что ваша правая фигура представляет шар. И топологически она трехмерна.

А можно поинтересоваться, что Вы понимаете под словосочетанием топологически трехмерная фигура?
01.09.2021 21:34
Эквивалент
Что это эквивалент 3-х мерной фигуры, нарисованной на плоскости. Одна часть просто не окрашена и отсутствует. Это та часть, которая вокруг вашей правой фигуры. Я увидел так. Но видимо к этой задаче подходов много, не знаю.
05.09.2021 21:00
Рождение нового измерения.
Я понял разницу. Заменив точку на окружность вы родили новое измерение в центре правой фигуры. То есть из ничего родилось измерение всего одной мыслью что-то добавить и захотеть получить новый результат.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти