Консультация № 186351
11.06.2012, 15:29
94.84 руб.
0 4 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Построить Эйлеров путь в графе, заданном своей матрицей смежности

Обсуждение

давно
Посетитель
7438
7205
11.06.2012, 15:47
общий
Что Вы хотите получить?
1) какой-нибудь один Эйфелев путь;
2) алгоритм их нахожденияж
3) может, программу, которая их ищет;
4) что-то другое.
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Профессор
230118
3054
11.06.2012, 23:01
общий
это ответ
Здравствуйте, Андрей!

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

Эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Начиная со стартовой вершины v строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в стеке S. Когда наступает такой момент, что для текущей вершины w все инцидентные ей ребра уже пройдены, записываем вершины из S в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.
Начнем с вершины 1
1-2-3-5-1-4-2-5-4-6-5-7-6-1
давно
Профессор
230118
3054
12.06.2012, 01:17
общий
Адресаты:
Эйфелева бывает только башня. Ну он еще мосты строил.
давно
Посетитель
7438
7205
12.06.2012, 11:13
общий
Адресаты:
А, ну да Конечно же, Эйлеров путь. На автомате получилось...
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа