2014 dxdy logo

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

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




 
 Раскраска в графах
Сообщение15.05.2011, 12:27 
1) Каждые две из 15 вершин графа соединены ребром. Можно ли все ребра графа покрасить в один из 14 цветов так, чтобы из любой вершины выходили ребра всех 14 цветов?
2) Все страны, расположенные на острове имеют форму треугольников, причем любые две соседние страны имеют общую сторону. Доказать, что карта острова 3-раскрашиваема.
3) На острове расположено несколько стран. Можно ли разбить некоторые из этих стран на меньшие так, чтобы все старые границы сохранились, а получившуюся карту можно было раскрасить в 2 цвета?

 
 
 
 Re: Раскраска в графах
Сообщение15.05.2011, 12:58 
Аватара пользователя
1. Сколько ребер каждого цвета получится?
3. Что можно сказать о 2-раскрашиваемом графе?

 
 
 
 Re: Раскраска в графах
Сообщение22.05.2011, 19:23 
1) Получится 14 ребер.
2) Карта 2-раскрашиваема тогда и только тогда,когда граф эйлеров.

 
 
 
 Re: Раскраска в графах
Сообщение22.05.2011, 19:51 
Аватара пользователя
1) Тут надо начинать издалека. Сколько всего рёбер в графе? Не одного цвета, а вообще всего?

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group