Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







ЗВ’ЯЗНІСТЬ ГРАФІВ. ЕЙЛЕРОВІ ТА ГАМІЛЬТОНОВІ ГРАФИ





 

 

4.1 Мета заняття

 

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

 

4.2 Методичні вказівки з організації самостійної роботи студентів

 

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–8, 10–12] з таких питань: поняття зв’язності графів, властивості зв’язних графів; метричні характеристики зв’язних графів; ейлерові графи; теорема Ейлера про наявність ейлерова циклу; алгоритм знаходження ейлерова циклу (теорема Флері); гамільтонові графи; ознаки існування гамільтонових циклів, шляхів і контурів.

Підготовка і виконання практичного заняття проводиться за два етапи.

Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень теми «Зв’язність графів. Ейлерові та гамільтонові графи»: маршрут; довжина маршруту; замкнений маршрут; коло; просте коло; цикл; дуга; орієнтований маршрут; шлях; контур; зв’язний граф; незв’язний граф; сильно зв’язний граф; підграф; компонента зв’язності; n-зв’язний граф; степінь зв’язності графа; число вершинної зв’язності; число реберної зв’язності; точка зчленування графа; міст; відстань між вершинами графа; діаметр графа; ексцентриситет вершини; радіус графа; центральна вершина графа; центр графа; грань (комірка) геометричного графа; необмежена грань (зовнішня грань); внутрішня грань; границя грані; ейлерове коло; ейлерів цикл; ейлерів граф; власний ейлерів шлях; алгоритм знаходження ейлерова циклу (алгоритм Флері); гамільтонів шлях (гамільтонів ланцюг); гамільтонів граф.



Під час виконання першого етапу практичного заняття студент має запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, поданих у підрозділі 4.3, на основі запропонованих типових прикладів (див. підрозділ 4.4).

 

4.3 Контрольні запитання і завдання

 

4.3.1 Контрольні запитання

1. Дайте визначення зв’язному і незв’язному графам.

2. Що є компонентою зв’язності графа? Наведіть приклади компонент зв’язності.

3. Що називається степенем зв’язності графа?

4. Перелічіть властивості зв’язних графів.

5. Наведіть приклади метричних характеристик зв’язних графів.

6. Якщо граф зв’язний і – число його вершин, то яка нижня оцінка для числа його ребер?

7. Дайте визначення ейлеровому циклу (ейлеровому колу, замкненому ейлеровому колу).

8. Який граф називається ейлеровим?

9. Для розв’язання яких практичних задач використовується теорема Ейлера?

10. Поясніть використання алгоритму знаходження ейлерева циклу (теорема Флері).

11. Дайте визначення гамільтонова шляху (гамільтонова ланцюга), гамільтонова циклу.

12. Який граф називається гамільтоновим?

13. Дайте характеристику алгоритму Робертса-Флореса. Для яких цілей він використовується?

14. Назвіть основні ознаки існування гамільтонових циклів, шляхів і контурів.

15. Охарактеризуйте теорему (умову Дірака) для визначення гамільтонова графа.

 

4.3.2 Контрольні завдання

Завдання 1. Визначити, чи є для графа , зображеного на рис. 4.1, маршрут колом, циклом, простим циклом, якщо маршрут задається як:
1) ; 2) ; 3) ; 4) .


Рисунок 4.1 – Граф

 

Завдання 2. Який з наведених на рис. 4.2 орієнтованих графів є зв’язним? Який з графів є сильно зв’язним?

Рисунок 4.2

Завдання 3. Визначити число компонент зв’язності в графах та (рис. 4.3), якщо ці графи задаються так

Рисунок 4.3

Завдання 4. Визначити компоненти зв’язності в графі (рис. 4.4) і знайти маршрути довжини три (три дуги), які виходять з вершини .

 

Рисунок 4.4

 

Завдання 5. Знайти в графі (рис. 4.5) усі точки зчленування і мости.

Рисунок 4.5

 

Завдання 6. Знайти такі метричні характеристики графа (рис. 4.6): ексцентриситети усіх вершин графа, діаметр графа, радіус графа, периферійні вершини графа, діаметральні кола, центральні вершини графа, центр графа.

 

Рисунок 4.6

 

Завдання 7. Знайти для графа , який зображений на рис. 4.7, центр, радіус, діаметр, периферійні точки.


Рисунок 4.7

Завдання 8. Визначити, чи є графи і , зображені на рис. 4.8, ейлеровими (мають ейлерів цикл).

Рисунок 4.8

Завдання 9. Серед графів, які зображені на рис. 4.9, знайдіть ті, які мають власний ейлерів шлях.

Рисунок 4.9


Завдання 10.

Поясніть, які з орієнтованих графів, зображених на рис. 4.10, мають ейлерів цикл?

Рисунок 4.10

 

Завдання 11.

Найдіть гамільтонів цикл, якщо він існує, для кожного з графів, які зображені на рис. 4.11.

Рисунок 4.11

Завдання 12.

Нарисуйте такі графи: а) ; б) ; в) ; г) .


4.4 Приклади аудиторних і домашніх завдань

 

Завдання 1.Визначити, чи є для графа , зображеного на рис. 4.1, відповідний маршрут колом, простим колом, циклом, простим циклом, якщо маршрут заданий як: 1) ; 2) ; 3) ; 4) ; 5) .

Розв’язок. Відповідно до визначення кола, простого кола, циклу, простого циклу одержимо: 1) простий цикл (усі вершини й ребра різні); 2) цикл (усі ребра різні, а вершини ні); 3) просте коло; 4) маршрут (є однакові ребра й вершини); 5) просте коло.

Завдання 2. Визначити число компонент зв’язності в графі , якщо граф задається так (рис. 4.12)

Рисунок 4.12 – Граф , для якого визначається число компонент зв’язності

 

Розв’язок.Граф має дві компоненти зв’язності, в першу входять вершини , в другу - .

Завдання 3. Розкласти орграф , зображений на рис. 4.13, на сильно зв’язані компоненти.

Рисунок 4.13

Розв’язок.Граф розкладається на три сильно зв’язані компоненти , , (рис. 4.14)

Рисунок 4.14

 

Завдання 4.

Знайти в графі , зображеному на рис. 4.15, всі точки зчленування і мости.

Рисунок 4.15

Розв’язок.

Послідовно розглянемо ребра графа, вилучаючи їх із графа. Тільки вилучення ребра призводить до збільшення числа компонент зв’язності, тому є мостом. Аналогічно розглядаємо вершини графа і знаходимо, що вершини 3 і 5 є точками зчленування, тому що вилучення їх із графа призводить до збільшення числа компонент зв’язності.

Завдання 5.

Знайти такі метричні характеристики графа (рис. 4.16): ексцентриситети усіх вершин графа, діаметр графа, радіус графа, периферійні вершини графа, діаметральні кола, центральні вершини графа, центр графа.

Рисунок 4.16


Розв’язок.

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

Завдання 6.

Визначити, чи є граф , зображений на рис. 4.17, ейлеровим.

Рисунок 4.17

 

Розв’язок.

Використаємо теорему Ейлера: граф є ейлеровим (містить ейлерів цикл) тоді і тільки тоді, коли він зв’язний і степені всіх його вершин – парні.

Граф є зв’язним. Степені його вершин такі: , , . Граф не є ейлеровим, тому що не всі степені вершин є парними.

Завдання 7.

Чи має граф, зображений на рис. 4.18, власний ейлерів шлях?


 

Рисунок 4.18

Розв’язок.

Використаємо таку теорему: граф (мультограф або псевдограф) має власний ейлерів шлях тоді й тільки тоді, коли він зв’язний і рівно дві його вершини мають непарний степінь. Граф, зображений на рис. 4.18, зв’язний, має власний ейлерів шлях, оскільки рівно дві його вершини ( і ) мають непарний степінь, тобто .

Завдання 8.

Чи має орієнтований граф, зображений на рис. 4.19, ейлерів цикл?

Рисунок 4.19

Розв’язок.

Використаємо таку теорему: орієнтований граф має ейлерів цикл тоді й тільки тоді, коли він зв’язний, і півстепені виходу та заходу у вершині рівні. Орієнтований граф, зображений на рис. 4.19, не містить ейлерів цикл, тому що півстепені виходу та заходу у вершинах і не дорівнюють відповідно один одному.

Завдання 9.

Знайдіть гамільтонів цикл, якщо він існує, у графі , що зображений на рис. 4.20.

Рисунок 4.20

Розв’язок.

Гамільтонів цикл для графа буде таким .

 

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.