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

Рис.1.15. Приклад 1 графу для оцінки зв’язності

В ньому .Викресливши два ребра, отримаємо граф . Викреслити далі яке-небудь ребро, не порушуючи зв язності, вже не можна (див.рис.1.16).

Рис. 1.16. Приклад 1 графу для оцінки зв’язності

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

Для доведення верхньої оцінки в нерівності (1.3) замінимо кожну компо-ненту повним графом. Нехай та два повних, отриманих з компонент зв’ язності та , а та число ребер в цих компонентах .Замінемо на повний граф, додавши одну вершину, а замінемо на повний граф, віднявши одну вершину.Тоді загальне число вершин не змінеться, а число ребер збільшиться на додатню величину

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

З нерівності (1.3) випливає такий наслідок.

Наслідок. Будь-який граф з і більше ніж ребрами є зв’язним.

Справді, якщо граф з вершинами має дві компоненти зв’язності, то максимальне число ребер не перевищує .

Найти компоненти сильної зв’язності графу на рис.1.17.

Відповіді

Рис.1.17. 7-ми вершинний граф для обчислення компонентів зв’язності [10]

1.4 Ор іє нтован і графи , графи з петлями, графи з паралельними дугами

Дамо означення орієнтованих графів, графів з петлями та графів з пара-лельними дугами.

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

Залежно від типу ребер відрізняють кілька типів графів. Петля — це реб-ро, щоз’єднує вершину саму з собою. У мультиграфі петлі не допускаються, але паривершин можуть з’єднуватися кількома ребрами, які називаються крат-ними, абопаралельними. У псевдографі допускаються петлі й кратні ребра. В звичайномуграфі немає ні петель, ні кратних ребер.

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

Рис.1.18. Види орієнтованих графів

Означення 1.12.

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

Дуга називається дугою з в (див.рис.1.19).

Рис. 1.19. Орієнтований 3-х вершинний граф (,