Comments 13
упущен важный момент о степени детализации карты. Если ребра графа будут представлять собой дороги, а в качестве узлов будут города, все становится сложнее. Хорошие отправные точки на подумать в этом направлении: эта статья и книжка "Хаос. Создание новой науки"
На эту тему даже рассказ веселый есть. Мартин Гарднер. Остров пяти красок.
UFO just landed and posted this here
Мне, навскидку, кажется, что для оценки и сравнения сложности лучше рассматривать количество рёбер взаимосвязи между модулями (и число самих модулей, но в меньшей степени), а не хроматическое число. При этом оценка
1. Будет работать для любого графа, а не только планарного.
2. Не будет ограничена (значением 4), как и сложность.
1. Будет работать для любого графа, а не только планарного.
2. Не будет ограничена (значением 4), как и сложность.
У Вас на главной картинке зеленый узел должен быть соединен с 4-мя другими узлами, а не с тремя.
Вообще не понял. Для оценки "сложности" графа использовать сложно вычисляемые вещи? (Кто увлекался математикой в детстве — помнит сложность раскрашивания, остальные могут поискать алгоритмы раскрашивания… я нашёл алгоритм через последовательный выбор максимальных независимых множеств, NP-полная задача).
Что, попроще метрики не нашлось?
Как будем рекурсию изображать графом?
Sign up to leave a comment.
Чему нас может научить теорема о четырех красках в разработке ПО