Уважаемый
Muninsqribner48
В традициях форума - не давать полные решения простых учебных задач
а наталкивать спрашивающего на то, чтобы он сам до такого решения добрался.
Простите, погорячился (с). Я думал, что мое сообщение
не является полным решением задачи и лишь даст ТС толчок для решения задачи с двумя вершинами.
Если вершин 2, то придется рисовать кратные ребра, а всего ребер будет 4, тогда имеем 4 области, но цвета всё ещё нужно 3.
Кстати и здесь есть большое поле для раздумий... Пусть думает и решает.
Уважаемый
arseniivА карта обязательно должна задаваться как стали делать выше, или всё-таки вершины графа соответствуют областям карты, а рёбра указывают смежность областей? ..... И разрешены ли петли вообще?
Вы тысячу раз правы!
Я вообще считаю, что задача ТС-ом сформулирована не корректно. Решение данной задачи зависит от вида графов (учитываются кратные ребра или нет, учитываются петли или нет, или даже как учитываются петли в степенях вершин (в разных книгах это делается по-разному). И ничего не сказано про число вершин графа. Можно ведь выбрать граф с минимальным числом вершин и будет вам
счастье минимальное число цветов. И наиболее интересным (и сложным для решения) вариантом будет вариант задачи с простыми графами (т.е. с графами без петель и кратных ребер).
А ТС о них как раз ничего и не пишет. Так что, может быть, ТС для начала должен дать правильную формулировку задачи и решать ее по частям --- сначала для псевдографов, а потом --- для простых графов.