Зміст
1. Введення
2. Теоретична частина
а) Основні поняття теорії графів
б) Поняття суміжності, інцидентності, ступеня
в) Маршрути і шляхи
г) Матриці суміжності і інцедентності
3. Алгоритм - YANDEX_28поіска мінімального шляху з в в - YANDEX_31оріентірованном орграфе (алгоритм фронту хвилі)
4. Лістинг програми
5. Приклади виконання програми
6. Використана література
Введення
Розвиток теорії графів у основному зобов'язана великому числу всіляких додатків. Мабуть, з усіх математичних об'єктів графи займають одне з перших місць в якості формальних моделей реальних систем.
Графи знайшли застосування практично у всіх галузях наукових знань: фізики, біології, хімії, математики, історії, лінгвістиці, соціальних науках, техніці і т.п. Найбільшою популярністю теоретико-Графова моделі використовуються при дослідженні комунікаційних мереж, систем інформатики, хімічних і генетичних структур, електричних ланцюгів і інших систем мережевої структури.
Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається.
Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від знаходження оптимального маршруту між двома об'єктами на місцевості (напр. найкоротший шлях від дому до академії), також використовується в системах автопілота, використовується для знаходження оптимального маршруту при перевезеннях комутації інформаційного пакета Internet і мн. ін
Найкоротший шлях розглядається за допомогою графів.
Мета курсової роботи:
Розробити програму пошуку оптимального шляху в ненавантаженому орієнтованому графі на будь-якій мові програмування.
Теоретична частина:
а) Основні поняття теорії графів
Теорія графів як теоретична дисципліна може розглядатися як розділ дискретної математики, що досліджує властивості кінцевих множин із заданими відносинами між їх елементами. Як прикладна дисципліна теорія графів дозволяє описувати та досліджувати багато фізичні, технічні, економічні, біологічні, соціальні та інші системи. Наприклад, графом, зображеним на рис. 1, в якому точки - вершини графа - міста, лінії, з'єднують вершини - ребра - дороги, що з'єднують міста, описується так звана транспортна задача (задача знаходження найкоротшого шляху з одного міста-пункту в інший).
Рис. 1.
Формальне визначення графа таке. Нехай задано кінцеве безліч V, що складається з n елементів, називаних вершинами графа, і підмножина X декартова твори V Г— V, тобто, зване безліччю дуг, тоді орієнтованим графом D називається сукупність (V, X). Неорієнтованим графом G називається сукупність безлічі V і безлічі ребер - невпорядкованих пар елементів, кожен з яких належить безлічі V.
Однакові пари - паралельні або кратні ребра;
кратності ребер називають кількість однакових пар.
Рис.2.
Наприклад, кратність ребра {V1, v2} в графі, зображеному на рис. 2, дорівнює двом, кратність ребра {v3, v4} - трьом.
Псевдограф - граф, в якому є петлі і/або кратні ребра.
мультіграф - псевдограф без петель.
Граф - мультіграф, в якому ні одна пара не зустрічається більше одного разу.
Граф називається орієнтованим, якщо пари (v, w) є впорядкованими.
Ребра орієнтованого графа називаються дугами.
Отже, використовувані далі позначення:
V - безліч вершин;
X - безліч ребер або дуг;
v (або vi) - вершина або номер вершини;
G, G0 - неорієнтовані граф;
D, D0 - орієнтований;
{v, w} - ребра неорієнтованого графа;
{v, v} - позначення петлі;
(v, w) - дуги в орієнтованому графі;
v, w - вершини, x, y, z - дуги і ребра;
n (G), n (D) кількість вершин графа;
m (G) - кількість ребер, m (D) - кількість дуг.
Приклади
1) Орієнтований граф D = (V, X), V = {v1, v2, v3, v4},
X = {x1 = (v1, v2), x2 = (v1, v2), x3 = (v2, v2), x4 = (v2, v3)}.
Рис. 3.
2) неорієнтовані графів G = (V, X), V = {v1, v2, v3, v4, v5},
X = {x1 = {v1, v2}, x2 = {v2, v3}, x3 = {v2, v4}, x4 = {v3, v4}}.
Рис. 4.
б) Поняття суміжності, інцидентності, ступеня
Якщо x = {v, w} - ребро, то v і w - кінці ребер.
Якщо x = (v, w) - дуга орієнтованого графа, то v - початок, w - кінець дуги.
Вершина v і ребро x неорієнтованого графа (дуга x орієнтованого графа) називаються інцидентними, якщо v є кінцем ребра x (початком або кінцем дуги x).
Вершини v, w називаються суміжними, якщо {v, w} ГЋX.
Ступенем вершини v графа G називається число d (V) ребер графа G, інцидентних вершині v.
Вершина графа, що має ступінь 0 називається ізольованою, а ступінь 1 - висячої.
Полустепенью результату (заходу) вершини v орієнтованого графа D називається число d + (v) (d-(v)) дуг орієнтованого графа D, витікаючих з v (заходять в v).
Слід зауважити, що в випадку орієнтованого псевдографа внесок кожної петлі інцидентності вершині v дорівнює 1 як в d + (v), так і в d-(v).
в) Маршрути і шляхи
Послідовність v1x1v2x2v3 ... xkvk +1, (Де k Ві 1, viГЋV, i = 1, ..., k +1, xiГЋX, j = 1, ..., k), в якій чергуються вершини і ребра (дуги) і для кожного j = 1, ..., k ребро (дуга) xj має вид {vj, vj +1} (для орієнтованого графа (vj, vj +1)), називається маршрутом, з'єднує вершини v1 і vk +1 (шляхом з v1 у vk +1).
Довжина маршруту (шляху) - число ребер у маршруті (Дуг в дорозі).
г) Матриці суміжності і інцидентності
Нехай D = (V, X) орієнтований граф, V = {v1, ..., vn}, X = {x1, ..., xm}.
Матриця суміжності орієнтованого графа D - квадратна матриця
A (D) = [aij] порядку n, де
Матриця інцидентності - матриця B (D) = [bij] порядку n'm, де
Матрицею суміжності неорієнтованого графа G = (V, X) називається квадратна симетрична матриця A (G) = [aij] порядку n, де
.
Матриця інцидентності графа G називається матриця B (G) = [bij] порядку n'm, де
Алгоритм - YANDEX_28поіска мінімального шляху з в в - YANDEX_31оріентірованном орграфе (алгоритм фронту хвилі)
1) Позначаємо вершину індексом 0, потім позначаємо вершини ГЋ образу вершини індексом 1. Позначаємо їх FW1 (v). Вважаємо k = 1.
2) Якщо або k = n-1, і одночасно то вершина не досяжна з. Робота алгоритму закінчується.
В іншому випадку продовжуємо:
3) Якщо, то переходимо до кроку 4.
В іншому випадку ми знайшли мінімальний шлях з в і його довжина дорівнює k. Послідовність вершин
теорія орграф матриця алгоритм
є цей мінімальний шлях. Робота завершується.
4) Позначаємо індексом k +1 всі Непомічені вершини, які належать образу безлічі вершин c індексом k. Безліч вершин з індексом k +1 позначаємо. Присвоюємо k: = k +1 і переходимо до 2).
Зауваження
Безліч називається фронтом хвилі kго рівня.
Вершини можуть бути виділені неоднозначно, що відповідає випадку, якщо кілька мінімальних шляхів з в.
Щоб знайти відстані в орієнтованому графі, необхідно скласти матрицю - YANDEX_34мінімальних відстаней R (D) між його вершинами. Це квадратна матриця розмірності, елементи головної діагоналі якої дорівнюють нулю (, i = 1, .., n).
Спочатку складаємо матрицю суміжності. Потім переносимо одиниці з матриці суміжності в матрицю мінімальних відстаней (, якщо). Далі порядково заповнюємо матрицю наступним чином.
розглядаються першими рядок, в якій є одиниці. Нехай це рядок - i-тая і на перетині з j-тим стовпцем стоїть одиниця (тобто). Це означає, що з вершини можна потрапити в вершину за один крок. Розглядаєм...
