Дурдом в клеточку

Не может мир быть чёрно белым... Ну, не может, - хоть дерись... Белый цвет, он составной, и его можно разложить, это показал Ньютон... Допустим, брать в расчёт начнём мы семь цветов... Их знает ведь любой художник - Каждый Охотник Желает Знать Где Сидит Фазан... Вспомнила их, госпожа моя Надежда, дум моих причал?
Восьмой лишь будет тьмой слоплошной... Вот и представь себе сферу из восьмиугольников... Это во первых... Теперь о магнитах и токах...
Если ток менять может частоту, соответветственно меняя частоту магнитных переполюсовок, свет то он тоже различается лишь по частоте, а следовательно по энергетике, кто сильнее, тот и сверху, так что оболочка одной сферы должна быть семислойной... Либо слой один, - но волнистенький такой, - тут впадина, там выпуклось, и между ними впуклостей многообразность...

ха-ха... представила себе, что будет с человеком, если ему таким вот мячиком для тениса заехать в лоб? ухохотаться можно со смеху!

Представить шар, составленный из квадратиков!!! - Где ты такой видала? - а вот футбольных мячей, сшитых и из пятиугольников, и из многоугольников с большим числом сторон, их видимо-невидимо... Неужто ты никогда не знала про всевозможные Плановые тела?

Короче, твоя матрёшка очень хороша... Но разноцветный мир более устойчив, чем чёрно-белый!

Да, чуть не забыл... Есть какая-то теорема, сколькими разными цветами можно раскрасить то ли глобус, то ли карту... Вот в Википедии статью подходящую нашёл... Название её - раскраска графов...
-----------
Теперь что поместится в рецензию, то и прочтёшь!
--------

Первые результаты были получены для плоских графов в задаче раскрашивания карт. Пытаясь раскрасить карту округов Англии, Францис Гутри сформулировал проблему четырёх красок, отметив, что четырёх цветов достаточно, чтобы раскрасить карту так, чтобы любые два смежных региона имели разные цвета. Его брат передал вопрос своему учителю по математике, Огастесу де Моргану, который упомянул о нём в своем письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял эту проблему на встрече Лондонского математического сообщества в 1878 году. В том же году Тэйтом было предложено первое решение этой задачи. Раскраску вершин первоначального графа он свел к раскраске рёбер двойственного графа и предположил, что эта задача всегда имеет решение. В 1880 году Альфред Кемпе опубликовал статью, в которой утверждалось, что ему удалось установить результат, и на десятилетие проблема четырёх цветов считалась решенной. За это достижение Кемпе был избран членом Лондонского Королевского общества и позже — президентом Лондонского математического сообщества.

В 1890 году Хивуд нашёл ошибку в доказательстве Кемпе. В этой же статье он доказал теорему пяти красок, показав, что любая плоская карта может быть раскрашена не более, чем пятью цветами. При этом он опирался на идеи Кемпе. В следующем столетии было разработано большое количество теорий в попытках уменьшить минимальное число цветов. Теорема четырёх красок была окончательно доказана в 1977 году учеными Кеннетом Аппелем и Вольфгангом Хакеном с использованием компьютерного перебора. Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований. Доказательство теоремы четырёх красок является одним из первых доказательств, в которых был использован компьютер.

В 1912 году Джордж Дэвид Биркхоф предложил использовать для изучения задач раскраски хроматический многочлен, являющийся важной частью в алгебраической теории графов. Хроматический многочлен впоследствии был обобщён Уильямом Татом (многочлен Татта. Кемпе в 1879 году уже обращал внимание на общий случай, когда граф не являлся плоским. Много результатов обобщений раскраски плоских графов на поверхности более высоких порядков появилось в начале 20 века.

В 1960 году Клод Бердж сформулировал гипотезу о совершенных графах, мотивированное понятием из теории информации, а именно нулевой ошибкой ёмкости графа, представленным Шенноном. Утверждение оставалось неподтвержденным на протяжении 40 лет, пока не было доказано как знаменитая строгая теорема о совершенных графах математиками Чудновской, Робертсоном, Сэймуром и Томасом в 2002 году.

Раскраска графов как алгоритмическая проблема начала изучаться с 1970-х годов: определение хроматического числа — входит в число 21 NP-полных задач Карпа (1972). И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления и стягивания Зыкова. С 1981 года раскраска графа применяется для распределения регистров в компиляторах.

Полёт Орла   12.08.2017 15:06   •   Заявить о нарушении