є зв'язок n вершин за помощью m дуг, розмір матріці інцідентності (n * m), альо вона Менш Зручна, чем матриця суміжності.
Інша форма задання графу - список зв'язності. Граф з n вершинами буде задаватіся списками - по одному для кожної вершини. Список для вершини и містіть вершини, суміжні з і.
3.3 Дерева
Дерево - це орієнтований аціклічній граф, для Якого віконуються Такі умови:
1) існує одна вершина, в яка не заходити жодних ребро (корінь);
2) у будь-яку вершину, крім кореня, входити ЛИШЕ ОДНЕ ребро;
3) з кореня можна найти Унікальний шлях до кожної вершини дерева.
орієнтований граф з кількох вершин - ліс. Бінарне дерево - шкірний вершина має два нащадки. При поиска Певного Вузли у дереві Використовують Пряме и зворотнє проходження вузлів.
Способи зберігання дерев
Послідовне зберігання діліться на рівневі и діжкове.
Рівневе: для шкірного уровня дерева послідовно вказаються его Вузли.
Дужкове: дужками вказуються нащадки даного Вузли.
зв'язного зберігання - списки, КОЖЕН список містіть вказівнімі на нащадків.
Поиск у глибінь и ширину
Поиск в глибінь - послідовно відвідуються ВСІ Нові вершини-нащадки (ЯКЩО вершина булу відвідана, то вона перестає буті новою).
Поиск у ширину - перевіряються суміжні вершини одного уровня, потім - Переход на нижчих рівень.
Остові дерева
Довільне дерево неорієнтованого графу G = назівається остов.
Ейлерові шляхи
Для Вирішення багатьох прикладних проблем Використовують ейлерові шляхи. Ейлеревімі назівають шляхи, Які проходять через шкірні ребро графу один раз. Если початковий вузол є кінцевім, то такий граф назівається ейлеревім циклом.
Задача про Кенігсбергські мости. p> Теорема. У графі існує ейлерів шлях Тільки тоді, коли граф зв'язного и містіть НЕ больше двох вершин непарного ступенів.
Знаходження найкоротшіх Шляхів у графі
Потрібно найти мінімальній шлях (контур) у навантаженості графі, де d (u, v) - відстань между вершинами u и v, Якщо не існує шляху, то d (u, v) =.
4. Загальна схема алгоритму Харта, Нельсона и Рафаєля
узагальнення алгорітмів поиска найкоротшого шляху на графах є алгоритм Харта, Нельсона и Рафаєля. p> Введемо Такі позначені:
s - початкова вершина;
q - цільова вершина;
c (i, j) - довжина ребра между вершинами и та j;
d (i, j) - довжина найкоротшого шляху между і-ю та j-ю вершинами;
g (n) - довжина найкоротшого шляху между від початкової вершини до n-ї;
h (n) - довжина найкоротшого шляху между від n-ї вершини до цільової;
f (n) - довжина найкоротшого шляху между від початкової вершини до цільової, Які проходять через вершину n, при цьом f (n) = g (n) + h (n);
g * (n) - оцінка Довжина найкоротшого шляху между від початкової вершини до n-ї;
h * (n) - еврістічна функція, яка задає оцінку Довжина найкоротшого шляху между від n-ї вершини до цільової;
f * (n) = g * (n) + h * (n) - оцінка f (n);
L (n) - множини всех наступніків вершини n.
Введемо Робочі множини: OPEN I CLOSE. p> Загальна схема поиска найкоротшого шляху:
1. Сформувати шраф поиска G, Який спочатку Складається з початкової вершини s. Занести s до OPEN. Прокласті g * (s) = g (s) = 0. p> 2. Сформувати множини CLOSE, яка спочатку буде порожня.
3. Если множини OPEN порожня, то вихід - потрібного шляху НЕ існує;
4. Взяти з множини OPEN перший елемент m (відповідно до порядку, встановленому кроком 9), Вилучити m з OPEN та занести ее до CLOSE.
5. Если m - цільова вершина, то Успіх. Відновіті шлях від s до m на Основі відновлюючі вказівніків, что встановлені на кроках 6-8 и Завершити алгоритм.
6. Розкрити вершину m, отріматі множини наступніків L (m). Додати до графу G ВСІ вершини, Які належати L (m), альо НЕ належати G, разом з відповіднімі дугами. Додати ці вершини до OPEN. Для кожної вершини обчісліті ОЦІНКИ f * (k) = g * (k) + h * (k), поклал g * (k) = g * (m) + c (m, k), Встановити з k до m відновлюючій вказівнік ;
7. Для кожної вершини n з тихий, Які попал до L (m), альо Вже належали OPEN або CLOSE, переобчісліті ОЦІНКИ g * (n) = min ((g * (m) + c (m, n), g * (n) ). Если оцінка зменшіть, то перевстановіті з неї відновлюючій вказівнік до m.
8. Для всіх вершин з L (m), Які до цього знаходится в CLOSE, перевстановіті відновлюючі вказівнімі для шкірного з наступніків ціх вершин у напрямі найкоротшого шляху.
9. Перевпорядкуваті множини OPEN за ЗРОСТАННЯ значень f *.
10. Повернутися на крок 3.
Если еврістічна функція НЕ вікорістовується, тоб h * (n) = 0 и f * (n) = g * (n), то отримується алгоритм Дейкстри.
Если взяти g * (n) = 0, утворюється алгоритм Дорана и Мічі. br/>
4.1 Планування в просторі задач....
