Основні види графів

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

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

Приклад 1. Побудувати повний двочастковий граф.

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

Отже, ейлеровим графом називається граф, в якому можна обійти всі вершини і при цьому пройти одне ребро тільки один раз. У ньому кожна вершина повинна мати тільки парне число ребер.

Приклад 2. Чи є повний граф з однаковим числом n ребер, яким инцидентна кожна вершина, ейлеровим графом? Пояснити відповідь. Привести приклади.

Відповідь. Якщо n - непарне число, то кожна вершина инцидентна n -1 ребрах. В такому випадку даний граф є ейлеровим графом. Приклади таких графів на малюнку нижче.

Регулярним графом називається зв'язний граф, всі вершини якого мають однаковий ступінь k. Таким чином, на малюнку наприклад 2 зображені приклади регулярних графів, званих по мірі його вершин 4-регулярними і 2-регулярними графами або регулярними графами 4-го ступеня і 2-го ступеня.

Число вершин регулярного графа k-го ступеня не може бути менше k +1. У регулярного графа непарної ступеня може бути лише парне число вершин.

Приклад 3. Побудувати регулярний граф, в якому найкоротший цикл має довжину 4.

Рішення. Міркуємо так: для того, щоб довжина циклу задовольняла заданій умові, потрібно, щоб число вершин графа було кратно чотирьом. Якщо число вершин дорівнює чотирьом, то вийде граф, зображений на малюнку нижче. Він є регулярним, але в ньому найкоротший цикл має довжину 3.

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

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

Приклад 4. Заданий двочастковий граф, в якому n - число вершин з множини A. а m - число вершин з безлічі B. В якому випадку граф буде ейлеровим графом, а в якому випадку - гамільтоновим графом?

Відповідь. Якщо n і n - парні, то граф буде ейлеровим. Якщо n = n. то граф буде гамільтоновим.

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

Деревом називається зв'язний граф без циклів (малюнок нижче). Будь-які дві вершини дерева пов'язані тільки одним маршрутом.

Число q ребер графа знаходиться зі співвідношення

де n - число вершин дерева.

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

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

Весь блок "Теорія графів"