ГРАФИ
Графічне подання рішення різних прикладних задач нам добре відомо. До графічних подань у широкому змісті можуть бути віднесені малюнки, креслення, графіки, діаграми, блок-схеми і т.п. З їхньою допомогою наочно ілюструються залежності процесів і явищ, логічні, структурні, причинно-наслідкові і інші взаємозв'язки. Однак теорія графів має свою власну проблематику. У дискретній математиці граф є найважливішим математичним поняттям. На основі теорії графів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування і керування, аналізу і проектування організаційних структур, аналізу процесу їх функціонування і багато іншого.
Основні визначення
Визначення 6.1. Графом називається сукупність двох множин точок і ліній, між якими визначене відношення інцидентності, причому, кожен елемент інцидентен рівно двом елементам . Елементи множини називаються вершинами, а елементи множини ‑ ребрами графа. Вершини і ребра графа називаються його елементами, тому найчастіше пишуть і .
|
|
Визначення 6.2. Якщо ребро з'єднує вершини , тоді вони є для нього кінцевими точками і називаються суміжними вершинами. Два ребра називаються суміжними, якщо вони інцидентні до загальної вершини.
Необхідно відзначити, що при зображенні графа не всі деталі малюнка мають значення. Так, наприклад, несуттєвою є довжина і кривизна ребер, взаємне розташування вершин на площині. Принциповим є тільки відношення інцидентності.
Приклад 6.1. Моделі, зображені на рис. 6.1 а, б, в, з погляду теорії графів однакові.
а б в
Рис. 6.1.
У деяких задачах інцидентні ребру вершини нерівноправні, а розглядаються в певному порядку. Тоді кожному ребру можна приписати напрямок від першої інцидентної вершини до другої.
Визначення 6.3. Напрямлені ребра називають орієнтованими ребрами або дугами, перша по черзі вершина називається початком дуги, а друга – її кінцем. Граф, що містить напрямлені ребра, називається орієнтованим графом або орграфом (рис. 6.2, а), а граф, що не містить напрямлених ребер – неорієнтованим або н-графом (рис. 6.2, б).
(а) (б)
Рис. 6.2.
Визначення 6.4. Ребро, що з'єднує деяку вершину саму із собою, називається петлею (рис. 6.3,а).
Визначення 6.5. Ребра, інцидентні до однієї і тієї ж вершини, називаються кратними (рис. 6.3,б). Граф, що містить кратні ребра, називається мультиграфом, а граф, що містить кратні ребра і петлі – псевдографом.
Визначення 6.6. Граф називається кінцевим, якщо множина його вершин і ребер звичайна.
Множина ребер графа може бути порожньою (рис. 6.3,в). Такий граф називається порожній або пустий.
|
|
(а) (б) (в)
Рис. 6.3.
Визначення 6.7. Граф без петель і кратних ребер називається повним, якщо кожна пара його вершин з'єднана ребром. Повний граф з вершинами позначається .
Приклад 6.2. На рис. 6.4 зображені повні графи , , , і відповідно:
Рис. 6.4.
Визначення 6.8. Доповненням графа називається граф , що має ті ж вершини, що і граф і тільки ті ребра, які необхідно додати до графа , щоб він став повним.
Приклад 6.3. Доповненням графа , зображеного на рис. 6.5,а є граф , зображений на рис. 6.5,б. Для порівняння, повний граф зображений на рис. 6.5,в.
(а) (б) (в)
Рис. 6.5.
Визначення 6.9. Степенем вершини називається кількість ребер, інцидентних цій вершині. Вершина степеня 0 називається ізольованою. У графі з петлями петля дає внесок в 2 одиниці у степінь вершини.
Теорема 6.1. Сума степеней вершин графа завжди парна: , де ‑ кількість ребер графа.
Доведення: Тому що кожне ребро графа має два кінці, степінь кожного кінця збільшується на 1 за рахунок одного ребра. Тобто у суму степеней всіх вершин кожне ребро вносить 2 одиниці. Отже, сума ступеней вершин повинна у два рази перевищувати число ребер, тобто бути парною.
Теорема 6.2. У будь-якому графі кількість вершин непарного степеня парна.
Доведення: Доведемо від оберненого. Припустимо, є непарне число вершин непарного степеня. Сума вершин парного степеня - парна. Сума степенів всіх вершин графа є сума вершин непарного і парного степенів. Така сума завжди є число непарне. Тобто сума степенів всіх вершин графа буде непарною. Це суперечить умові теореми 6.1. Прийшли до протиріччя. Отже, кількість вершин непарного степеня в будь-якому графі парна.
Справедливість теорем 6.1 і 6.2 можна проілюструвати на наступному прикладі.
Приклад 6.4. Визначити степені вершин графа, зображеного на рис. 6.6.
Рис. 6.6.
Рішення: ; ; ; ; ; .
. У розглянутому графі дев’ять ребер, а вершин непарного степеня дві: ; .
Визначення 6.10. Для орієнтованого графа визначаються дві степені вершин: ‑ кількість ребер, що виходять із вершини і ‑ кількість ребер, що входять у вершину . Петля дає внесок по одиниці в обидві степені.
В орграфі суми степенів всіх вершин і рівні між собою і дорівнюють кількості ребер цього графа: .
Приклад 6.5. Визначити степені вершин орграфа, зображеного на рис. 6.7.
Рис. 6.7.
Рішення:
, ; ; ; ;
, ; ; ; ;
.
Визначення 6.11. Граф називається підграфом графа , якщо кожна вершина і кожне ребро графа є відповідно вершиною і ребром графа .
Визначення 6.12. Граф називається остов (каркас) графа , якщо містить всі його вершини. За визначенням 6.11 він також є підграфом графа .
Приклад 6.6. На рис. 6.8(а,б,в) зображені підграфи графа, зображеного на рис. 6.8,г. Причому підграф (рис. 6.8,б) є його каркас.
а б в г
Рис. 6.8.
Один і той же граф можна зображувати по-різному. Різним образом можна розташовувати вершини на площині і ребра можна зображувати не тільки відрізками прямих (різної довжини) але і дугами. Тому порівнюючи графи, будемо спиратися на наступні визначення.
Визначення 6.13. Графи і рівні, якщо множини їхніх вершин і ребер, визначених через пари інцидентних їм вершин, збігаються. Наприклад, графи, зображені на рис. 6.1 рівні.
Задати граф – означає описати множини його вершин і ребер, а також відношення інцидентності. Коли граф ‑ кінцевий, для його опису досить занумерувати вершини і ребра.
Визначення 6.14. Граф називається повністю заданим у точному значенні, якщо нумерація його вершин і ребер зафіксована. Графи, що відрізняються тільки нумерацією, називаються ізоморфними.
Приведемо ще одне визначення ізоморфних графів.
Визначення 6.15. Графи і ізоморфні якщо їхні вершини можна пронумерувати таким чином, що ребро тоді і тільки тоді з'єднує вершини і у графі , коли ребро з'єднує вершини і у графі .
|
|
Приклад 6.7. Графи, зображені на рис. 6.9, (а), (б) ‑ ізоморфні.
(а) (б)
Рис. 6.9.
Приклад 6.8. На рис. 6.10 зображені графи ‑ з п'ятьма вершинами в кожному. Порівняти графи.
Рис. 6.10.
Рішення:
Графи ‑ ‑ неорієнтовані графи, а ‑ ‑ орієнтовані.
Графи і ‑ повні, причому = .
Граф не є повним, тому що незважаючи на то, що кожна пара вершин з'єднана ребром, є петля.
Графи і є мультиграфами, тому що містять кратні ребра.
Граф ‑ має порожню множину ребер, всі вершини графа є ізольованими.
Графи і є доповненням друг до друга.
Графи і не є рівними, тому що ребра 5 мають різний напрямок.
Граф ‑ орієнтований мультиграф, тому що має кратні ребра, у той час як граф не є мультиграфом, тому що ребра 8 і 9 по-різному орієнтовані.
Вправи:
1. Визначити степені вершин графів ‑ (рис. 6.10).
2. Визначити доповнення графів , зображених на рис. 6.11. Побудувати повні графи.
(а) (б) (в) (г)
(д) (е) (ж) (з)
Рис. 6.11.
3. Які пари графів, представлених на рис. 6.12, ізоморфні?
Рис. 6.12.