Чему нас может научить теорема о четырех красках в разработке ПО

[osharper]

упущен важный момент о степени детализации карты. Если ребра графа будут представлять собой дороги, а в качестве узлов будут города, все становится сложнее. Хорошие отправные точки на подумать в этом направлении: эта статья и книжка "Хаос. Создание новой науки"

[System12]

Следующим шагом будет использование логистики как инструмента для упорядочивания графа.

[alan008]

На эту тему даже рассказ веселый есть. Мартин Гарднер. Остров пяти красок.

[multiprogramm]

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

[mayorovp]

Так хроматическое число тоже же определено для любого графа…

[multiprogramm]

Верно. Запутался слегка. Со слов «При этом оценка» написал чушь.

[vivlav]

У Вас на главной картинке зеленый узел должен быть соединен с 4-мя другими узлами, а не с тремя.

[PatientZero]

Картинка не моя, это перевод, но да, вы правы.

[NoorBall]

И вообще его можно закрасить 3-мя цветами, поэтому пример немного непоказательный

[aamonster]

Вообще не понял. Для оценки "сложности" графа использовать сложно вычисляемые вещи? (Кто увлекался математикой в детстве — помнит сложность раскрашивания, остальные могут поискать алгоритмы раскрашивания… я нашёл алгоритм через последовательный выбор максимальных независимых множеств, NP-полная задача).
Что, попроще метрики не нашлось?

[nailer]

Как будем рекурсию изображать графом?