Нескінченні графи
Нескінченим (неорієнтованим) графом називається пара G = (V, Е) де V - нескінчена множина вершин і E - нескінчена множина ребер. Якщо обидві множини V і E злічені, то граф називається зліченим.
Слід зазначити, що ці визначення не стосуються випадку, коли V - скінчена множина, a E - нескінчена множина, або коли E - скінчена множина, а V - нескінчена множина. Граф G слід вважати скінченим, якщо він має в першому випадку скінчене число вершин і нескінчене число ребер (або петель), а в другому випадку - скінчене число ребер і нескінчене число ізольованих вершин.Означення таких понять, як суміжні вершини, інцидентні ребра, ізоморфні графи, підграф графа, зв’язний граф, компонента зв’язності повністю переносяться на нескінчені графи.
Степенем вершин у нескінченого графа називається потужність множини ребер, інцидентних вершин V. Отже степінь вершин в нескінченому графі може бути як скінченим, так і нескінченим.
Нескінчений граф називається локально скінченим, якщо степінь кожної його вершини скінчений. Прикладом локально скінченого графа може бути квадратна решітка (рис. 49), складена з цілих чисел.
Нескінчений граф називається локально зліченим, якщо кожна вершина цього графа має злічений степінь.
Для нескінчених графів дійсні наступні твердження:
• будь який зв’язний локально злічений нескінчений граф є зліченим;
• всякий зв’язний локально скінчений нескінченний граф є зліченим.
На скінчені графи переноситься і поняття маршруту, причому воно може мати такі різновиди:
• скінчений маршрут у нескінченому графі G визначається так, як у випадку скінчених графів;
• нескінченим в одну сторону маршрутом у графі G, який починається вершиною Vo, називається нескінчена послідовність
• нескінченим в обидві сторони маршрутом у графі G називається нескінчена послідовність ребер
Нескінчені в одну і обидві сторони ланцюги і прості ланцюги визначаються так, як і поняття довжини ланцюга і відстані між вершинами. Умовні існування нескінчених ланцюгів у графах дає теорема, яка в теорії графів відома під назвою леми Кьоніга.
Лема Кьоніга. Нехай G - зв’язний локально скінчений нескінчений граф. Тоді для всякої його вершини v існує нескінчений в один бік простий ланцюг, який починається у вершині v.
Доведення. Якщо u довільна вершина графа G, відмінна від вершини V, то існує деякий простий ланцюг, який з’єднує вершини V І U. Звідси випливає, що в G повинно бути нескінченно багато простих ланцюгів з початком у вершині v. Оскільки степінь вершини v скінчений, то нескінчена множина таких простих шляхів повинна починатися з одного і того ж ребра. Якщо таким ребром є ребро (u, Vi), ТО повторивши ЦЮ процедуру ДЛЯ вершини Vi, одержимо нову вершину V2 і відповідне їй ребро (Vi, v2). Продовжуючи цей процес далі, одержимо нескінчений В одну сторону простий ланцюг V, Vi, V2,...
Важливе значення леми Кьоніга полягає в тому, що вона дає можливість одержувати результати про нескінчені графи з відповідних результатів про скінчені графи.
Зв’язний злічений граф G називається ейлеровим, якщо в ньому існує нескінчений в обидві боки ланцюг, який містить кожне ребро графа G. Такий ланцюг називається двостороннім ейлеровим ланцюгом.
Злічений граф називається напівейлеровим, якщо в ньому існує нескінченний в один, або в обидва боки ланцюг, який містить в собі кожне ребро графа G.
2.6.6.