Главная | Обратная связь | Поможем написать вашу работу!

Основні поняття теорії графів

РОЗДІЛ 8

ПРОГРАМУВАННЯ НА МЕРЕЖАХ

Основні поняття теорії графів

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

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

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

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

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

─ задачі, які пов’язані з підрахунком кількості об’єктів заданої властивості;

─ задачі, що розв’язуються за алгоритмами на графах.

Позначимо деяку множину точок як , де точку з цієї множини назвемо вершиною. Ці вершини мають деякі зв’язки між собою, які утворюють множину зв’язків та відображуютьнаявність або відсутність зв’язків між парами елементів , тобто , де .

Якщо не має значення, в якому порядку беруться пари вершин – або , – то зв’язок такої пари вершин називається ребром (тобто без орієнтації).

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

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

Якщо та , то граф називається підграфом графа . У випадку, коли збігається з , то граф називається остовним підграфом графа .

Якщо для будь-яких двох вершин є зв’язок, то такий граф називається повним.

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

Приклади графів наведено нарис. 8. 1.

Граф Підграф Остовний граф Повний

граф

Рис. 8.1

Перехід від однієї вершини графа до другої виконується за допомогою шляху. У неорієнтованому графі шлях називається ланцюгом, який складається з послідовного набору суміжних ребер. Шлях в орграфі називається орієнтованим. Якщо перша та остання вершини шляху збігаються, то такий шлях називається циклом. Якщо для будь-якої пари є принаймні один шлях, то граф називається зв’язаним. Особистим класом графів є дерево – це зв’язаний граф, в якому відсутні цикли (рис.8.2).

1 4 1 4 1 4

3 3 3

2 5 2 5 2 5

Простий шлях Орієнтований шлях Цикл 1,3,4

1,3,5 1,3,4,5

Зв’язаний граф Граф-дерево

Рис. 8.2

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

3 3 5

5 1

2 2

Рис. 8.3

Такі графи ізоморфні.

12 3 4 5 Следующая ⇒