Guest
Новичок
|
    
Доброго времени суток!
Задача:
Предположим, что G связный граф и в нем ровно две вершины a и b имеют нечетную степень. Покажите, что существуют путь между a и b такой, что проходит через каждое ребро графа ровно один раз (так же, как и Эйлеров путь, но не является циклом).
Знаю, что решение простое, но не могу собрать в кучу. Помогите!
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 31 окт. 2008 4:06 | IP
|
|
Trushkov
Долгожитель
|
  
Про эйлеров цикл решать умеете?
Если да, то соедините вершины a и b ребром и пройдите эйлеровым циклом, чтобы новое ребро было первым или последним.
|
Всего сообщений: 273 | Присоединился: январь 2006 | Отправлено: 31 окт. 2008 12:09 | IP
|
|
|
Форум
Задача по теории графов
