2014 dxdy logo

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

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




 
 задача на графы: построить граф с заданными свойствами
Сообщение08.07.2007, 18:55 
Помогите решить задачу на графы:
В королевстве 16 городов. Король хочет построить систему авиалиний в своём королевстве так, чтобы выполнялись следующие условия:
1) каждый город должен быть соединён не более чем с 5 другими
2) из каждого города можно доьраться в каждый сделав не более 1 пересадки (минуя 1 промежуточный город или сразу из города в город)
а) Сможет ли король осуществить своё желание?
б) докажите что если каждый город соединён авиалиниями не более чем с 4 другими, то желание короля неосуществимо

 
 
 
 Re: помогите...
Сообщение09.07.2007, 12:44 
dev_il писал(а):
Помогите решить задачу на графы:
В королевстве 16 городов. Король хочет построить систему авиалиний в своём королевстве так, чтобы выполнялись следующие условия:
1) каждый город должен быть соединён не более чем с 5 другими
2) из каждого города можно доьраться в каждый сделав не более 1 пересадки (минуя 1 промежуточный город или сразу из города в город)
а) Сможет ли король осуществить своё желание?


Однозначно, сможет, он ведь король. :D

Обозначим города от 0 до 15. А теперь будем их рассматривать в двоичной кодировке.
Вот они:
0000
0001
...
...
...
1110
1111

Чтобы "упростить" способ связывания городов, введем понятие расстояние между городами.
"Расстоянием" между двумя городами будем считать количество различающихся разрядов в их названии.

Например Растояние(0111,1001)=3, так как совпадают только самые младшие разряды.
Каждый город соединим с четырьмя "ближайшими" к нему городами (расстояние=1) и самым дальним расстояние=4 (город с инвертированным номером).

Например город 0110 будет соединен с городами 1110, 0010, 0100, 0111 и с самым дальним городом - 1001. И так - каждый город (выбранное отношение близости городов - симметрично).
Что получится.

Наугад выбранный город X соединен прямыми линиями с пятью другими городами (4+1). К городам удаленным от X на расстояние 2 можно долететь через один из четырех городов "уменьшающих" расстояние на 1 (аккурат за одну пересадку) и таких городов 6.
К четырем городам удаленным на расстояние 3 можно пролететь через "инвертированный" город. Перелет к инвертированному городу уменьшит расстояние с трех до одного, и затем в целевой город за 1 перелет.
Итого 1+5+6+4=16 и это для любого из городов.

dev_il писал(а):
б) докажите что если каждый город соединён авиалиниями не более чем с 4 другими, то желание короля неосуществимо


Вот! Не всё могут короли.
Здесь надо ипользовать принцип клеток Дирихле...

 
 
 
 
Сообщение09.07.2007, 17:36 
Аватара пользователя
 !  dev_il,
Поменяйте, пожалуйста, заголовок темы (заголовок первого сообщения) на информативный.

 
 
 
 
Сообщение10.07.2007, 17:32 
:shock: ... тока вот я если честно даже не представляю себе, как это можно доказать с помощью принципа Дирихле... вообще первая часть легче второй, поэтому я лучше бы хотел увидеть решение второй части, если можно :D

 
 
 
 ...
Сообщение01.08.2007, 14:55 
неужели никто не может решить часть б) ?? :(

 
 
 
 Re: задача на графы: построить граф с заданными свойствами
Сообщение25.12.2009, 17:22 
Аватара пользователя
dev_il в сообщении #72177 писал(а):
В королевстве 16 городов. Король хочет построить систему авиалиний в своём королевстве так, чтобы выполнялись следующие условия:
1) каждый город должен быть соединён не более чем с 5 другими
2) из каждого города можно доьраться в каждый сделав не более 1 пересадки (минуя 1 промежуточный город или сразу из города в город)
а) Сможет ли король осуществить своё желание?
б) докажите что если каждый город соединён авиалиниями не более чем с 4 другими, то желание короля неосуществимо

Решение пункта б):
Нетрудно видеть, что если искомый граф существует, то степень каждой вершины должна быть в точности 4 (иначе нарушится условие 2).
Поэтому искомый граф, если существует, является 4-регулярным, а условие 2 означает, что диаметр этого графа равен 2.
Однако, согласно теореме Erdos-Fajtlowicz-Hoffman, $d$-регулярного графа с $d^2$ вершинами и диаметром $2$ при $d>2$ не существует.

P. S. Максимальный 4-регулярный граф диаметра 2 имеет 15 вершин:
Изображение
С подробностями можно ознакомится в этом обзоре.

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


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