Page 66 - 4496

Рисунок 3. 2 - Графи

Теорема (Ейлера). Для того щоб даний зв'язний граф
(не орграф, але, можливо, мультиграф без петель) був
Ейлеровим, необхідно й достатньо, щоб степені всіх вершин
були парними. Даний зв'язний граф буде напівейлеровим тоді
й тільки тоді, коли степені двох вершин будуть непарними, а
степені інших вершин – парними.
Лема. Кількість вершин у графі (або мультграфі без
петель), що мають непарний степінь,парна.
Доказ леми. Сума степеней всіх вершин у графі (або
мультграфі без петель) повинна бути парною. Це випливає з
того, що якщо взяти вершини, взагалі не пов'язані одна з
одною, то сума степеней цих вершин дорівнює нулю.
Додаючи будь-яке ребро, що зв'язує дві вершини, збільшуємо
суму всіх степенів на 2 одиниці. Таким чином, сума всіх
степеней вершин парна. Видаляючи із цієї суми степенів
парних вершин, одержимо, що сума степенів непарних
вершин, повинна бути парною. Це значить, що саме число
таких вершин повинне бути парним. Лема доведена.
А) Нехай граф є Ейлеровим. Тоді в ньому є Ейлеровий
цикл, що повинен прийти у вершину по одному ребру й
покинути його по іншому, тому що кожне ребро повинне
використатися тільки один раз (тобто кожен “захід” у
вершину й “вихід” з її дає 2 степеня вершини). Таким чином,
сума степенів всіх вершин повинна бути парною (і дорівнює
подвоєному числу “заходів” у цю вершину при обході
Ейлерова цикла).
Б) Нехай у даному зв'язному графі (або мультграфі без
петель) ступінь будь-якої вершини парний (тобто ступінь
більше або дорівнює 2, тому що нульовий ступінь приводить
до незв'язного графа). Доведемо, що в ньому є Ейлеровий
63