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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завдання 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

Розв’язок.

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

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

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