Размещено на http://www.allbest.ru/

Основи дискретної математики

1. Історія виникнення теорії графів

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

Зображення графів на площині

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

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

2. Завдання 1

Задано граф суміжності.

Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) - це квадратна матриця A розміру n, в якій значення елементу a_ij рівне числу ребер з i-ї вершини графа в j-у вершину.

Завдання 1.1.

Побудувати граф, що відповідає їй.

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

Завдання 1.2.

Побудувати множину пар вершин, що відповідає ії.

,

Завдання 1.3.

Знайти кількість вершин, ребер(дуг) і степені (напівстепені) кожної вершини графу.

Вершина, Вузол - базове поняття: точка, де можуть сходитися / розходитися ребра та/або дуги. Множина вершин графа G позначається V(G).

Дивлячись на це вершин цього графа 5.

V(G)=5.

Ребро графа (дуга графа) - базове поняття. Ребро з'єднує дві вершини графа. Ребра позначають Е(G).

E(G)=18.

Напівстепінь входу в орграфі для вершини v - кількість дуг, що входять в вершину. Позначається .

.

.

.

.

.

Напівстепінь виходу в орграфі для вершини v - кількість дуг, що виходять з вершини. Позначається .

.

.

.

.

.

В орієнтованому мульти графі сума всіх напівстепені входу повинен дорівнювати напівстепені виходу.

=



Завдання 1.4.

Побудувати матрицю інцидентності графа

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

	E1	E2	E3	E4	E5	E6	E7	E8	E9	E10	E11	E12	E13	E14	E15	E16	E17	E18
V1	2	1	1	1	-1	0	0	0	0	0	0	0	0	0	0	0	0	0
V2	0	-1	0	0	1	1	1	1	0	0	0	-1	0	0	0	0	0	0
V3	0	0	0	0	0	-1	-1	-1	1	1	1	0	-1	-1	0	0	-1	0
V4	0	0	-1	-1	0	0	0	0	-1	-1	0	1	1	1	1	1	0	-1
V5	0	0	0	0	0	0	0	0	0	0	-1	0	0	0	-1	-1	1	1

Завдання 1.5.

Побудувати граф, ізоморфний заданому

Ізоморфізмом графів G і H це бієкція між множинами вершин G і H такий, що будь-які дві вершини u і v графа G суміжні в G тоді і тільки тоді, коли ?(u) і ?(v) суміжні в H. Такий тип бієкції зазвичай зветься «реброзберігальна бієкція», згідно із загальним поняттям ізоморфізму як бієкції зі збереженням структури.

Завдання 1.6.

Чи існує Ейлерів цикл та шлях у графа?

Ейлерів ланцюг - ланцюг в графі, що проходить кожне ребро рівно один раз. Схожим чином.

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

Орієнтований граф має Ейлерів цикл, якщо він сильно зв'язний і кожна вершина має однаковий вхідний і вихідний степінь. Цей граф не має Ейлеревого циклу і Ейлеревого шляху теж не має.

Завдання 1.7.

Чи існує Гамільтонів цикл та шлях у графа?

Гамільтомнів грамф - в математиці це граф, що містить гамільтонів шлях або гамільтонів цикл.

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

Гамільтонів шлях виконується за умови, якщо степінь будь-яких двох не суміжних вершин не менше, загальної кількості вершин. Візьмемо вершину deg(v₁)=4 та deg(v₃)=9 та сумуємо іх 4+9=13>5. Звідси беремо висновок, що наш граф має Гамільтонів шлях.

За теоремою Дірка «Якщо для кожної вершини V зв'язного простого графа n3 вершинами, виконується нерівність deg(v)n/2, тоді цей граф має Гамільтонів цикл». Виконавши розрахунки, можна побачити, що наш граф має Гамільтонів цикл.

Завдання 1.8.

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

Зважений граф - це граф ребра якого мають вагу.

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

Крок 1

Ініціалізація. Відстань до всіх вершин графа V = . Відстань до а = 0. Жодна вершина графа ще не опрацьована.

Крок 2

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

Крок 3

Перший по порядку сусід 1-ї вершини - 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.

Кроки 4, 5

Аналогічну операцію проробляєм з двома іншими сусідами 1-ї вершини - 3-ю та 6-ю.

Крок 6

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

Крок 7

Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7.

І знову намагаємося зменшити відстань до всіх сусідів 2-ї вершини, намагаючись пройти в них через 2-у. Сусідами 2-ї вершини є 1, 3, 4.

Крок 8

Перший (по порядку) сусід вершини №2 - 1-а вершина. Але вона вже оброблена (або викреслена - див. крок 6). Тому з 1-ою вершиною нічого не робимо.

Крок 8 (з іншими вхідними даними)

Інший сусід вершини 2 - вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ої + відстань між 2-ою і 4-ою вершинами = 7 + 15 = 22. Оскільки 22 < ?, встановлюємо відстань до вершини №4 рівним 22.

Крок 9

Ще один сусід вершини 2 - вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини №3 і дорівнює 9, тому поточну відстань до 3-ї вершини не міняємо.

Крок 10

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



Кроки 11 - 15

По вже «відпрацьованій» схемі повторюємо кроки 2 - 6. Тепер «найближчою» виявляється вершина №3. Після її «обробки» отримаємо такі результати:

Наступні кроки

Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).

Завершення виконання алгоритму

Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої становить 7, до 3-ої - 9, до 4-ої - 20, до 5-ої - 20, до 6-ої - 11 умовних одиниць.

Вирішення:E2=7

E3=3

E4=4

E5=5

E6=10

E7=13

E8=2

E9=17

E10=16

E11=9

E12=11

E13=19

E14=20

E15=23

E16=21

E17=1

E18=6

E19=22



Беремо шлях від . Беру ребра з найменшими вагами

0

7 3

7 16 21

16 21

Отже найкоротший шлях від дорівнює 21

Завдання 1.9.

Побудувати простий граф (n=6), розфарбувати його та визначити хроматичне число.

Хроматичне число графа - мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори.

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



Хроматичне число графа дорівнює 3.

3. Завдання 2

Задано дерево

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

Завдання 2.1.

Визначити корінь дерева, його батьків, синів, листки. Які вершини є внутрішніми?

Корінь - це вершина яка є початком дерева і від якої ідуть всі інші вершини.

Корінь - а.

Батько - це вершина з якої виходять інші вершини(сини).

Батьки - a, b, d, f, k, j.

Сини - це вершини які мають батька, тобто це вершини, що виходять з початкових вершин.

Сини-b, c, d, e, g, q, i, k, j, f, s, r, w, z.

Листки - це вершини-сини, які не мають продовження, тобто своїх синів.

Листки-e, q, i, f, s, r, w, z.

Внутрішні вершини - це вершини які не є листками

Внутрішні вершини - a, b, c, d, q, k, i

Завдання 2.2.

Визначити рівень кожної вершини та висоту дерева.

Висота дерева-це довжина від перших синів кореня дерева до листків. Висота дерева позначається h.

h=4

Рівень кожної вершини:

Завдання 2.3.

Чи є дерево завершеним?

Завершене дерево-це дерево на якому всі сини розміри на а-рівні. Тому це дерево не є завершеним, бо листки знаходяться не на одному рівні.

Завдання 2.4.

Чи є дерево збалансованим?

Збалансоване дерево - це дерева сини якого знаходяться на n та (n-1) рівнях. Це дерево не є збалансованим, тому що лиски найменшого 2, а найбільшого 4

Завдання 2.5.

Виконати обхід дерева у прямому, внутрішньому та зворотному порядках

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

Існують три види таких обходів, кожний з яких визначається рекурсивно:

· прямий порядок наступної послідовності:

1. відвідати корінь

2. відвідати ліве піддерево

3. відвідати праве піддерево

Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.

· зворотний порядок наступної послідовності:

1. відвідати ліве піддерево

2. відвідати праве піддерево

3. відвідати корінь

Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.

· центрований (центральний) порядок наступної послідовності:

1. відвідати ліве піддерево

2. відвідати корінь

3. відвідати праве піддерево

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

RAB:a, b, d, i, k, s, r, c, g, q, j, w, z, f. - прямий порядок

ARB:i, d, s, k, r, a, g, c, w, jz, q, f. - центрований (центральний) порядок

ABR:i, s, r, k, d, e, b, g, w, z, j, f, q, c, a. - зворотний порядок

Завдання 2.6.

Визначити ексцентриситет вершин та цент дерева

Ексцентриситет - це довжина найдовшого простого шляху який починається в цій вершині.

a=4; b=5; c=5; d=6; e=6; g=6; q=6; i=7; k=7; j=7; f=7; s=8; r=8; w=8; z=8.

Центр дерева є вершина а.

Завдання 3.

Побудувати блок-схему алгоритму розв'язку завдання 1.2. Реалізувати отриманий алгоритм у певному середовищі програмування та зафіксувати.

Ведемо розміри матриці N>1.

граф ізоморфний дейкстра ексцентриситет

Список літератури

1. Нікольский Ю.В., Пасічник В.В., Щербета Ю.М. Дискретна математика - К.: Видавнича група BHV, 2007. - 368 c.:іл.

2. Кук Д., Бейз Г. Компьюрная математика. - М: Наука, 1990.

Размещено на Allbest.ru

...