Комментарии 13
упущен важный момент о степени детализации карты. Если ребра графа будут представлять собой дороги, а в качестве узлов будут города, все становится сложнее. Хорошие отправные точки на подумать в этом направлении: эта статья и книжка "Хаос. Создание новой науки"
-1
На эту тему даже рассказ веселый есть. Мартин Гарднер. Остров пяти красок.
+2
НЛО прилетело и опубликовало эту надпись здесь
Мне, навскидку, кажется, что для оценки и сравнения сложности лучше рассматривать количество рёбер взаимосвязи между модулями (и число самих модулей, но в меньшей степени), а не хроматическое число. При этом оценка
1. Будет работать для любого графа, а не только планарного.
2. Не будет ограничена (значением 4), как и сложность.
1. Будет работать для любого графа, а не только планарного.
2. Не будет ограничена (значением 4), как и сложность.
0
У Вас на главной картинке зеленый узел должен быть соединен с 4-мя другими узлами, а не с тремя.
+3
Вообще не понял. Для оценки "сложности" графа использовать сложно вычисляемые вещи? (Кто увлекался математикой в детстве — помнит сложность раскрашивания, остальные могут поискать алгоритмы раскрашивания… я нашёл алгоритм через последовательный выбор максимальных независимых множеств, NP-полная задача).
Что, попроще метрики не нашлось?
0
Как будем рекурсию изображать графом?
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Чему нас может научить теорема о четырех красках в разработке ПО