В компьютерной игре главный герой перемещается по государству , состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого.…
В компьютерной игре главный герой перемещается по государству , состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого. Герой обошел все острова в поисках карты , пройдя по каждому мосту ровно один раз. Но на острове Древнем он побывал целых 17 раз. Сколько мостов ведет с острого Древнего, если герой не с него начал и не на нем закончил свой поход
Для решения этой задачи, нам необходимо воспользоваться понятием графов.
Представим каждый остров как вершину графа, а мосты как рёбра графа. Мы знаем, что герой прошёл каждый мост один раз, а на острове Древнем он побывал 17 раз, следовательно, 17 рёбер графа инцидентны (инцидентны = инцидентны вершине) этому острову.
Теперь вспомним, что сумма степеней всех вершин графа, то есть сумма количества инцидентных рёбер каждой вершине, равна удвоенному количеству рёбер графа. Рассматривая только рёбра, которые инцидентны вершине Древний, мы видим, что данная вершина смежна с 17 мостами.
Важно отметить, что каждый мост соединяет два острова, значит, когда герой заходит на остров по мосту, он должен покинуть его по другому мосту. Следовательно, каждая вершина, за исключением начальной и конечной, имеет чётную степень.
Теперь мы можем решить задачу:
- Поскольку вершина Древнего имеет нечётную степень (17), это означает, что она либо начальная, либо конечная вершина обхода героя (по условию нет).
- Если вершина Древнего была бы начальной или конечной вершиной, каждая из остальных вершин графа, не являющихся Древнем, имела бы чётную степень.
- Таким образом, чтобы вершина Древнего имела нечётную степень, она не может быть начальной или конечной вершиной обхода.
Следовательно, на остров Древний ведет чётное количество мостов.
