Курсовая работа: Основи теорії графів. Властивості ойлерових та гамільтонових графів

Рис.1.2. Неорієнтований граф (вершини та ребра)

Орієнтований граф (орграф) — це граф, для кожного ребра якого істотний порядок двох його кінцевих вершин. Орграф представлений на рис.1.3, ребра орграфа іноді називають дугами.

Рис. 1.3. Орієнтований граф

Рис. 1.4. Змішаний граф

Змішаний граф (рис.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].

Дамо формальне математичне означення графазгідно [11].

Нехай –деяка скінченна множина (множина вершин), - множина всіх невпорядкованих пар елементів (ребер або дуг графу) з множини вершин, .

Означення 1.1.

Граф – пара множин. Множина –це множина вер-шин, множина –це множина ребер. Якщо , то ми говоримо, що ребро сполучає вершину з вершиною ; інша термінологія – ребро і вершини та - інцидентні.

Означення 1.2.

Граф називається повним , якщо , тобто граф складається з максимально можливої кількості ребер, які попарно з’єднують точки його вершин (див.рис.1.8). Якщо множина містить вершин, то, очевидно , число ребер повного графа дорівнює .

Рис.1.8. Приклади повних графів

Означення 1.3.

Граф називається порожнім, якщо , тобто граф не має ребер (див.рис.1.9).

Рис.1.9. Приклад побудови 3-х вершинного графу з різною кількістю ребер (заповнення графу від «порожнього» до «повного»)

Природно виникає питання: скільки є різних графів з множиною вершин , якщо . Для цього доведемо наступну теорему.