Подскажите пожалуйста кто дол***б, я или автор

Nonnik

Вот что пишут уроды
Думаю, что это всё гон и они просто о**ели, аж передёргивает

natunchik

ЛОЛ
>>Максимально возможный полный планарный граф К4 , откуда следует любой планарный граф 4-раскрашиваем.
Вообще-то наоборот =) Из раскрашиваемости следует планарность =)

h_alishov

Из раскрашиваемости следует планарность

K(3,3) не является планарным, но при этом он раскрашивается в два цвета. Так что все верно, из планарности по теореме о четырех красках следует 4-раскрашиваемость.

h_alishov

Гыгы.
Гипотеза четырех красок

Не гипотеза, а теорема. В 1976 году В.Хакен и К.Аппель доказали теорему о четырех красках. Изложено в
[1] K. Appel, W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977 429-490.
[2] K. Appel, W. Haken, J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977 491-567.

n- полный граф n-раскрашиваем, так как достаточно убрать одну связь, и граф становится n-1- раскрашиваем - не связные вершины имеют один цвет.
Максимально возможный полный планарный граф К4 , откуда следует любой планарный граф 4-раскрашиваем.
Гипотеза 4-х красок доказана, как частный случай 1.
Нечётные циклы сведём к К3 (треугольнику) по изоморфизму, ребро также рассмотрим, как К2 и т.д.

Отличное доказательство! Особенно хорошо выглядит слово и т.д.
На основе данного доказательства автором был разработан алгоритм оптимальной раскраски произвольного графа, составлена программа на языке Qbasic и экпериментально проверенна его верность.

О да, это круто. Математика у нас наука сугубо экспериментальная. Особенно круто, когда надо проверить все возможные графы.

LeeSream

Как ярый догматик скажу, что дб автор, ибо это(простое доказательство теор 4красок) было бы слишком существенный прорыв в ТеоГр. Ознакомившись с доказательством строгой логики пока не вижу. Буду думать над ним.

Nonnik

Ну так это ладно, пусть пишут свои ебан***утые доказательства, так меня вот от чего передёрнуло
" После оплаты счета, который Вы получите автоматически, на Ваш email будут отправлены реквизиты предприятия, представившего данную информацию на нашем сайте
Я просто тут тоже еба...лся чуть с этой раскраской, придумал супер жадный алгоритм для которого не могу найти пример чтобы он красил не в минимальное количество цветов.
A1:
Берём нераскрашенную вершину максимальной степени (строгий порядок вводим конечно -по имени сортируем на крайняк)
Если её можно покрасить каким-нибудь из уже использованных цветом (Краски тоже строго упорядочены, всегда берём меньшую из возможных то красим, если нет - вводим новый цвет.
Сколько не проверял, (на всех графах с 5 вершинами или меньше) всегда правильно работает, так что, надо тоже счёт открывать и идиотам этим решение слать.

h_alishov

Сколько не проверял, (на всех графах с 5 вершинами или меньше) всегда правильно работает

Для восьми вершин есть пример, когда для раскраски графа достаточно 2 цветов, а у тебя алгоритм красит в 3:

Nonnik

Супер!
Большое спасибо!
Но врятли программой на qbasice переберёшь все графы до 8 вершин, так что для них всё равно прокатит, думаю

h_alishov

Да, у меня тоже сомнения насчет той мегапрограммы.
Оставить комментарий
Имя или ник:
Комментарий: