АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Теорема

Граф містить ейлерів цикл тоді і тільки тоді, коли він зв'язний і степені всіх його вершин — парні.

□ Якщо граф ейлерів, то він зв'язний і при обході ейлерова циклу захід і вихід в чергову вершину вносить дві одиниці в її степінь (тому що ребра не повторюються). Оскільки проходяться всі ребра графа, то степені всіх вершин — парні.

Нехай тепер зв'язний граф О має парні степені вершин. Оберемо вершину x₁і перейдемо від неї до вершини х_і за деяким ребром у_k пофарбувавши його подумки у будь-який колір. З вершини х_і рушимо далі в х₂ по непофарбленому ребру, пофарбувавши його після проходження. Просуваючись таким чином по не пофарбованим ребрам, ми повинні повернутися до вихідної вер­шини (зустрічаючи, можливо, інші вершини кілька разів), бо у протилежному випадку вер­шина x_p, з якої ми не може­мо рухатися далі, має непарну степінь. Повернувшись перший раз у вершину x₁, ми пофарбує­мо граф С₀, що є за побудовою ейлеровим циклом.

Матриця суміжності A:

Х – множина вершин.

a_ij – кількість дуг з вершини х_i в вершину x_j.

Дата добавления: 2015-09-27 | Просмотры: 417 | Нарушение авторских прав