аючи олівця від паперу, називається ейлеровим графом (ріс.1.3.8). Такими графи названі на честь вченого Леонарда Ейлера.
Закономірність 1. (випливає з розглянутої нами теореми). Неможливо накреслити граф з непарним числом непарних вершин.
Закономірність 2. Якщо всі вершини графа парні, то можна не відриваючи олівець від паперу («одним розчерком»), проводячи по кожному ребру тільки один раз, накреслити цей граф. Рух можна почати з будь-якої вершини і закінчити його в тій же вершині.
Закономірність 3. Граф, що має всього дві непарні вершини, можна накреслити, не відриваючи олівець від паперу, при цьому рух потрібно почати з однією з цих непарних вершин і закінчити у другій з них.
Закономірність 4. Граф, що має більш двох непарних вершин, неможливо накреслити «одним розчерком».
Фігура (граф), яку можна накреслити, не відриваючи олівець від паперу, називається унікурсальной.
Граф називається зв'язковим, якщо будь-які дві його вершини можуть бути з'єднані шляхом, т. е. послідовністю ребер, кожне наступне з яких починається в кінці попереднього. Граф називається незв'язним, якщо ця умова не виконується.
ріс.1.3.10 ріс.1.3.11
На малюнку 1.3.10, очевидно, зображений незв'язних граф. Якщо, наприклад, на малюнку між вершинами Д і Е провести ребро, то граф стане зв'язковим (ріс.1.3.11) .Таке ребро в теорії графів (після видалення якого граф з зв'язкового перетворюється на незв'язних) називається мостом.
Прикладами мостів на малюнку 1.3.10 могли б служити ребра ДЕ, A3, ВЖ та ін., кожне з яких єднало б вершини «ізольованих» частин графа (ріс.1.3.11).
Незв'язний граф складається з декількох «шматків». Ці «шматки» називаються компонентами зв'язності графа. Кожна компонента зв'язності є, звичайно, зв'язковим графом. Відзначимо, що зв'язний граф має одну компоненту зв'язності.
Теорема. Граф є ейлеровим тоді і тільки тоді, коли він пов'язаний і має не більше двох непарних вершин.
Доказ: Малюючи граф кожну вершину, за винятком початкової і кінцевої, ми увійдемо стільки ж разів, скільки вийдемо з неї. Тому ступеня усіх вершин повинні бути парними, крім двох, а значить, Ейлером граф має не більше двох непарних вершин.
в) Дерева.
Деревом називається будь зв'язний граф, який не має циклів.
Домовилися вважати «деревом» і всякий граф, що складається з однієї (ізольованою) вершини. Циклом називається шлях, в якому збігаються початок з кінцем. Якщо всі вершини циклу різні, то такий цикл називається елементарним (або простим) циклом. Якщо ж цикл включає в себе всі ребра графа по одному разу, то такий цикл називається ейлеровимі лінією (ріс.1.3.12 (а)). У графі на ріс.1.3.13 (б) два цикли: 1-2-3-4-1 і 5-6-7-5.
Шляхом в графі від однієї вершини до іншої називається така послідовність ребер, по якій можна прокласти маршрут між цими вершинами. При цьому ніяке ребро маршруту не повинно зустрічатися більше одного разу. Вершина, від якої прокладений маршрут, рівно одне називається початком шляху, вершина в кінці маршруту - кінець шляху.
Висячої вершиною називається вершина, з якої виходить ребро (ріс.1.3.14).
ріс.1.3.12а ріс.1.3.13б
Властивість 1. Для кожної пари вершин дерева існує єдиний шлях, їх з'єднує.
Цією властивістю користуються при знаходженні всіх предків у генеалогічному дереві, наприклад, по чоловічій лінії, будь-якої людини, чий родовід представлена ??у вигляді генеалогічного дерева, яке є «деревом» і в сенсі теорії графів.
Властивість 2. Усяке ребро в дереві є мостом.
Дійсно, після видалення будь-якого ребра дерева, воно «розпадається» на два дерева.
ріс.1.3.14 (кружком обведені висячі вершини)
Теорема. Граф, у якому дві будь вершини з'єднані рівно одним простим шляхом, є деревом.
Доказ: Очевидно, що даний граф зв'язний. Припустимо, що в ньому є цикл. Тоді будь-які дві вершини цього циклу з'єднане принаймні двома простими шляхами. Отримали протиріччя, а значить, наше припущення невірно.
Дерево - це граф, в якому дві будь-які вершини з'єднані рівно одним простим шляхом.
Теорема. У дереві число вершин на одну більше числа ребер.
Доказ: З умови теореми граф - дерево. У нього є висяча вершина. Видалимо його і виходить з неї ребро. Залишившись граф також дерево. У нього є висяча вершина, яку також видалимо. Виконавши цю операцію n - 1 раз, отримаємо граф, що складається з однієї вершини. Т.к. віддалялося по одному ребру, то спочатку їх було n - 1.
г) Плоскі графи.
Граф, який можна намалювати так, щоб його р...
