Раскраска карты, задаваемой графом

[sotu]

Есть проблема с задачей про граф. Подскажите, пожалуйста, кому не сложно.

Условие задачи следующее: на плоскости дан связный граф, степень каждой вершины равна 4. Вопрос: каково минимальное число цветов для раскраски этой карты?

Сделал следующее:
По ф-ле Эйлера, $v-e+f=2$, где $v$ - вершины графа, $e$ - рёбра графа, $f$ - число связных областей, на которые граф делит плоскость (как я понял, это и есть раскрашиваемые участки карты).
Пользуясь тем, что сумма степеней всех вершин графа равна удвоенному количеству рёбер, получаю $4v=2e$, то есть $e=2v$, откуда $f=2+v$

Посмотрел частные случаи:
Если вершина 1, то ребра 2 (петли), областей 3. ( цвета тоже 3)
Если вершин 2, то придется рисовать кратные ребра, а всего ребер будет 4, тогда имеем 4 области, но цвета всё ещё нужно 3.

Как доказать, что и в общем случае получится 3 цвета, если это вообще верно?

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[situs]

sotu в сообщении #1395755 писал(а):

Как доказать, что и в общем случае получится 3 цвета, если это вообще верно?

Попробуйте расположить данный Вам граф на сфере. Рассмотрите минимальный такой граф на сфере. Какое минимальное число цветов потребуется в этом случае?

[sqribner48]

situs

situs в сообщении #1395903 писал(а):

Рассмотрите минимальный такой граф на сфере. Какое минимальное число цветов потребуется в этом случае?

А почему именно на сфере? А не на кубе, или на бутылке Клейна? А мне, например, больше нравится тор.

(Оффтоп)

И в этом случае Великий Диэдр мне подсказывает, что минимальное число цветов равно 4.
Делайте Ваши ставки, господа. Кто больше?

[Munin]

sotu в сообщении #1395755 писал(а):

Посмотрел частные случаи:
Если вершина 1, то ребра 2 (петли), областей 3. ( цвета тоже 3)

Нельзя ли эту карту раскрасить в меньшее число цветов?

[sqribner48]

sotu

Munin в сообщении #1395912 писал(а):

sotu в сообщении #1395755 писал(а):

Посмотрел частные случаи:
Если вершина 1, то ребра 2 (петли), областей 3. ( цвета тоже 3)

Нельзя ли эту карту раскрасить в меньшее число цветов?

Можно раскрасить в два цвета. Две области, заданные двумя петлями, не смежны по ребру (см. Теорему о 4-х красках). Поэтому их можно раскрасить в один цвет. Плюс еще один цвет на закраску внешней области. Получается всего два цвета.

(Теорема о четырёх красках)

Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них.

Очевидно, что для псевдографов (графов с кратными ребрами и петлями) с любым числом вершин минимальное число цветов равно 2.
sotu, попробуйте доказать это.

[Munin]

sqribner48
В традициях форума - не давать полные решения простых учебных задач :-) а наталкивать спрашивающего на то, чтобы он сам до такого решения добрался.

[svv]

sqribner48 в сообщении #1395962 писал(а):

Две области, заданные двумя петлями, не смежны по ребру (см. Теорему о 4-х красках). Поэтому их можно раскрасить в один цвет.

Есть ещё вариант, когда одна петля вложена в другую, и тогда обе внутренние области смежны. Правда, и тут хватит двух цветов: «самая внутренняя» область красится в тот же цвет, что и внешняя.

Я имел в виду случай 1 вершины.

[arseniiv]

А карта обязательно должна задаваться как стали делать выше, или всё-таки вершины графа соответствуют областям карты, а рёбра указывают смежность областей? (Задача о раскраске карты именно так переформулировалась в своё время в раскраску графов.) И разрешены ли петли вообще?

[sqribner48]

Уважаемый Munin

Munin в сообщении #1395970 писал(а):

sqribner48
В традициях форума - не давать полные решения простых учебных задач а наталкивать спрашивающего на то, чтобы он сам до такого решения добрался.

Простите, погорячился (с). Я думал, что мое сообщение не является полным решением задачи и лишь даст ТС толчок для решения задачи с двумя вершинами.

sotu в сообщении #1395755 писал(а):

Если вершин 2, то придется рисовать кратные ребра, а всего ребер будет 4, тогда имеем 4 области, но цвета всё ещё нужно 3.

Кстати и здесь есть большое поле для раздумий... Пусть думает и решает.
Уважаемый arseniiv

arseniiv в сообщении #1395979 писал(а):

А карта обязательно должна задаваться как стали делать выше, или всё-таки вершины графа соответствуют областям карты, а рёбра указывают смежность областей? ..... И разрешены ли петли вообще?

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

[Munin]

Ну посмотрим. Надо дать ТС слово, а то он вообще пока ничего не написал.

[sotu]

Петли и прочее можно использовать, под картой подразумевается число связных областей, на которые граф делит плоскость. И ответ действительно 2, всем спасибо.

[B@R5uk]

sotu в сообщении #1395755 писал(а):

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

Почему именно так? В таком случае условие связности графа как-то излишне. Почему вершины графа не могут означать страны, а рёбра — границы между этими странами. Тогда, например, если в графе есть вершина, удаление которой делит граф на два несвязных, будет означать что страна, соответствующая этой вершине, является своего рода "водоразделом" для всех остальных стран, деля мир на две части. Или это можно интерпретировать как большую страну, которая окружает маленькую группу других стран со всех сторон. В любом случае, такая трактовка графа, на мой взгляд, более рациональная. Разве нет?

[sqribner48]

B@R5uk

B@R5uk в сообщении #1396861 писал(а):

Почему вершины графа не могут означать страны, а рёбра — границы между этими странами.

Именно так и должно быть в классической постановке задачи о раскраске карт.
Об этом и писал уважаемый arseniiv в своем сообщении:

arseniiv в сообщении #1395979 писал(а):

А карта обязательно должна задаваться как стали делать выше, или всё-таки вершины графа соответствуют областям карты, а рёбра указывают смежность областей? (Задача о раскраске карты именно так переформулировалась в своё время в раскраску графов.)

Так что ТС, по-видимому, дал не совсем правильную формулировку задачи.