|
|
Подання графу в пам'яті комп'ютера
Графічний спосіб подання (якщо граф невеликий). Використання матриць. Матриця легко описуванняється, й при аналізі характеристик графу можна використати алгоритми лінійної алгебри. Також використається подання графа у зв'язній пам'яті, утому випадку, якщо значна кількість елементів у матриці дорівнює нулю (матриця не заповнена). Одним із матричних способів подання графу є матриця суміжності. Нехай задано граф G = (X, U), |Х| = n. Маємо матрицю А розмірності n х n, що називається матрицею суміжності, якщо елементи її визначаються так:
Приклад 7.1. Нехай маємо граф, поданий рисунку 9.
Рисунок 9 – Приклад графу.
Йому відповідає така матриця суміжності:
Розглянемо застосування матричної алгебри для визначення характеристик графу. Вираз aikLakj означає, що між вузлами i і j є дві дуги, що проходять через вузол k, якщо значення виразу дорівнює True. Вираз A L A = А(2) – логічні операції заміняються арифметичними. Тоді кожний елемент аij буде подавати інформацію про те, чи є шлях з i в j (i,j = 1, 2,...,n)... Вираз А(n) = А(n-1) L А означає, чи є шлях довжиною n між різними вузлами і. По діагоналі буде характеристика, чи є цикли (контури) у матриці.
Алгоритм обчислення заданого виразу: 1) Р = А; 2) повторити 3, 4 (k=1, 2,...,n); 3) повторити 4 для i=1,2,...,n; 4) повторити Ріj = Ріj ∨ (Ріk L Pkj), j=1, 2,...,n... У зв'язній пам'яті найчастіше подання графу здійснюється за допомогою структур суміжності. Для кожної вершини множини X задається множина М(Хi) відповідно до дуг її послідовників (якщо це орграф) або сусідів (для неорграфу). Отже, структура суміжності графу G буде списком таких множин: <М(Х1),М(Х2),...,М(Хn)> для всіх його вершин. Приклад 7.2. Нехай маємо граф, поданий на рисунку 10 (вузли позначаємо у вигляді цифр: 1,2,..., n):
Рисунок 10 – Подання графу.
Для неорграфу: 1:2, 3; 2:1, 3; 3:1, 2; 4:5; 5:4. Для орграфу: 1:2; 2:3; 3:1; 4:5; 5:-. Структуру суміжності можна реалізувати масивом з т лінійно зв'язаних списків:
Подання графу може вплинути на ефективність алгоритму. Часто запис алгоритмів на графах задається в термінах вершин і дуг, незалежно від подання графу. Наприклад, алгоритм визначення кількості послідовників вершин: С(Х)=0, S – кількість дуг. S = 0;
початок С(х)=0;
S = S + С(х); кінець;
Контрольні питання
1. Дайте визначення графу. 2. Дайте визначення дерева за допомогою графу. 3. Поясніть призначення та принципи роботи алгоритмів проходження по графу. 4. Наведіть типи графів та порівняйте їх. 5. Назвіть структури даних, що використовуються в алгоритмах проходження вглиб та вшир. Тести для закріплення матеріалу 1. Назвати компоненти неорграфу: а) дуги; б) ребра; в) шлях; г) контур; д) ланцюг; є) цикл.
2. Назвати компоненти орграфу: а) дуги; б) ребра; в) шлях; г) контур; д) ланцюг; є) цикл.
3. За визначенням знайти термін: орграф заміняється неорієнтованим графом, що у свою чергу є зв'язним: а) слабка зв'язність; б) однобічна зв'язність; в) сильна зв'язність.
4. За визначенням знайти термін: між двома вершинами існує шлях в одну або в іншу сторону: а) слабка зв'язність; б) однобічна зв'язність; в) сильна зв'язність.
5. За визначенням знайти термін: між будь-якими двома вершинами існує шлях в одну й в іншу сторону: а) слабка зв'язність; б) однобічна зв'язність; в) сильна зв'язність.
6. Способи подання графу: а) графічний; б) матричний; в) описовий; г) перелічуваний.
7. Знайти правильний вислів: а) будь-яке дерево є графом; б) будь-який граф є деревом; в) будь-яке двійкове дерево є графом; г) для того, щоб граф був деревом, в ньому не має бути циклів.
ЛЕКЦІЯ № 5
Тема: Алгоритми проходження графу
Ціль: розглянути алгоритми проходження графів та їх застосування
План
Алгоритм проходження графу вглиб Алгоритм проходження графу вшир
Алгоритм проходження може бути використаний як алгоритм пошуку, якщо вузлами графу є елементи таблиці. Маємо граф G = (X,U), X={x1,x2,...,xn}... Кожне проходження можна розглядати як певну послідовність. Максимальна кількість проходжень (перестановок) – n!.   ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
означає, що завжди є шлях між цими вузлами довжиною 2, якщо вираз є істинним.
– матриця зв'язності. Визначає, чи існує якийнебудь шлях між вузлами i та j.
виконати:
виконати: С(х) = С(х) + 1;