ни V Вў вершин графа L ( G ) рівнопотужна множіні ребер E графа G , тоб існує бієкція j : V Вў В® E . Вершини v , w ГЋ V Вў з єднуються ребром у графі L < span align = "justify"> ( G ), тоді й позбав тоді, коли відповідні їм ребра j ( v ) i j ( w ) інцідентні одній и тій же вершіні в графі G .
Теорема 2.2.5 Если граф G має ейлерів цикл, то граф L ( G ) має як ейлерів, так и гамільтонів цикли.
Теорема 2.2.6 Если граф G має гамільтонів цикл, то граф L ( G ) такоже має гамільтонів цикл.
.3 Завдання побудова гамільтоновіх ціклів у графі
Термін В«гамільтонівВ» походити від имени відомого ірландського математика У. Гамільтона (W. Hamilton), Який 1857 р. запропонував гру В«Навколосвітня подорожВ». Кожній Із двадцяти вершин додекаедра (правильного дванадцятігранніка, Грані Якого - п'ятікутнікі) приписана назва одного з великих міст світу. Потрібно, починаючі з довільного міста, відвідаті Решті 19 міст точно один раз и вернуться у Початкове місто. Перехід дозволений по ребрах додекаедра.
В
Рис. 2.3.1
Приклад 2.1.1. Ту
