Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Поняття графу

Поняття графу

План

 

2 Подання графу в пам'яті комп'ютера

 

Граф – двійка G = (X, U), де X - множина елементів (вершин, вузлів), а U - бінарне відношення на множині X (U X x X). Якщо |Х| = n, то граф є скінченим. Елементи U називають або дугами, або ребрами.

 

 

 

Якщо (Xi, Xj) – впорядкована пара, то такий граф називається орієнтованим(орграфом) а елементи U називаються дугами.

Якщо (Xi, Xj) = (Xj, Xi) то граф – неорієнтований (неорграф), а елементи U називаються ребрами.

F: U → R – якщо задано таку функцію, то граф є зваженим, де R – множина дійсних чисел, тобто відображення дуги на число.

Загалом:Ø U ⊆ X x X.

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

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

Компонентами орграфу є: дуга, шлях, контур.

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

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

Компонентами неорграфу є, відповідно: ребро, ланцюг, цикл.

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

 

 

 

Слабка зв'язність – орграф замінюється неорієнтованим графом, який, у свою чергу, є зв'язним.

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

Сильна зв'язність – це зв'язність, коли між будь-якими двома вершинами існує шлях в одну й в іншу сторону.

Отже, багатозв'язна структура має такі властивості:

1) на кожен елемент (вузол, вершину) може бути довільна кількість посилань;

2) кожен елемент може мати зв'язок з будь-якою кількістю інших елементів;

3) кожна зв'язка (ребро, дута) може мати напрямок і вагу.

Дерево - зв'язний граф без циклів.

Ліс (або ациклічний граф) – неограф без циклів (може бути і незв'язним).

Контур (каркас) зв'язного графу - дерево, що містить всі вершини графу. Визначається неоднозначно.

Редукція графу – контур з найбільшим числом ребер.

Цикломатичне (або циклічний ранг) число графу S=m-n+c, де n – кількість вершин, m – кількість ребер, с – кількість компонент зв'язності графу.

Коциклічний ранґ (або коранґ) S*=n-c.

Неограф G є лісом тоді і тільки тоді, коли S(G)=0.

Неограф G має єдиний цикл тоді і тільки тоді, коли S(G)=1.

Контур неографу має S* ребер.

Ребра графа, що не входять в контур, називаються хордами.

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

 

2 Подання графу в пам'яті комп'ютера

 

Графічний спосіб подання (якщо граф невеликий).

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

Одним із матричних способів подання графу є матриця суміжності. Нехай задано граф G = (X, U), |Х| = n. Маємо матрицю А розмірності n х n, що називається матрицею суміжності, якщо елементи її визначаються так:

 

 

 

Приклад 7.1. Нехай маємо граф, поданий рисунку 9.

 

 

 

Рисунок 9 – Приклад графу.

 

Йому відповідає така матриця суміжності:

 

  A B C D E
A
B
C
D
E

 

 

Розглянемо застосування матричної алгебри для визначення характеристик графу. Вираз aikLakj означає, що між вузлами i і j є дві дуги, що проходять через вузол k, якщо значення виразу дорівнює True.

Вираз означає, що завжди є шлях між цими вузлами довжиною 2, якщо вираз є істинним.

A L A = А(2) – логічні операції заміняються арифметичними. Тоді кожний елемент аij буде подавати інформацію про те, чи є шлях з i в j (i,j = 1, 2,...,n)...

Вираз А(n) = А(n-1) L А означає, чи є шлях довжиною n між різними вузлами і. По діагоналі буде характеристика, чи є цикли (контури) у матриці.

матриця зв'язності. Визначає, чи існує якийнебудь шлях між вузлами i та j .

Алгоритм обчислення заданого виразу:

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;

виконати: С(х) = С(х) + 1;

S = S + С(х);

кінець;

 

Контрольні питання

 

1. Дайте визначення графу.

2. Дайте визначення дерева за допомогою графу.

3. Поясніть призначення та принципи роботи алгоритмів проходження по графу.

4. Наведіть типи графів та порівняйте їх.

5. Назвіть структури даних, що використовуються в алгоритмах проходження вглиб та вшир.

Тести для закріплення матеріалу

1. Назвати компоненти неорграфу:

а) дуги;

б) ребра;

в) шлях;

г) контур;

д) ланцюг;

є) цикл.

 

2. Назвати компоненти орграфу:

а) дуги;

б) ребра;

в) шлях;

г) контур;

д) ланцюг;

є) цикл.

 

3. За визначенням знайти термін: орграф заміняється неорієнтованим графом, що у свою чергу є зв'язним:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

 

4. За визначенням знайти термін: між двома вершинами існує шлях в одну або в іншу сторону:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

 

5. За визначенням знайти термін: між будь-якими двома вершинами

існує шлях в одну й в іншу сторону:

а) слабка зв'язність;

б) однобічна зв'язність;

в) сильна зв'язність.

 

6. Способи подання графу:

а) графічний;

б) матричний;

в) описовий;

г) перелічуваний.

 

7. Знайти правильний вислів:

а) будь-яке дерево є графом;

б) будь-який граф є деревом;

в) будь-яке двійкове дерево є графом;

г) для того, щоб граф був деревом, в ньому не має бути циклів.

 

 


 

ЛЕКЦІЯ № 5

 

Тема: Алгоритми проходження графу

 

Ціль: розглянути алгоритми проходження графів та їх застосування

 


Читайте також:

  1. I. Доповнення до параграфу про точкову оцінку параметрів розподілу
  2. II. Поняття соціального процесу.
  3. V. Поняття та ознаки (характеристики) злочинності
  4. А/. Поняття про судовий процес.
  5. Адміністративний проступок: поняття, ознаки, види.
  6. Адміністративні провадження: поняття, класифікація, стадії
  7. Акти застосування юридичних норм: поняття, ознаки, види.
  8. Алгоритм проходження графу вглиб
  9. Аналіз ступеня вільності механізму. Наведемо визначення механізму, враховуючи нові поняття.
  10. АРХІВНЕ ОПИСУВАННЯ: ПОНЯТТЯ, ВИДИ, ПРИНЦИПИ І МЕТОДИ
  11. Аудиторські докази: поняття та процедури отримання
  12. Базове поняття земле оціночної діяльності.




Переглядів: 2138

<== попередня сторінка | наступна сторінка ==>
Поняття структури даних | Алгоритм проходження графу вглиб

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.018 сек.