Комбинаторные алгоритмы

66построим ориентированный мультиграф, вершинами кото-рого будут являться буквы от a до z (мультиграфом называ-ется граф, в котором пары вершин могут быть соединены более чем одним ребром). каждому слову из заданного списка сопо-ставим ребро, соединяющее первую и последнюю буквы этого слова. в полученном мультиграфе требуется найти эйлеров путь (т. е. путь, проходящий по каждому ребру ровно один раз). Это легко делается поиском в глубину.однако кажется более естественным построить другую модель этой задачи, в которой вершинами являются слова, а ори-ентированные ребра ведут из одной вершины в другую, если последняя буква первого слова совпадает с начальной буквой вто-рого. к какой задаче на графе сведется исходная?требуемая покраска всегда возможна. приведем алгоритм такой покраски.строим неориентированный граф: его вершины — залы, а ребра — двери. задача сводится к следующему: ориентировать ребра так, чтобы степени исхода и захода каждой вершины разли-чались не более чем на единицу. алгоритм — поиск в глубину.1. полагаем Статус каждой вершины равным 0 /*Статус — разность между степенью исхода и захода вер-шины*/.