2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Раскраска карты, задаваемой графом
Сообщение27.05.2019, 19:48 


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

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

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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение27.05.2019, 19:52 
Супермодератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение27.05.2019, 20:04 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 13:12 
Аватара пользователя


03/02/19
138
sotu в сообщении #1395755 писал(а):
Как доказать, что и в общем случае получится 3 цвета, если это вообще верно?
Попробуйте расположить данный Вам граф на сфере. Рассмотрите минимальный такой граф на сфере. Какое минимальное число цветов потребуется в этом случае?

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 14:25 


13/05/14
384
situs
situs в сообщении #1395903 писал(а):
Рассмотрите минимальный такой граф на сфере. Какое минимальное число цветов потребуется в этом случае?
А почему именно на сфере? А не на кубе, или на бутылке Клейна? А мне, например, больше нравится тор.

(Оффтоп)

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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 14:35 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
sotu в сообщении #1395755 писал(а):
Посмотрел частные случаи:
Если вершина 1, то ребра 2 (петли), областей 3. ( цвета тоже 3)

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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 16:48 


13/05/14
384
sotu
Munin в сообщении #1395912 писал(а):
sotu в сообщении #1395755 писал(а):
Посмотрел частные случаи:
Если вершина 1, то ребра 2 (петли), областей 3. ( цвета тоже 3)

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

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

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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 17:00 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 17:16 
Заслуженный участник


23/07/08
7870
Харьков
sqribner48 в сообщении #1395962 писал(а):
Две области, заданные двумя петлями, не смежны по ребру (см. Теорему о 4-х красках). Поэтому их можно раскрасить в один цвет.
Есть ещё вариант, когда одна петля вложена в другую, и тогда обе внутренние области смежны. Правда, и тут хватит двух цветов: «самая внутренняя» область красится в тот же цвет, что и внешняя.

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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 17:28 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 18:06 


13/05/14
384
Уважаемый Munin
Munin в сообщении #1395970 писал(а):
sqribner48
В традициях форума - не давать полные решения простых учебных задач :-) а наталкивать спрашивающего на то, чтобы он сам до такого решения добрался.
Простите, погорячился (с). Я думал, что мое сообщение не является полным решением задачи и лишь даст ТС толчок для решения задачи с двумя вершинами.
sotu в сообщении #1395755 писал(а):
Если вершин 2, то придется рисовать кратные ребра, а всего ребер будет 4, тогда имеем 4 области, но цвета всё ещё нужно 3.
Кстати и здесь есть большое поле для раздумий... Пусть думает и решает.
Уважаемый arseniiv
arseniiv в сообщении #1395979 писал(а):
А карта обязательно должна задаваться как стали делать выше, или всё-таки вершины графа соответствуют областям карты, а рёбра указывают смежность областей? ..... И разрешены ли петли вообще?
Вы тысячу раз правы! :!:
Я вообще считаю, что задача ТС-ом сформулирована не корректно. Решение данной задачи зависит от вида графов (учитываются кратные ребра или нет, учитываются петли или нет, или даже как учитываются петли в степенях вершин (в разных книгах это делается по-разному). И ничего не сказано про число вершин графа. Можно ведь выбрать граф с минимальным числом вершин и будет вам счастье минимальное число цветов. И наиболее интересным (и сложным для решения) вариантом будет вариант задачи с простыми графами (т.е. с графами без петель и кратных ребер).
А ТС о них как раз ничего и не пишет. Так что, может быть, ТС для начала должен дать правильную формулировку задачи и решать ее по частям --- сначала для псевдографов, а потом --- для простых графов.

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение28.05.2019, 18:22 
Заслуженный участник
Аватара пользователя


30/01/06
02/09/19
70490
Ну посмотрим. Надо дать ТС слово, а то он вообще пока ничего не написал.

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение29.05.2019, 10:17 


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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение31.05.2019, 09:57 
Аватара пользователя


26/05/12
860
приходит весна?
sotu в сообщении #1395755 писал(а):
...число связных областей, на которые граф делит плоскость (как я понял, это и есть раскрашиваемые участки карты).

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

 Профиль  
                  
 
 Re: Раскраска карты, задаваемой графом
Сообщение31.05.2019, 13:52 


13/05/14
384
B@R5uk
B@R5uk в сообщении #1396861 писал(а):
Почему вершины графа не могут означать страны, а рёбра — границы между этими странами.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group