Question

На острове находятся 7 островов, которые соединены между собой мостами так, как показано на рисунке 28. На какой остров должен доставить катер путешественников, чтобы они могли пройти по каждому мосту и только один раз? С какого острова катер должен снять этих людей? Почему нельзя доставить путешественников на остров А

Answer 1

Мне кажется ответ 2 да точно

Answer 2

Чтобы путешественники могли пройти по каждому мосту и только один раз, им нужно начать с одного острова и закончить на другом. Такой тип задачи называется "задачей о ходе по графу по всем рёбрам и вершинам ровно один раз" или "задачей об обходе Эйлерова цикла". Чтобы определить, с какого острова им нужно начать и на каком закончить, можно воспользоваться правилом Эйлера.

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

Давайте посчитаем степени вершин на островах в вашем графе:

А - 4 моста Б - 3 моста В - 4 моста Г - 4 моста Д - 3 моста Е - 4 моста Ж - 3 моста

Есть только одна вершина с нечетной степенью - остров Б. Поэтому, чтобы пройти по каждому мосту и только один раз, путешественники должны начать с острова Б и закончить на нем же. Нельзя начать с острова А, потому что он имеет четную степень (4 моста), и задачу нельзя решить, начиная и заканчивая на вершине с четной степенью.