задача на графы: построить граф с заданными свойствами

[dev_il]

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

[Macavity]

dev_il писал(а):

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

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

Обозначим города от 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 другими, то желание короля неосуществимо

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

[нг]

dev_il,
Поменяйте, пожалуйста, заголовок темы (заголовок первого сообщения) на информативный.

[dev_il]

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

[dev_il]

неужели никто не может решить часть б) ??

[maxal]

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 вершин:

С подробностями можно ознакомится в этом обзоре.