Путем в графе от одной вершины к другой называется

Чем отличается маршрут AEH от маршрута AEFCEH? Тем, что во втором маршруте на «перекрестке» в точке E мы побывали дважды. Этот маршрут длиннее, чем AEH. Маршрут AEH можно получить из маршрута AEFCEH «вычеркнув» из последнего маршрут FCE. Маршрут AEH является путем в графе, а маршрут AEFCEH путем не является. Существуют различные маршруты, по которым можно добраться, например, из вершины A в вершину H. Маршруты CFEC, ADGHECBA, ADFCEA — циклы: CFEC и др. — элементарные циклы.

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

Решить эту задачу удалось в 1736 г. Леонарду Эйлеру. В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке), Л. Эйлер установил, помимо уже рассмотренных нами, закономерности (доказательство этих закономерностей предлагаем вам).

Решение: Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа, представленного на рисунке. Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то, согласно закономерности 7. такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигcбергским мостам, соблюдая заданные условия, нельзя.

Путь в графе.Цикл.

На рисунке с помощью графа изображена схема дорог между населенными пунктами. Например, из пункта A (вершина графа) в пункт H можно добраться различными маршрутами: ADGH, AEH, AEFCEH, ABCEH.