Елементи теорії алгоритмів.

Розділ 3

Елементи теорії графів.

Елементи теорії алгоритмів.

Тема 4. Елементи теорії графів

Приклад 4.

 

Способи завдання графа: матрицею інцидентності,

Списком ребер, матрицею суміжності.

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

Розглянемо наступні способи завдання графа :

а) Завдання графа матрицею інцидентності.

Означення. Матрицею інцидентності графа  називається  - матриця , де

Приклад 5.

вешини ребра	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ	Ⅵ	Ⅶ
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

 

Означення . Матрицею іинцидентності орграфа  називається  - матриця , де

 

    Приклад 6.

                                                                 

вершини ребра	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅴ	Ⅵ	Ⅶ
1	-1	1	0	0	0	0	0
2	-1	0	1	0	0	0	0
3	0	-1	0	1	0	0	0
4	0	1	0	-1	0	0	0
5	0	0	-1	0	1	0	0
6	0	0	-1	0	0	1	0
7	0	0	-1	0	0	0	1
8	0	0	0	1	0	1	2

 

   ³

                  1             ₄                                   

          

                   

₅       

                2                ⁶

                                ₇

                  

      ⁸

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

 

б). Завдання графа списком ребер.

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

    Приклад 7. Задамо списком ребер граф із приклада 5.

 

Ребра	Вершини
1	I, II
2	I, III
3	II, IV
4	I, V
5	II, VI
6	III, IV
7	III, V
8	IV, VI
9	V, VII
10	VI, VII

Приклад 8. Задамо списком ребер граф із приклада 6.

Ребра	Вершини
1	I, II
2	I, III
3	II, IV
4	IV, II
5	III, V
6	III, VI
7	III, VIII
8	VII, VII

За списком ребер графа легко побудувати його матрицю інцидентності. Дійсно, кожен рядок цього списку відповідає рядку матриці з тим же номером. Для неорієнтованого графа в рядку списку зазначені номери елементів рядка матриці інцидентності, які дорівнюють 1, і для орієнтованого графа в цьому рядку першим стоїть номер елемента рядка матриці, який дорівнює –1, а другим - номер елемента рядка,який дорівнює +1.

    в) Завдання графа матрицею суміжності.

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

Приклад 9. Задамо матрицею суміжності граф із приклада 5.

              I II III IV V VI VII

    I    0 1 1 0 1 0 0

    II   1 0 0 1 0 1 0 

    III  1 0 0 1 1 0 0 

    IV  0 1 1 0 0 1 0

    V   1 0 1 0 0 0 1

    VI  0 1 0 1 0 0 1

    VII 0 0 0 0 1 1 0

 

Приклад 10. Задамо матрицею суміжності граф із приклада 6.

                                               I II III IV V VI VII

    I   0 1 1 0 0 0 0

    II  0 0 0 1 0 0 0

    III 0 0 0 0 1 1 1

    IV 0 1 0 0 0 0 0

    V  0 0 0 0 0 0 0

    VI   0 0 0 0 0 0 0

    VII 0 0 0 0 0 0 1

    Матриця суміжності неорієнтованого графа симетрична (тобто ), а орієнтованого - не обов'язково.

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

 

Ізоморфізм графів.

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

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

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

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

Означення. Числова характеристика, однакова для всіх ізоморфних графів, називається інваріантом графа.

    Приклад. Число вершин p(G) і число ребер q(G) – інваріанти графа G

    Зауваження. Невідомо ніякого набору інваріантів, що визначають граф з точністю до ізоморфізму.

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

 

 

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

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

 

 

Елементи графів

Означення.Граф  називається підграфом графа  (позначається ), якщо  і/або . Якщо  і  і  або , то  називається власним підграфом графа . Якщо , а , то  називається остовним підграфом графа .

Означення. Число ребер, инцидентных вершині , називається ступенем вершини  і позначається :

Мінімальний ступінь вершини графа  позначається :

Максимальний ступінь вершини графа G позначається :

Означення. Якщо ступінь вершини дорівнює 0 ( ), то вершина називається ізольованою. Якщо ступінь вершини дорівнює 1 ( ), то вершина називається кінцевою або висячою.

Означення . В орграфі число дуг, що виходять з вершини, називається напівступенем виходу (позначається ), і вхідних – напівступенем заходу (позначається ).

Теорема (Ейлера). Сума ступенів вершин графа дорівнює подвоєній кількості ребер:

 

 для орграфа

 

Доведення: при підрахунку суми ступенів вершин кожне ребро враховується два рази: для одного кінця ребра і для іншого. ■

 

Ейлерові графи.

Операції над графами

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

Найбільш вживаними одномісними операціями є:

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

2. Операція вилучення ребра з графа  полягає у вилученні відповідної пари з E. При цьому усі вершини зберігаються.

3. Операція додавання вершини до графа . Додану вершину можна з'єднати ребрами з деякими вершинами графа .

4. Операція додавання ребра до графа  між двома вершинами.

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

Приклад.

G₁=(V₁, E₁)

G₂=(V₂, E₂)

V₂=V₁ V {V₆}

E₂=(E₁‏\{(V₁,V₅)})U{(V₁,V₆);

(V₆,V₅)}

G₂

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

Найбільш уживаними 2-місними операціями над графами є об'єднання і декартовий добуток.

Означення. Нехай G₁=(V₁,E₁); G₂=(V₂,E₂) – два графи таких, що V₁∩V₂=Ø, E₁∩E₂=Ø. Об'єднанням графів  і  називається граф  з множиною вершин V=V₁UV₂ і множиною ребер E₁UE₂

Приклад.

                                              

 

 

    Нехай задані графи  і  з множинами вершин  і .

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

Приклад.

                             

                                            =

                                               

 

Види графів

Тривіальні і повні графи.

Означення. Граф, що складається з однієї вершини, називається тривіальним.

Означення. Граф, що має максимально можливе число ребер називається повним.

2) Дерево і ліс.

Означення.Деревом називається зв'язний ациклічний неорієнтований граф, Дерево не містить петель і кратних ребер.

Приклад.

 

 

Властивості дерев.

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

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

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

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

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

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

 

Дерево з коренем.

Виділимо в дереві  вершину . Цю вершину називають коренем дерева , а саме дерево називають деревом з коренем. У дереві з коренем можна природним чином орієнтувати ребра. Вершину  ребра  можна з'єднати єдиним ланцюгом з коренем . Якщо цей ланцюг не містить ребра , то вводиться орієнтація від  к , в противному випадку – від  до . Орієнтоване в такий спосіб дерево з коренем називається орієнтованим деревом. У ньому всі ребра мають напрямок від кореня:

 

 

                                

 

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

Будь-яке дерево можна орієнтувати, вибравши як корінь будь-яку його вершину.

 

Блок-схеми алгоритмів.

Простими прикладами алгоритмів є відомі ще з початкової школи методи додавання і множення цілих невід’ємних чисел “стовпчиком” і ділення “куточком”. Інші алгоритми: алгоритм Евкліда знаходження НСД двох чисел, алгоритм розкладання числа на прості множники; спосіб побудови трикутника за трьома заданими сторонами; метод послідовного виключення невідомих при розв’язуванні систем лінійних алгебраїчних рівнянь; правило диференціювання складеної функції, та інші.

Означення.Алгоритмом називається процес, якому притаманні наступні властивості:

1. Наявність даних: вихідних (входів), проміжних і результатів (виходів).

2. Дискретність: у кожен момент часу множина (проміжних) даних виходить з множини даних, що малися в попередній момент часу шляхом виконання дискретної послідовності деяких елементарних дій, що називаються кроками алгоритму.

3. Елементарність кроку: операції, які виконуються на кожнім кроці, повинні бути відносно простими і локальними.

4. Детермінованість: множина даних, одержуваних у якийсь (не початковий) момент часу, однозначно визначається множиною даних, отриманих у попередній момент часу.

5. Результативність: зупинка після скінченого числа кроків ( що залежить від даних) із указівкою того, що вважати результатом.

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

Варто розрізняти:

1) опис алгоритму (інструкцію чи програму)

2) механізм реалізації алгоритму (наприклад, ЕОМ), що включає засоби пуску, зупинки, реалізації елементарних кроків, видачі результатів і забезпечення детермінованості, тобто керування ходом обчислення.

3) процес реалізації алгоритму, тобто послідовність кроків, що буде породжена при застосуванні алгоритму до конкретних даних.

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

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

Вершини блок-схеми можуть бути двох видів:

1) оператори, з них виходить одне ребро

2) логічні умови, з яких виходить 2 ребра.

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

Важлива особливість блок-схеми полягає в тому, що зв’язки, які вона описує, не залежать від того, чи є кроки елементарними чи являють собою самостійні алгоритми, так звані блоки. Можливість розбивати великий алгоритм на блоки широко використовується в програмуванні. І навпаки, за допомогою блок-схем можна декілька алгоритмів, розглянутих як блоки, зв'язати в один великий алгоритм.

На блок-схемі добре видна різниця між описом алгоритму і процесом його реалізації. Опис – це граф; процес реалізації – маршрут в графі. Різні маршрути в тому самому графі виникають при різних даних, і які створюють різні логічні умови в точках розгалуження. Якщо в процесі обчислення не з'являється умов, що приводять до кінця, то процес піде по нескінченному шляху, тобто зациклиться.

 

 

Розділ 3

Елементи теорії графів.

Елементи теорії алгоритмів.

1234567Следующая ⇒

Поделиться: