Теорема
Граф містить ейлерів цикл тоді і тільки тоді, коли він зв'язний і степені всіх його вершин — парні.
□ Якщо граф ейлерів, то він зв'язний і при обході ейлерова циклу захід і вихід в чергову вершину вносить дві одиниці в її степінь (тому що ребра не повторюються). Оскільки проходяться всі ребра графа, то степені всіх вершин — парні.
Нехай тепер зв'язний граф О має парні степені вершин. Оберемо вершину x1і перейдемо від неї до вершини хі за деяким ребром уk пофарбувавши його подумки у будь-який колір. З вершини хі рушимо далі в х2 по непофарбленому ребру, пофарбувавши його після проходження. Просуваючись таким чином по не пофарбованим ребрам, ми повинні повернутися до вихідної вершини (зустрічаючи, можливо, інші вершини кілька разів), бо у протилежному випадку вершина xp, з якої ми не можемо рухатися далі, має непарну степінь. Повернувшись перший раз у вершину x1, ми пофарбуємо граф С0, що є за побудовою ейлеровим циклом.
Матриця суміжності A:
Х – множина вершин.
aij – кількість дуг з вершини хi в вершину xj.
Дата добавления: 2015-09-27 | Просмотры: 457 | Нарушение авторских прав
|