2014 dxdy logo

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

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




 
 Никита составил схему автобусного сообщения между деревнями
Сообщение23.05.2024, 14:14 
Никита составил схему автобусного сообщения между деревнями.
Илья составил таблицу автобусных сообщений между населенными пунктами.
Илья пронумеровал деревни, а наличие автобусного сообщения обозначил звездочкой.

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

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

Изображение

Изображение

Если пристально смотреть на таблицу, то видно, что не хватает Вершины с 4 путями для Пункта Карелы.

Добавляем вершину, проверяя, чтобы при этом не образовалось две вершины с 4 путями.
Но возможных вариантов слишком много. Как их отсеять?

 
 
 
 Re: Никита составил схему автобусного сообщения между деревнями
Сообщение23.05.2024, 14:51 
Аватара пользователя
Ясно, что маршруты Карелы—Толстовка и Карелы—Боловитино не могли быть пропущены в таблице.
Зацепка: если убрать ребро Карелы—Антоновка, возникнет уникальная особенность — две смежные вершины степени 2 (Боловитино и Антоновка). Их легко найти и в таблице. В графе, полученном из исходного удалением ребра Карелы—Ухтынск, вершин с таким свойством нет.

 
 
 
 Re: Никита составил схему автобусного сообщения между деревнями
Сообщение23.05.2024, 16:12 
Аватара пользователя
svv в сообщении #1640074 писал(а):
Боловитино
Извиняюсь, Болотовино.

 
 
 
 Re: Никита составил схему автобусного сообщения между деревнями
Сообщение23.05.2024, 22:13 
gevaraweb в сообщении #1640107 писал(а):
Зацепка: если убрать ребро Карелы—Антоновка, возникнет уникальная особенность — две смежные вершины степени 2

Хм, действительно ).
Посчитал степени вершин в таблице, степень 2 имеют вершины №1, №4, №5.
Смежными являются №1 и №5.
Итак, Болотовино и Антоновка - это (№1, №5) или (№5, №1). Дальше опять тупик :mrgreen:
Новое ребро должно добавить вершину степени 4.
Пока вершины степени 3 это №2, №3, №6, №7.
Соединяем одну из (№1, №5) с одной из (№2, №3, №6, №7). Опять много вариантов.

А, Толстовка, получается, имеет номер №4.
А, аналогично: если убрать ребро Карелы—Антоновка, возникнет еще уникальная особенность —
ровно одна из вершины степени 3 имеет две смежные вершины степени 2.
Это вершина №6. Итак, Карелы имеет номер №6.

Далее уже раскручивается...
Толстовка смежна с Карелы и Алексеевка.
При этом №4 смежна с №6 и №2.

Итак, Алексеевка имеет номер №2.

Далее Ухтынск и Клименки - им остается пара №3 и №7, или наоборот.
Карелы смежна с Ухтынск, а в таблице с №7, поэтому Ухтынск имеет №7.
Соответственно, Клименки имеет №3.

Ну теперь и Антоновка - это №5. Болотовино это №1.
svv, благодарю.
Тяжелая задача (имеется в виду, соседний вариант гораздо очевиднее).

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


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