Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Графи, різновиди графів та дії над ними.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2000
Тип роботи:
Розрахункова робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
1.Графи, різновиди графів та дії над ними.
1.1. Графом EMBED Equation.3 називається пара непустої множини EMBED Equation.3 та відображення EMBED Equation.3 в ній. Інакше: граф EMBED Equation.3 складається з множини EMBED Equation.3 та невпорядкованих пар EMBED Equation.3 з множини EMBED Equation.3 – вершин графа.
Пара, EMBED Equation.3 ; EMBED Equation.3 і EMBED Equation.3 називається ребром графа EMBED Equation.3 , причому говорять, що EMBED Equation.3 та EMBED Equation.3 – суміжні вершини, EMBED Equation.3 , а ребро EMBED Equation.3 інцендентне вершині EMBED Equation.3 і вершині EMBED Equation.3 . Якщо в EMBED Equation.3 ребра EMBED Equation.3 є в одній і тій же вершині, то вони називаються суміжними ребрами.
Граф з EMBED Equation.3 вершинами та EMBED Equation.3 ребрами називається EMBED Equation.3 графом ; граф (1,0) – тривіальний і ребро, що з’єднує точку з собою називається петлею.
Типи графів:
1. Мультиграф – граф, що не містить петель, але пара вершин в якому з’єднується кілька раз – кратні ребра.
2. Псевдограф – граф, в якому допускається і петля, і кратні ребра. EMBED Equation.3
3. Орієнтований граф (орграф) – граф EMBED Equation.3 , в якому EMBED Equation.3 є множиною впорядкованих пар вершин із EMBED Equation.3 . Елементи із EMBED Equation.3 називаються орієнтованими ребрами або дугами. Дуги виду EMBED Equation.3 та EMBED Equation.3 - називаються симетричними дугами.
4. Направлений граф – орграф, що не має симетричних дуг.
5. Граф називається поміченим або перенумерованим, якщо його вершини відрізняються деякими проміжками, індексами EMBED Equation.3 .
6. Підграф графа EMBED Equation.3 , EMBED Equation.3 ; EMBED Equation.3 , EMBED Equation.3 .
7. Якщо EMBED Equation.3 - підграф EMBED Equation.3 , то EMBED Equation.3 називається надграфом для EMBED Equation.3 .
8. Частинний граф (основний граф) – підграф, що містить всі вершини графа.
9. Породженим множиною вершин EMBED Equation.3 підграф EMBED Equation.3 називається максимальним для EMBED Equation.3 з множиною EMBED Equation.3 ; в EMBED Equation.3 вершини суміжні тоді і тільки тоді, коли вони суміжні в EMBED Equation.3 . На введені поняття покажемо кілька прикладів.
SHAPE \* MERGEFORMAT 1) EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
граф породжений частинний
підграф граф
2) EMBED Equation.3 – підграф EMBED Equation.3 , що не містить вершини EMBED Equation.3 . Це максимальний підграф EMBED Equation.3 , що не містить вершини EMBED Equation.3 .
3) EMBED Equation.3 – частинний підграф без ребра EMBED Equation.3 , він є максимальним підграфом без ребра EMBED Equation.3 .
Процес видалення вершини EMBED Equation.3 та ребра EMBED Equation.3 графа EMBED Equation.3 показано на рисунку.
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
4) EMBED Equation.3 , де EMBED Equation.3 не суміжні в EMBED Equation.3 , утворює найменший надграф для EMBED Equation.3 , що містить ребро EMBED Equation.3 .
1.2. Два графи EMBED Equation.3 і EMBED Equation.3 називаються ізоморфними, EMBED Equation.3 , якщо між множинами їх вершин існує взаємно-однозначна відповідність, що зберігає суміжність, наприклад EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
Гіпотеза Улана. Нехай граф EMBED Equation.3 має n-вершини EMBED Equation.3 граф EMBED Equation.3 має n-вершин EMBED Equation.3 . Якщо для кожного EMBED Equation.3 підграфи EMBED Equation.3 і EMBED Equation.3 ізоморфні, то графи EMBED Equation.3 і EMBED Equation.3 – ізоморфні.
Інваріант графа EMBED Equation.3 – це число, зв’язане з EMBED Equation.3 , яке приймає одне і те ж значення для будь-якого графа, що ізоморфний з EMBED Equation.3 . Наприклад, числа EMBED Equation.3 є інваріантами (n, m)–графа. Повний набір інаріантів графа визначає граф з точністю до ізоморфізму. Зокрема, повним набором інваріантів є для EMBED Equation.3 проблема. Визначити повний набір інваріантів графа.
1.3. Маршрути і звідність графа.
1. В орграфі EMBED Equation.3 ,
10. Шлях – послідовність EMBED Equation.3 EMBED Equation.3 де EMBED Equation.3 – суміжні, а кінець EMBED Equation.3 є початком EMBED Equation.3 . Шлях буває складний (з повторенням дуг), простий (без кратних дуг, але з повторенням вершин), елементарний – з різними вершинами. Якщо EMBED Equation.3 , то шлях називається контуром. Контури також діляться на складні, прості і елементарні. Довжина шляху – кількість дуг в ньому.
20. Ланцюг – послідовність ребер, де кінець попереднього ребра є початком наступного. Ланцюги, як і щляхи, бувають складні, прості і елементарні. Замкнений ланцюг (початок співпадає з кінцем) називається циклом. Цикли є складні, прості і елементарні.
30. Граф називається звідним, якщо будь-яка пара його вершин з’єднана елементарним ланцюгом.
40. Віддаль EMBED Equation.3 між вершинами EMBED Equation.3 - довжина найкоротшого елементарного ланцюга, що з’єднує EMBED Equation.3 з EMBED Equation.3 ; якщо EMBED Equation.3 і EMBED Equation.3 не з’єднані в EMBED Equation.3 , тоді EMBED Equation.3 . З означення випливає, що
1) EMBED Equation.3 і EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 ; 2) EMBED Equation.3 ,
3) EMBED Equation.3 .
Найкоротший елементарний ланцюг EMBED Equation.3 в графі EMBED Equation.3 називається геодезичною між EMBED Equation.3 і EMBED Equation.3 .
Діаметр EMBED Equation.3 зв’язного графа EMBED Equation.3 – довжина найдовшої геодезичної.
50. Степінь вершини EMBED Equation.3 в EMBED Equation.3 - EMBED Equation.3 або EMBED Equation.3 – це число ребер (дуг), інциндентних xі.
60. Граф називається сильно звідним, якщо він є орграфом, і існує для EMBED Equation.3 , шлях EMBED Equation.3 і шлях EMBED Equation.3 .
2. Деякі види графів.
10. Повний граф EMBED Equation.3 – кожна пара вершин суміжні і EMBED Equation.3 має EMBED Equation.3 ребер.
20. EMBED Equation.3 - цілком незвідний граф з n-ізольованими вершинами.
30. Однорідний (регулярний) граф – граф степеня EMBED Equation.3 .
40. Доповняльним EMBED Equation.3 до графа EMBED Equation.3 називається граф або остовий граф, в якому в якому дві вершини суміжні тоді і тільки тоді, коли в EMBED Equation.3 вони не суміжні.
50. Сомодоповняльний граф EMBED Equation.3 – такий, що ізоморфний своєму доповняльному графу, EMBED Equation.3 .
60. Дводольний граф (біграф, біхроматичний, простий, паракомбінація) – це граф, множина вершин якого EMBED Equation.3 , EMBED Equation.3 така, що кожне ребро EMBED Equation.3 з’єднує множини EMBED Equation.3 (будемо говорити, що кожне ребро графа EMBED Equation.3 з’єднує множини X1 і X2). Такий граф будемо позначати EMBED Equation.3 .
70. Повний дводольний граф EMBED Equation.3 - дводольний граф з EMBED Equation.3 , EMBED Equation.3 , кожна вершина з EMBED Equation.3 з’єднана з кожною вершиною з EMBED Equation.3 .
80. Зірка (гроно) – дводольний граф EMBED Equation.3 .
90. Граф перетинів сім’ї множин:
Нехай EMBED Equation.3 – множина, а EMBED Equation.3 – сім’я різних непустих його підмножин, об’єднання яких дає S. Граф перетинів EMBED Equation.3 цієї сім’ї – граф з вершиною множин EMBED Equation.3 , в якому EMBED Equation.3 суміжна з EMBED Equation.3 якщо EMBED Equation.3 . Наприклад, EMBED Equation.3 , EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
100. Кліка графа – це його будь-який максимальний повний підграф.
110. Граф клік даного графа EMBED Equation.3 - це граф перетину всіх клік.
120. Плоский граф – це граф, представлений на площині без самоперетинів ребер.
130. Планарний граф – граф, що ізоморфний плоскому графу.
140. Ейлеровий граф – граф, в якому існує ейлеровий цикл, тобто простий цикл, що охоплює всі ребра графа.
150. Гамільтоновий граф – граф, в якому існує елементарний цикл, що включає всі вершини графа.
160. Ациклічний граф – граф, що не має циклів.
170. Дерево – зв’язний ациклічний граф.
180. Прадерево – направлений граф-дерево.
190. Реберний граф для EMBED Equation.3 ; EMBED Equation.3 - граф перетинів EMBED Equation.3 .
200. Тотальний граф EMBED Equation.3 - граф, в якого множиною вершин є EMBED Equation.3 і дві вершини суміжні тоді і тільки тоді, коли вони суміжні в EMBED Equation.3 .
210. Зовнішньопланарний граф – планарний граф, якого можна вкласти на площині так, щоб всі його вершини належали одній грані.
220. Турнір EMBED Equation.3 - направлений повний граф.
3. Операції над графами.
10. Доповнення графа – по EMBED Equation.3 утворення EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
20. Квадрат EMBED Equation.3 графа EMBED Equation.3 , має ту ж саму множину вершин, що і в EMBED Equation.3 , EMBED Equation.3 і дві вершини суміжні тоді і тільки тоді, EMBED Equation.3 , коли EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
30. Степінь графа EMBED Equation.3 ; EMBED Equation.3 , EMBED Equation.3 і дві вершини в EMBED Equation.3 суміжні тоді і тільки тоді, коли EMBED Equation.3 .
40. Об’єднання графів EMBED Equation.3 і EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3 тоді
EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
50. Переріз графів EMBED Equation.3 і EMBED Equation.3 .
EMBED Equation.3 ; EMBED Equation.3 тоді
EMBED Equation.3 EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
60. Сполучення графів EMBED Equation.3 , EMBED Equation.3 , тоді EMBED Equation.3 , де EMBED Equation.3 - множина ребер, що з’єднує всі EMBED Equation.3 з усіма EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
70. Кратність графа: якщо EMBED Equation.3 - зв’язний граф, то EMBED Equation.3 - граф з однаковими компонентами, кожна з яких ізоморфна EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
80. Приєднання графів: якщо EMBED Equation.3 і EMBED Equation.3 такі, що ототожнення довільної вершини графа EMBED Equation.3 з будь-якою вершиною графа EMBED Equation.3 приводить до одного і того ж графа (з точністю до ізоморфізму), то граф EMBED Equation.3 , отриманий з допомогою описуваного ототожнювання вершин, позначаються через EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
90. Добуток графів EMBED Equation.3 і EMBED Equation.3 : вершини EMBED Equation.3 є суміжні тоді і тільки тоді, коли EMBED Equation.3 і EMBED Equation.3 або EMBED Equation.3 EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
100. Композиція графів EMBED Equation.3 має множину вершин EMBED Equation.3 - декартовий добуток, тоді вершина EMBED Equation.3 суміжна з вершиною EMBED Equation.3 , причому EMBED Equation.3 , EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 або EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
110. Прямий добуток графів EMBED Equation.3 .
EMBED Equation.3 , EMBED Equation.3 , тоді EMBED Equation.3 , причому EMBED Equation.3 і EMBED Equation.3 :
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
120. Пряма сума графів EMBED Equation.3 .
1) EMBED Equation.3 , 2) EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
130. Корона графів EMBED Equation.3 , кожна вершина EMBED Equation.3 графа EMBED Equation.3 сполучається (з’єднується) з одним екземпляром графа EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
4. Шляхи в графі.
Розглядається декілька алгоритмів для знаходження найкоротших шляхів у зваженому і незваженому графах.
4.1. Шлях з найменшою кількістю дуг.
Задача: нехай задано довільний граф EMBED Equation.3 . Знайти такий шлях, що з’єднує дві дані вершини EMBED Equation.3 і містить найменшу кількість дуг.
Алгоритм розв’язку.
10. Присвоїти вершині EMBED Equation.3 мітку EMBED Equation.3 .
20. Якщо EMBED Equation.3 і EMBED Equation.3 , то присвоїти кожній такій вершині мітку EMBED Equation.3 .
30. Нехай EMBED Equation.3 , EMBED Equation.3 - множина вершини EMBED Equation.3 присвоїти мітку EMBED Equation.3
40. Процес присвоєння вершинам міток припинити, якщо тільки вершина EMBED Equation.3 отримає мітку EMBED Equation.3 , EMBED Equation.3 .
50. Розглянути вершини EMBED Equation.3 такі, що EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 .
Шлях EMBED Equation.3 дає розв’язок задачі.
4.2. Шлях зваженого графа найкоротшої довжини.
Нехай кожній дузі EMBED Equation.3 співставлено додатне число EMBED Equation.3 - довжина дуги. Довжиною шляху EMBED Equation.3 - називається сума довжин дуг, які входять в EMBED Equation.3 : EMBED Equation.3 .
Задача: знайти у зваженому графі EMBED Equation.3 шлях EMBED Equation.3 найкоротшої довжини, що з’єднує вершину EMBED Equation.3 та EMBED Equation.3 .
Алгоритм розв’язку:
10. Пронумерувати вершини графа EMBED Equation.3 так, щоб вершина EMBED Equation.3 отримала номер EMBED Equation.3 . Позначити вершину EMBED Equation.3 через EMBED Equation.3 (причому вершина EMBED Equation.3 нехай співпадає з деякою вершиною EMBED Equation.3 ).
20. Присвоїти кожній вершині EMBED Equation.3 мітку EMBED Equation.3 так, щоб EMBED Equation.3 , EMBED Equation.3 при EMBED Equation.3 .
30. Знайти таку дугу EMBED Equation.3 , для якої EMBED Equation.3 , вважаючи, що EMBED Equation.3 . У вершині EMBED Equation.3 змінить мітку EMBED Equation.3 на нову меншу мітку EMBED Equation.3 .
40. Застосовуємо правило 30 до тих пір, поки для кожної дуги EMBED Equation.3 не стане справедлива нерівність: EMBED Equation.3 .
50. В множині EMBED Equation.3 , знайти таку вершину EMBED Equation.3 , що EMBED Equation.3 .
Аналогічно, в множині EMBED Equation.3 знайти таку вершину EMBED Equation.3 , щоб виконувалась рівність: EMBED Equation.3 і так далі.
Після деякої кількості кроків вершина EMBED Equation.3 співпадає з вершиною EMBED Equation.3 . Шлях EMBED Equation.3 – найкоротший шлях з довжиною EMBED Equation.3 .
5. Знаходження ейлеревих циклів графа.
Нехай EMBED Equation.3 – зв’язний мультиграф, степені всіх вершин якого парні.
Задача. Знайти ейлерів цикл в графі EMBED Equation.3 .
Алгоритм розв’язку.
10 Вибрати довільну деяку вершину EMBED Equation.3 .
20 Вибрати довільно деяке ребро EMBED Equation.3 , інцидентне EMBED Equation.3 , і присвоїти номер 1 (пройдене ребро).
30 Кожне наступне ребро викреслювати і присвоювати йому номер на одиницю більший номера попереднього викресленого ребра.
40 Знаходячись у вершині EMBED Equation.3 , не вибирати ребра, яке з’єднує EMBED Equation.3 з EMBED Equation.3 , якщо тільки є можливість іншого вибору.
50 Знаходячись у вершині EMBED Equation.3 , не вибирати ребра, яке є „перешийком” (при видаленні якого граф, утворений незакресленими ребрами, розпадається на дві компоненти зв’язності, що мають хоча б по одному ребру).
60 Після того, як у графі будуть закреслені всі ребра, цикл EMBED Equation.3 , утворений ребрами з номерами від 1 до EMBED Equation.3 , де EMBED Equation.3 – число ребер у графі, є Ейлеревим циклом.
Перелік різних шляхів в графі.
Нехай EMBED Equation.3 - орієнтований граф, Х – множина вершин, Г – відображення на множині Х.
SHAPE \* MERGEFORMAT х2
х3
х1
х4
Шляхом µ в графі G називається така впорядкована послідовність вершин, в якій хк є одночасно кінцем дуги EMBED Equation.3 і початком дуги EMBED Equation.3 .
Шлях µ називається елементарним, якщо всі його вершини різні.
Шлях µ називається простим, якщо в ньому повторюються деякі вершини, але не повторюються дуги.
Шлях µ називається складним, якщо в ньому повторюються і вершини, і дуги.
Перелік різних шляхів в графі здійснюється за допомогою матриці суміжності. Матриця EMBED Equation.3 називається матрицею суміжності графа EMBED Equation.3 з вершинами EMBED Equation.3 , якщо елементи aij цієї матриці дорівнюють кількості дуг, які з’єднують вершину xi з вершиною xj.
Графи, які відповідають сумі і добутку матриць суміжності двох даних графів із спільною множиною вершин EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3 ;
Розглянемо суму і добуток двох матриць (двох графів).
Теорема. Якщо граф EMBED Equation.3 заданий матрицею суміжності EMBED Equation.3 , а граф EMBED Equation.3 - матрицею суміжності EMBED Equation.3 , то:
сумі матриць А і В відповідає граф з тією ж самою множиною вершин Х, а множина дуг належить об’єднанню EMBED Equation.3 :
EMBED Equation.3 ;
добутку матриць А і В відповідає граф EMBED Equation.3 , в якому вершини EMBED Equation.3 суміжні лише тоді, коли EMBED Equation.3 .
Доведення. 1) Додавши матриці А, В отримаємо матрицю EMBED Equation.3 , загальна кількість дуг якої дорівнює сумі дуг в першому і другому графах.
SHAPE \* MERGEFORMAT х1
х2
х4
х3
G
х1
х2
х4
х3
H
Для графів G i H побудуємо відповідно матриці суміжності А і В:
EMBED Equation.3 і EMBED Equation.3 ,
тоді С=А+В матиме вигляд:
EMBED Equation.3 ,
і результуючий граф буде таким:
SHAPE \* MERGEFORMAT х1
х2
х3
х4
2) Якщо перемножити матриці суміжності А, В тоді матимемо добуток EMBED Equation.3 елементів матриць суміжностей.
SHAPE \* MERGEFORMAT хk
хj
хi
Загальна кількість всіх шляхів, що з’єднують вершину EMBED Equation.3 з вершиною EMBED Equation.3 чисельно буде рівна елементу EMBED Equation.3 , а це – загальний член в добутку матриць А і В.
причому, якщо:
SHAPE \* MERGEFORMAT x1
x3
x2
G:
x1
x3
x2
H:
Побудуємо матриці суміжностей для заданих двох графів G i H:
EMBED Equation.3 ; EMBED Equation.3 ,
тоді згідно правила множення матриць EMBED Equation.3 матиме вигляд:
EMBED Equation.3 .
Для матриці суміжності С отримаемо граф:
SHAPE \* MERGEFORMAT х1
х3
х2
Кількість шляхів в графі заданої довжини
Нехай задано граф EMBED Equation.3 , якому відповідає матриця суміжності EMBED Equation.3 .
Теорема. Кількість шляхів довжини l даного графа G, що йдуть з вершини EMBED Equation.3 в EMBED Equation.3 чисельно рівна елементові EMBED Equation.3 матриці EMBED Equation.3 , де EMBED Equation.3 .
Доведення: Для доведення застосуємо метод математичної індукції. У випадку, коли l = 1 твердження очевидне. Нехай теорема справедлива для EMBED Equation.3 . Доведемо справедливість теореми для EMBED Equation.3 :
EMBED Equation.3 ,
Теорему доведено.
Приклад:
SHAPE \* MERGEFORMAT G
x3
x2
x1
EMBED Equation.3 .
Побудуємо граф, що відповідає EMBED Equation.3 :
SHAPE \* MERGEFORMAT х3
х1
х2
EMBED Equation.3
Знайдемо граф, що відповідає матриці EMBED Equation.3 :
SHAPE \* MERGEFORMAT х1
х2
х3
EMBED Equation.3
Кількість контурів довжини „3” (три) в антисиметричному повному графі.
Граф називається повним антисиметричним, якщо кожна пара його вершин з’єднана тільки в одному напрямку:
SHAPE \* MERGEFORMAT х2
х3
х4
х1
Теорема. Якщо граф EMBED Equation.3 , в якому кількість вершин EMBED Equation.3 , задається матрицею суміжності EMBED Equation.3 , то кількість контурів довжиною „3” такого повного антисиметричного, а саме EMBED Equation.3
EMBED Equation.3 , де EMBED Equation.3 .
Доведення. Розглянемо кількість циклів довжини „3” (цикли довжини „3” – неорієнтований контур).
Вона буде виражатись числом
EMBED Equation.3
з вершини EMBED Equation.3 виходить EMBED Equation.3 дуг, де EMBED Equation.3 число циклів, що не співпадають з контуром.
Загальна кількість циклів, що не співпадають з контуром є така:
EMBED Equation.3
EMBED Equation.3 .
В нашому випадку EMBED Equation.3 EMBED Equation.3 ;
а саме контури
EMBED Equation.3 ;
EMBED Equation.3 .
х2
х3
х4
х1
2)
х2
х3
х4
х1
1)
Кількість шляхів у графі, які відповідають даній трійці невід’ємних чисел
Задано граф EMBED Equation.3 , якому відповідає матриця суміжності EMBED Equation.3 . Задана трійка невід’ємних цілих чисел EMBED Equation.3 .
Говорять, що шлях EMBED Equation.3 відповідає даній трійці невід’ємних цілих чисел EMBED Equation.3 , якщо у послідовності вершин знайдуться дві такі вершини EMBED Equation.3 , що шлях EMBED Equation.3 має довжину EMBED Equation.3 , EMBED Equation.3 . Шлях EMBED Equation.3 має довжину EMBED Equation.3 , EMBED Equation.3 , відповідно EMBED Equation.3 .
Тоді EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 ;
EMBED Equation.3 ;
EMBED Equation.3 .
Теорема. Кількість шляхів у графі EMBED Equation.3 з матрицею суміжності EMBED Equation.3 , які відповідають числам EMBED Equation.3 і йдуть з вершини EMBED Equation.3 у вершину EMBED Equation.3 , дорівнює загальному членові EMBED Equation.3 матриці EMBED Equation.3 .
Доведення. Елементи матриці суміжності EMBED Equation.3 , дорівнюють кількості шляхів, що йдуть із вершини EMBED Equation.3 у вершину EMBED Equation.3 , і мають довжину EMBED Equation.3 . Елементи матриці EMBED Equation.3 , дають кількість контурів довжини EMBED Equation.3 , які починаються і закінчуються у вершині EMBED Equation.3 даного графа. Загальний член EMBED Equation.3 дає кількість шляхів довжини EMBED Equation.3 , що йдуть із вершини EMBED Equation.3 у вершину EMBED Equation.3 . Кількість шляхів, які відповідають трійці EMBED Equation.3 визначаються загальним членом EMBED Equation.3 . Кількість шляхів, які відповідають трійці EMBED Equation.3 визначаються загальним членом EMBED Equation.3
6. Поняття про теорію переліку Поста.
Проблема переліку включає 3 аспекти:
технічні труднощі, зв’язані з обчисленнями. Ця трудність в певній мірі може бути подолана за допомогою твірних функцій.
доводиться здійснювати перелік не самих елементів, а їх класів еквівалентності, тобто перелік різних об’єктів, що вважаються еквівалентними.
різним об’єктам приписуються різні ваги.
Група підстановок
1. Нехай задана множина елементів EMBED Equation.3 . На цій множині введена певна операція (множення).
EMBED Equation.3 , яка задовільняє таким властивостям:
EMBED Equation.3 ;
EMBED Equation.3 ;
EMBED Equation.3 .
EMBED Equation.3 — група відносно множення.
2. Група підстановок.
Нехай дана множина EMBED Equation.3 .
Підстановкою на цій множині EMBED Equation.3 називається взаємно-однозначне відображення множини EMBED Equation.3 на себе, а саме:
EMBED Equation.3
EMBED Equation.3 – множина підстановок.
Множина всіх підстановок утворює групу відносно множення підстановок
EMBED Equation.3 і EMBED Equation.3 тоді EMBED Equation.3 і EMBED Equation.3 .
3. Цикл множини , що відповідає даній підстановці
EMBED Equation.3 , коли EMBED Equation.3 .
1). Кожна підстановка розбиває EMBED Equation.3 на цикли (цикл – підмножина, в якій один елемент переходить в інший елемент з цієї підмножини).
EMBED Equation.3 .
Наприклад, тоді маємо цикли EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 .
Множина EMBED Equation.3 в даному випадку розбивається на 3 цикли.
Довжиною циклу називається кількість елементів в цьому циклі. Нехай EMBED Equation.3 кількість циклів довжини EMBED Equation.3 , де EMBED Equation.3 . Тоді маємо, що кількість циклів довжини „1” є 1, довжини „2” – 1 і довжини „3” – 1.
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 .
Назвемо вектор EMBED Equation.3 списком даної підстановки.
Виконується така закономірність, що EMBED Equation.3 , де m – кількість елементів у підстановці.
В даному випадку маємо EMBED Equation.3
EMBED Equation.3
2) EMBED Equation.3 і EMBED Equation.3 , маємо (1,4); (2,3); (5,6); (7,8); (9). Тоді EMBED Equation.3 , EMBED Equation.3 ; EMBED Equation.3 і EMBED Equation.3
3) Цикловий індекс групи підстановок.
Задана множина EMBED Equation.3 . Розглядається група EMBED Equation.3 підстановок.
Для кожної підстановки визначимо її тип таким чином, що:
EMBED Equation.3 – цикловий індекс групи підстановок.
S=(1,2,3) і відповідно
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 .
Тоді маємо
T( EMBED Equation.3 )=(3,0,0); T( EMBED Equation.3 )=(1,1,0); T( EMBED Equation.3 )=(0,0,1); T( EMBED Equation.3 )=(1,1,0); T( EMBED Equation.3 )=(0,0,1); T( EMBED Equation.3 )=(1,1,0),
і EMBED Equation.3 . Тоді
EMBED Equation.3 .
Задача
Множина з 4-х елементів.
Знайти власну підгрупу і обчислити її цикловий індекс.
3) EMBED Equation.3 ; EMBED Equation.3 , EMBED Equation.3 , і EMBED Equation.3 .
4) Ваги та запас і перлік запасів.
Нехай
EMBED Equation.3 , де EMBED Equation.3 і EMBED Equation.3 — скінченні множини.
10 Множину елементів із EMBED Equation.3 назвемо запасами.
20 Кожному елементу EMBED Equation.3 приписується певна вага (число або змінна величина).
Переліком множини EMBED Equation.3 називається сума
EMBED Equation.3 переліку EMBED Equation.3 .
1) EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 і відповідно знаходимо EMBED Equation.3 і EMBED Equation.3 .
Перелік EMBED Equation.3
2) Вага та перелік функції EMBED Equation.3 .
Вагою функції EMBED Equation.3 .
EMBED Equation.3
Класи еквівалентності даного відображення EMBED Equation.3 .
EMBED Equation.3 називаються еквівалентними EMBED Equation.3 , якщо існує підстановка EMBED Equation.3 , що EMBED Equation.3 .
Властивості підстановок
рефлексивність EMBED Equation.3 ;
симетричність EMBED Equation.3 ;
транзитивність EMBED Equation.3 .
Множину класів еквівалентності позначимо через F. До F[f] відносяться всі відображення, які еквівалентні функції f.
EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
Маємо EMBED Equation.3 і EMBED Equation.3 .
Довести, що класи еквівалентності володіють певними властивостями.
1.а. рефлексивність EMBED Equation.3 , тобто існує така підстановка EMBED Equation.3 , що виконується умова EMBED Equation.3 .
Візьмемо відображення EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
і підстановку EMBED Equation.3
Тоді маємо, що EMBED Equation.3 і залишається на місці.
1.б. симетричність EMBED Equation.3 .
Візьмемо
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
і
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
EMBED Equation.3 тобто EMBED Equation.3
EMBED Equation.3 тобто EMBED Equation.3
Умова симетричності в даному випадку виконується
1.в. транзитивність EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
і
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
1
2
3
,
EMBED Equation.3 маємо EMBED Equation.3 ; EMBED Equation.3 EMBED Equation.3 ;
звідки для EMBED Equation.3 EMBED Equation.3 .
Оскільки EMBED Equation.3 і відповідно EMBED Equation.3 еквівалентні між собою, а саме EMBED Equation.3 ;
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3
Дві еквівалентні функції мають однакову вагу EMBED Equation.3 EMBED Equation.3
Спільне значення ваги всіх еквівалентних між собою функцій приймається за вагу класу еквівалентності цих функцій.
EMBED Equation.3 – визначається через перелік відповідних функцій.
Основна теорема теорії переліку (теорема Поста)
Задана множина EMBED Equation.3 і визначена група підстановок множини EMBED Equation.3 , яка розбиває групу на класи еквівалентності EMBED Equation.3 . Тоді перелік класів еквівалентності дорівнює цикловому індексу групи підстановок при таких значеннях аргументу.
EMBED Equation.3 .
Наслідок. Якщо Прийняти всі ваги EMBED Equation.3 , то кількість класів еквівалентності дорівнює EMBED Equation.3 .
Приклад.
EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3 ;
EMBED Equation.3 ; де EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 і EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 .
Таким чином EMBED Equation.3 .
Лабіринти.
Пошук виходу з лабіринту, коридори якого не обов’язково знаходяться на одному рівні. Також стосується ситуації мандрівок в печерах або катакомбах.
Задача. Вважаючи, що можна певним способом визначити, в якому напрямку пройдено коридор і який коридор приводить до перехрестя вперше треба, знаходячись на перехресті EMBED Equation.3 знайти вихід EMBED Equation.3 із лабіринту.
Алгоритм розв’язку
Ніколи не проходити по одному й тому ж коридорі в одному й тому ж напрямку двічі.
Знаходячись на деякому перехресті, не вибирати коридору, який привів на це перехрестя вперше, якщо тільки є можливість іншого вибору.
7 Задача про найбільший потік у зваженому графі
Поняття потоку на транспортній сітці, алгоритм знаходження найбільшого потоку та критерії існування потоку, який насичує вихідні дуги сітки, є плодотворним для багатьох прикладних і теоретичних питань комбінаторного аналізу.
7.1 Потоки на транспортних сітках
Теорія транспортних сіток виникла при розв’язку задач, пов’язаних з організацією перевезень вантажу.
10 Основна задача теорії транспортних сіток.
Транспортна сітка EMBED Equation.3 є сукупністю двох об’єктів
1) зв’язного графа EMBED Equation.3 з такими властивостями:
в графі EMBED Equation.3 відсутні петлі
в графі EMBED Equation.3 існує одна і тільки одна вершина EMBED Equation.3 така, що множина EMBED Equation.3 .
2) цілочисельної невід’ємної функції EMBED Equation.3 , заданої на множині EMBED Equation.3 дуг графа EMBED Equation.3 .
Вершина EMBED Equation.3 називається входом сітки, вершина – виходом. Значення EMBED Equation.3 на дузі EMBED Equation.3 називається пропускною здатністю дуги.
3) Нехай EMBED Equation.3 – множина дуг, що заходять у вершину EMBED Equation.3 , а EMBED Equation.3 – множина дуг, які виходять із вершини EMBED Equation.3 . Цілочисельна невід’ємна функція , задана на множині EMBED Equation.3 дуг графа EMBED Equation.3 називається потоком, якщо вона задовольняє таким умовам:
а) EMBED Equation.3
б) EMBED Equation.3
Із а) випливає, що EMBED Equation.3 .
Величина EMBED Equation.3 називається величиною потоку EMBED Equation.3 і позначається EMBED Equation.3 .
Задача.
На транспортній сітці EMBED Equation.3 побудувати потік найбільшої величини.
Дуга EMBED Equation.3 називається насиченою, якщо EMBED Equation.3 . Потік EMBED Equation.3 називається повним, якщо кожен шлях із EMBED Equation.3 у EMBED Equation.3 містить хоча би одну насичену дугу.
Алгоритм Форда – Фалкерсона (для знаходження потоку найбільшої величини).
10 Перенумерувати довільним чином вершини сітки EMBED Equation.3 відмінні від EMBED Equation.3 і EMBED Equation.3 .
20 Побудувати довільний потік EMBED Equation.3 на транспортній сітці EMBED Equation.3 (наприклад покласти EMBED Equation.3 ).
30 Розглянути шляхи, що з’єднують вхід сітки EMBED Equation.3 з виходом EMBED Equation.3 , якщо потік EMBED Equation.3 повний – перейти до пункту 40. Іншому випадку розглянути шлях EMBED Equation.3 , що з’єднує EMBED Equation.3 з EMBED Equation.3 , всі дуги якого ненасичені. Побудувати новий потік EMBED Equation.3 :
EMBED Equation.3
Повторити увесь процес до одержання повного потоку EMBED Equation.3 .
Присвоїти цілочисельні мітки вершинам сітки EMBED Equation.3 і знаки (+) або (-) дугам по правилах:
а) входу EMBED Equation.3 присвоїти мітку 0,
б) якщо вершина EMBED Equation.3 одержала деяку мітку, а EMBED Equation.3 – ще не помічена вершина, то вершині EMBED Equation.3 , такій, що EMBED Equation.3 , присвоїти мітку EMBED Equation.3 , а дузі EMBED Equation.3 знак (+); вершині EMBED Equation.3 , такій, що EMBED Equation.3 , присвоїти мітку EMBED Equation.3 , а дузі EMBED Equation.3 знак (-); інші вершини і дуги мітки і знаку не отримують.
в) повторяти процес, описаний в 40(б) до тих пір, поки не виявиться, що присвоїти мітку або знак новій непоміченій вершині або дузі неможливо. Якщо в результаті процесу вершина EMBED Equation.3 не одержить мітки, то потік володіє найбільшою величиною. В іншому випадку перейти до пункту г).
г) розглянути послідовність відмічених вершин EMBED Equation.3 , кожна з яких має мітку, що дорівнює номеру наступної вершини, і послідовність дуг EMBED Equation.3 (необов’язково шлях), що з’єднує послідовні вершини із EMBED Equation.3 . Побудувати новий потік EMBED Equation.3 таким чином:
EMBED Equation.3
і перейти до п.4.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора