Page 68 - 4496

спосіб. Обходимо послідовно ребра вилученого контуру.
Якщо ми прийшли у вершину, загальну для контуру і якогось
компонента зв’язності, то обходимо за Ейлеровим циклом цей
компонент, повертаємося при цьому у вершину контуру і
йдемо по цьому контурі далі. Тим самим всі ребра будуть
пройдені й кожне тільки один раз (все це схематично
зображено на рис. 4: спочатку починаємо обходити контур
АВСDEА. Пройшовши ребро АВ, проходимо “верхній” граф,
потім повертаємося в т В. І далі йдемо по ребру АС, обходимо
“правий” граф і так далі). Твердження Б доведене.
В) Нехай граф напівейлеровий. Це значить, що він має
Ейлеровий шлях, що починається в одній вершині й
закінчується в іншій. Видно, що обидві ці вершини повинні
мати непарний ступінь, а ступінь інших парна

В

А С

D

Рисунок 3. 4 – Ейлерів цикл

Г) Обернено. Нехай у зв'язаному графі вершини к і р
мають непарний ступінь, а інші вершини – парну. Тоді
можливі 2 випадки: ці вершини зв'язані ребром або не зв'язані.
65