ешанийий граф (рис.1.4) - це граф, який містить як орієнтовані, так і неоріентіруемие ребра. Кожній з перерахованих видів графа може містити одне або кілька ребер, в яких обидва кінці сходяться в одній вершині, такі ребра називаються петлями (рис.1.5).
Гамільтонових головоломка ланцюг число
Рис. 1.5 Змішаність граф з петлями
Рис. 1.6 Загальний випадок графа
У загальному випадку безліч ребер може складатися з трьох непересічних підмножин: підмножини ланок, підмножини дуг і підмножини петель (рис.1.6).
Ріс.1.7 Сутність геометричної конфігурації графа
Наочно граф можна представляти як геометричну конфігурацію (див. ріс.1.7), яка складається з точок (вершин графа 1,2,3,4,5,6) і ребер (ліній або відрізків № 1 (1-3), № 2 (3-4), № 3 (4-5), № 4 (3-5), № 5 (2-3), № 6 (2-5), № 7 (5-6), № 8 (6 - 2), № 9 (2-1), які з'єднують деякі точки (вершини) за обраним алгоритмом обходу вершин графа) [5].
Дамо формальне математичне визначення графа. Нехай -Деякі кінцеве безліч (безліч вершин), - безліч всіх невпорядкованих пар елементів (ребер або дуг графа) з безлічі вершин
,
Визначення 1.1.
Граф - пара множин. Безліч -це множина вершин, безліч -це безліч ребер. Якщо, то ми говоримо, що ребро з'єднує вершину з вершиною, інша термінологія - ребро і вершини і - інцідентни.
Визначення 1.2.
Граф називається повним, якщо, тобто граф складається з максимально можливої ??кількості ребер, які попарно з'єднують точки його вершин (див. рис.1.8). Якщо безліч містить вершин, то, очевидно, число ребер повного графа дорівнює.
Рис.1.8 Приклади повних графів
Визначення 1.3.
Граф називається порожнім, якщо граф не має ребра (см.ріс.1.9).
Рис.1.9 Приклад побудови 3-х вершинного графа з різною кількістю ребер
Природно виникає питання: скільки існує різних графів з множиною вершин, якщо. Для цього доведемо наступну теорему.
Теорема 1.1. Число всіх різних графів з вершинами дорівнює:
Доказ. Дійсно, граф повністю визначений, якщо вказано безліч, є підмножиною. Безліч містить елементів, тому число всіх її підмножин одно.
Визначення 1.4.
Вершини та графа інцідентни, якщо.
Визначення 1.5.
Ступенем вершини графа називається число вершин, які інцідентние вершині (число відрізків які виходять з вершини) - см.ріс.1.10.
ріс.1.10 Визначення ступенів вершин графа за кількістю ребер, що виходять з вершин
Визначення 1.6.
Якщо, то вершина називається кінцевою вершиною графа. Якщо, то вершини називається ізольованою (див. Рис. 1.11)
ріс.1.11 Визначення кінцевих та ізольованих вершин графа
. 2 Лемма про рукостискання
Формулювання цієї леми проста -" кількість рук, які беруть участь у рукостисканням N-пар людей, дорівнює 2 * N. Лему можна представити у формі графа, де N вершин з'єднані ребрами d (хі, xj) рукостисканням i і j - вершин (див. Рис.1.12), виконавши наступний доказ.
рис.1.12. " Лемма про рукостискання 5 осіб
Нехай граф з множиною верщін. Тоді
(1.1)
Доказ. Зауважимо, що кожне ребро графа в сумі враховується двічі (див. Рис.1.12), і тому справедливо рівність (1.1). Зауважимо, що сума ступенів усіх вершин у графі (або мультіграф без петель) повинно бути парним. Це випливає з того, що якщо взяти вершини, взагалі не пов'язані один з одним, то сума ступенів цих вершин дорівнює нулю. Додаючи будь ребро, пов'язує дві вершини, збільшуємо суму всіх ступенів на 2 одиниці. Таким чином, сума всіх ступенів вершин парна. З рівності 1.1 випливає таке твердження: число вершин непарного ступеня в графі обов'язково є парним числом. Теорема доведена.
Визначення 1.7.
Матриця суміжності - це симетрична матриця, елементи якої дорівнюють нулю або одиниці (діагональні елементи рівні нулю) і така, що сума чисел в будь-якому рядку і будь-якому стовпці дорівнює ступеня відповідної вершини. Так, для графа, наведеного на рис.1.13, матриця суміжності побудується у вигляді:
рис.1.13. До побудови матриці суміжності 3-х вершинного графа
Визначення 1.8.
Послідовність ребер, в якій сусідні ребра інцідентни однієї і тієї ж вершині називаються ланцюгом. Ланцюг називається простою, якщо всі вершини, що належать їй (крім, можливо, першої і останньої), різні; число в цьому випадку називають довжиною ланцюга.
Якщо, то ланцюг називається циклом. Цикл, в якому всі вершини різні, називається простим. Приклад...
