Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Навчальний посібник
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 4
6. ҐРАФИ
Ґрафічне представлення розв’язків різних прикладних задач є загальновідомим. До ґрафів у широкому сенсі можуть бути віднесені малюнки, креслення, ґрафіки, діаграми, блок-схеми тощо. З їх використанням наочно ілюструються залежності між процесами та явищами, логічні, структурні, причинно-наслідкові та інші взаємозв’язки. Однак, теорія ґрафів має свою власну проблематику. У дискретній математиці ґраф є найважливішим математичним поняттям. На основі теорії ґрафів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування та керування, аналізу й проектування організаційних структур, аналізу процесу їх функціонування та багато іншого.
6.1. Основні означення.
Означення 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.
6.2. Способи задання ґрафів.
Як відзначалося в п. 6.1 для задання ґрафу необхідно занумерувати вершини і ребра, а також задати відношення інцидентності. Відношення інцидентності будемо задавати трьома способами: матрицею інцидентності, матрицею суміжності, списком ребер ґрафу. Опишемо детально кожний із перерахованих способів.
Матриця інцидентності – це матриця розміром , у якій вертикально(рядки) вказуються вершини , а горизонтально (стовпці) – ребра . Тоді на перетині -того рядка і -того стовпця елемент матриці дорівнюватиме:
а) у випадку неорієнтованого ґрафу
б) у випадку орієнтованого ґрафу
Матриця суміжності це квадратна матриця розміром , у якій вертикально і горизонтально вказуються вершини ґрафу і . На перетинанні -того рядка і -того стовпця число дорівнює:
числу ребер, які з’єднують ці вершини в разі неорієнтованого ґрафу;
числу ребер з початком в -тій вершині і кінцем в -тій вершині для випадку орієнтованого ґрафу .
Список ребер ґрафу – це таблиця, що складається із трьох рядків. У першому перераховані всі ребра; у другому і третьому – інцидентні до них вершини:
у випадку неорієнтованого ґрафу порядок вершин у рядку довільний;
у випадку орієнтованого ґрафу першою записується вершина, в якій починається ребро (другий рядок); вершина, де закінчується ребро, записується у третій рядок.
Для нумерації вершин і ребер ґрафу використовують різний символьний запис: римські, арабські цифри, латинські букви.
Якщо ґрафи рівні, то їх матриці суміжності і інцидентності, а також список ребер, однакові.
Приклад 6.9. Задати матрицями інцидентності і суміжності, а також списком ребер, неорієнтований ґраф, показаний на рис. 6.13.
/
Рис. 6.13.
Розв’язок:
Матриця інцидентності Матриця суміжності
1
2
3
4
5
6
7
8
9
10
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
1
0
1
0
0
0
1
1
0
2
1
0
0
0
0
0
1
1
2
0
1
0
0
0
0
2
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
Тут .
Список ребер
Ребро
1
2
3
4
5
6
7
8
9
10
Вершини
початок
a
b
a
c
c
d
c
d
e
e
кінець
b
c
c
d
d
d
e
e
f
g
Як бачимо, у кожному стовпці матриці інцидентності є тільки два елементи, відмінних від нуля (або один, якщо ребро – петля).
Матриця суміжності симетрична щодо головної діагоналі.
Список ребер є найбільш компактним способом задання ґрафів.
Кожний із наведених способів однозначно описує ґраф, показаний на рис. 6.13.
Приклад 6.10. Задати матрицями інцидентності, суміжності, списком ребер орієнтований ґраф, показаний на рис. 6.14.
/
Рис. 6.14.
Розв’язок:
Матриця інцидентності
1
2
3
4
5
6
7
8
9
10
2
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
Матриця суміжності
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
Список ребер
Ребро
1
2
3
4
5
6
7
8
9
10
Вершини
початок
A
a
b
b
c
c
d
f
f
f
кінець
a
b
a
c
d
e
e
d
e
g
Для орієнтованого і неорієнтованого ґрафів відмінність матриць інцидентності полягає у вказуванні початку і кінця ребер, а матриця суміжності втрачає свою симетричність. У списку ребер важливий порядок вказівки вершин, які з’єднуються зазначеним ребром (від початку до кінця).
Як відзначалося вище, всі розглянуті способи задання ґрафів однозначно визначають ґраф. На запитання про те, чи можливо відновити ґраф по заданих матрицях інцидентності, суміжності або списку ребер очевидною є позитивна відповідь.
Із матриці інцидентності число ребер і вершин визначається з розмірності матриці: число ребер ґрафу дорівнює числу стовпців , а число вершин числу рядків матриці.
Із матриці суміжності число вершин визначається з розмірності матриці. Як вже відзначалося, матриця суміжності н-ґрафу симетрична щодо головної діагоналі, і кількість ребер визначається верхнім правим трикутником матриці, розташованим над головною діагоналлю, включаючи останню. Тобто, число ребер н-ґрафу дорівнює сумі елементів, розташованих на головній діагоналі і у верхньому правому трикутнику. У матриці суміжності орґрафу симетрія відсутня, а число ребер дорівнює сумі всіх елементів матриці суміжності.
Список ребер є скороченим варіантом матриці інцидентності. Кількість ребер очевидна, а кількість вершин дорівнює максимальному номеру всіх перерахованих вершин зі списку.
Отже, матриця інцидентності і список ребер, власне, еквівалентні, тобто, знаючи матрицю інцидентності, можна записати список ребер, і навпаки.
Побудова матриці інцидентності за списком ребер. Кожен рядок списку ребер відповідає рядку в матриці інцидентності з тим же номером. Для неорієнтованого ґрафу в кожному рядку списку ребер зазначені номери елементів матриці інцидентності, дорівнюють 1 (всі інші елементи – нулі). Для орієнтованого ґрафу першою вказується вершина, що відповідає початку ребра (у матриці інцидентності – елемент ), а другий – відповідному кінцю ребра (у матриці інцидентності – елемент 1). При збігу елементів у рядку списку ребер, у відповідному рядку матриці інцидентності записується число, відмінне від , 0, 1, наприклад, 2. Така ситуація відповідає наявності у ґрафі петель.
Приклад 6.11. Побудувати матрицю інцидентності неорієнтованого ґрафу за списком ребер:
Ребро
1
2
3
4
5
6
7
8
Вершини
початок
a
d
e
C
a
d
b
f
кінець
d
f
f
E
b
c
f
f
Розв’язок:
Матриця інцидентності, відповідно до списку ребер, має вигляд:
1
2
3
4
5
6
7
8
1
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
1
2
Приклад 6.12. Записати список ребер відповідно до матриці інцидентності орієнтованого ґрафу :
1
2
3
4
5
6
7
8
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
Розв’язок:
Список ребер, записаний відповідно до матриці інцидентності орієнтованого ґрафу має вигляд:
Ребро
1
2
3
4
5
6
7
8
Вершини
початок
b
b
c
c
d
d
e
a
кінець
a
c
c
d
d
e
f
f
Означенням 6.14 було введене поняття ізоморфних ґрафів. Чи можливо встановити, чи є ґрафи ізоморфними за їхніми матрицями інцидентності, суміжності, або списку ребер?
Для перевірки ізоморфності ґрафів і за матрицею суміжності необхідно визначити, чи існує така перестановка рядків і стовпців у матриці суміжності , щоб у результаті вийшла матриця суміжності . Для цього треба зробити всі можливі перестановки рядків і стовпців (а їхня максимальна кількість дорівнює ∙) ! Якщо після однієї із цих перестановок матриці суміжності тотожно збіжаться, то ґрафи ізоморфні.
Для перевірки ізоморфності ґрафів і за матрицею інцидентності (і списку ребер) необхідно визначити, чи існує така перестановка рядків і стовпців у матриці інцидентності , щоб у результаті вийшла матриця . Тут треба зробити всі можливі пари перестановок рядків і стовпців (а їхня максимальна кількість дорівнює ) ! Якщо після однієї із цих перестановок матриці інцидентності тотожно збіжаться, то ґрафи ізоморфні.
І в першому, і в другому випадку ці операції потребують значних часових затрат, тому їх використання не завжди виправдане. Тому на практиці ізоморфність ґрафів найчастіше встановлюють з їх графічних представлень.
Вправи:
1. Задати матрицями інцидентності, суміжності і списком ребер неорієнтовані ґрафи, що показані на рис. 6.15:
/ /
(а) (б)
/ /
(в) (г)
/
(д)
Рис. 6.15.
2. Задати матрицями інцидентності, суміжності і списком ребер орієнтовані ґрафи, котрі показані на рис. 6.16:
/ /
(а) (б)
/ /
(в) (г)
Рис. 6.16.
3. Для заданих матриць інцидентності а) і б) знайти відповідний ґраф.
а) б)
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
1
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
1
4. Для заданих матриць суміжності а) і б) знайти відповідний ґраф.
а) б)
0
0
1
0
1
0
0
1
0
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
1
0
1
1
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
0
1
0
1
0
0
0
0
0
1
1
0
6.3. Зв’язність ґрафу . Маршрути, шляхи, ланцюги, цикли.
6.3.1. неорієнтований ґраф.
Означення 6.16. Маршрутом (шляхом) у ґрафі називається така послідовність ребер , у якій кожні два сусідніх ребра і мають спільну вершину. У маршруті те саме ребро може зустрічатися кілька разів. Іншими словами маршрут – це сукупність ребер, які об’єднані разом вершинами так, що можна рухатися ними уздовж ґрафу .
Означення 6.17. Початок маршруту – це вершина , інцидентна ребру і не інцидентна ребру . Кінець маршруту – це вершина , інцидентна ребру і не інцидентна . Якщо ребра , ( , ) кратні, то необхідно додатково вказувати, яку із двох інцидентних вершин вважати початком (кінцем) маршруту.
Означення 6.18. Маршрут довжини послідовність, що містить ребер. Іншими словами, довжиною маршруту називається кількість ребер у ньому; при цьому кожне ребро враховується стільки разів, скільки разів воно зустрічається в маршруті.
Позначення маршруту з у послідовністю є надлишкове, тому ми будемо позначати маршрут як перелік вершин .
Означення 6.19. Маршрут, усі ребра якого різні, називається ланцюгом. Ланцюг, що не перетинає себе, тобто не має вершин, які повторюються, називається простим.
Приклад 6.13. Визначити можливі маршрути (і їхню довжину) з вершини в у ґрафі, показаному на рис. 6.17.
/
Рис. 6.17
Розв’язок: з вершини у ведуть, наприклад, шляхи:
1) довжини 2; 5) довжини 6;
2) довжини 4; 6) довжини 6;
3) довжини 4; 7) довжини 8;
4) довжини 6; 8) довжини 10.
Шляхи: 6), 8) не є простими.
Означення 6.20. Маршрут, у якому збігаються початок і кінець і називається циклічним. Циклічний маршрут називається циклом, якщо він є ланцюг, і простим циклом – якщо це простий ланцюг.
Наприклад, маршрут для ґрафу, показаного на рис. 6.17, є простим циклом; а маршрут є циклом, але не буде простим, оскільки містить вершини, які повторюються.
Означення 6.21. Вершини і ґрафу називаються зв’язаними, якщо існує маршрут з початком у і кінцем у . Маршрут між зв’язаними вершинами може бути поданий простим ланцюгом.
Означення 6.22. Ґраф називається зв’язним, якщо будь-які пари його вершин зв’язані між собою.
Приклад 6.14. Ґраф, показаний на рис. 6.18,а – не зв’язний, а ґраф на рис. 6.18,б – зв’язний.
/ /
(а) (б)
Рис. 6.18
Теорема 6.3. Якщо існує маршрут з вершини в ґрафу , то існує простий ланцюг, що з’єднує вершини і .
Наслідок. Ґраф є зв’язним тоді і тільки тоді, коли між будь-якими двома його вершинами існує простий ланцюг.
Означення 6.23. Максимальний непорожний зв’язний підґраф ґрафу називається компонентом ґрафу .
Іншими словами, кожен ґраф представляє собою об’єднання своїх компонент, які попарно не перетинаються.
Незв’язний ґраф має, як мінімум, два компоненти. Наприклад, ґраф, показаний на рис. 6.18,а, має два компоненти: і .
Означення 6.24. Вершина називається точкою з’єднання, якщо видалення її із ґрафу приводить до збільшення числа компонент зв’язності.
Означення 6.25. Ребро утворює міст, якщо його видалення з ґрафу приводить до збільшення числа компонент зв’язності.
Наприклад, у ґрафі, показаному на рис. 6.17 вершина є точкою з’єднання, а ребро, що з’єднує вершини міст.
Означення 6.26. Множина ребер зв’язного ґрафу називається множиною розрізу, якщо видалення ребер із множини порушує зв’язність ґрафу, а видалення власної підмножини множини залишає ґраф зв’язним. Якщо множина складається з одного ребра, то це ребро називається ребром розрізу.
Приклад 6.15. Визначити ребра розрізу ґрафу, показаного на рис. 6.19.
/
Рис. 6.19.
Розв’язок: ребра , і є ребрами розрізу. Їх видалення порушує зв’язність
19.02.2013 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора