На головну

Способи представлення графів

  1. Будова та способи збудження
  2. Види інформації та способи її кодування
  3. Видобування: код родовища, дата представлення даних, видобуток нафти за добу.
  4. Використання операцій інтервального представлення
  5. Двійкова алгебра. Форми представлення чисел в ПК
  6. Джерела формування активів фінансових установ та способи забезпечення їх оптимальної структури
  7. Запаси: код родовища, видобувні запаси, дата представлення даних.

Перший конструктивний спосіб, як відзначалося, - завдання графу G у вигляді двійки G=<X, Г>. За допомогою цього способу не можна задати мультиграф і псевдограф.

Більш складний аналітичний спосіб завдання відзначених графів у вигляді трійки G=<X, V, D>, де D - відношення, що задається у свою чергу трійкою DÍX´V´X, таке, що для "<xi, vj, xk>ÎD випливає, що дуга vjÎ V, з'єднує вершини xi і xk. Трійкою G=<X, V, D> можна задати і мультиграф, і псевдограф.

Інший основний спосіб - завдання графу G за допомогою матриці. У матриці суміжності графу G рядка і стовпці відповідають вершинам графу, а елемент (клітка) матриці uij, що відповідає стовпцю xi і xj рядку, дорівнює числу кратних ребер, що зв'язують вершину xi з вершиною xj чи, для орграфу, числу дуг, спрямованих з вершини xi у вершину xj.

Приклад. Орієнтований граф, заданий матрицею суміжності і графічно

 
 

Таблиця 14.1

Рис.14.9. Орієнтований псевдограф G =<X, V>, X = {x1, x2, x3, x4, x5},
V = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}

Очевидно, що для будь-якого орграфу на його матриці суміжності справедливо:

n n

" xi(s(xi) = åuij; p(xi) = åuji; G(xi) = s(xi) + p(xi))

j=1 j=1

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

 
 

Приклад. Неорієнтований граф, заданий матрицею суміжності і графічно

Таблиця 14.2

Рис. 14.10. Неорієнтований псевдограф : G =<X, V>,
X = {x1, x2, x3, x4, x5}, V = {v1, v2, v3, v4, v5, v6}

Для неорієнтованого графу матриця суміжності симетрична.

Петля в матриці суміжності неорієнтованого графу вважається один раз, тоді для матриця суміжності будь-якого неорієнтованого графу справедливо:

n n

" xi( '$ vj = <xi, xi> ® G(xi) = å uik і G(xi) = å uik),

k=1 k=1

n n

" xi ( $ vj = <xi, xi> ® G(xi) = (å uik) + 1 і G(xi) = 1+ å uik).

k=1 k=1

Якщо вершина є кінцем ребра, то говорять, що вершина інцидентна ребру, а ребро інцидентно вершині, чи вони інцидентні. Для орграфов розрізняють позитивну інцидентність, коли дуга виходить з вершини, і негативну інцидентність, коли дуга заходить у вершину.

Граф G можна задати матрицею інцидентності, стовпці якої відповідають ребрам (дугам) графу, а рядки - вершинам графу. Для неорієнтованого графу на перетинанні i-го рядка, що відповідає вершині xi, і j-го стовпця, що відповідає ребру vj, ставиться одиниця, якщо
вершина xi інцидентна ребру vj. Для орграфу на перетинанні i-го рядка і
j-го стовпця ставиться "+1", якщо дуга vj виходить з вершини
xi, і ставиться "-1", якщо дуга vj заходить у вершину xi. Кожен стовпець містить два елементи. Петлі зіставляють порожній стовпець, тоді матриця інцидентності задає графу без зазначення вершин, з якіми зв'язані петлі. Ця обстава вимагає спеціальних міток.

 
 

Приклад. Неорієнтований граф і його матриця інцидентності

Таблиця 14.3

Рис. 14.11. Неорієнтований псевдограф G =<X, V>,
X = {x1, x2, x3, x4, x5}, V = {v1, v2, v3, v4, v5, v6}

Для будь-якого неорієнтованого графу без петель і його матриці інцидентності справедливо:

m

" xi (G(xi) = å uij), де m = êVê.

j=1

Приклад. Орграф, заданий графічно і матрицею інцидентності

 
 

Таблиця 14.4

Рис. 14.12. Орієнтований псевдограф G =<X, V>, X = {x1, x2, x3, x4, x5},
V = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}

Для будь-якого орієнтованого графу без петель і його матриці інцидентності справедливо:

m m m

" xi(s(xi) = å uji (+1); p(xi) = å uji(-1); G(xi) = s(xi) + p(xi) = å êuji ê,

j=1 j=1 j=1

де uji(-1) Î{+1;0}, uji(-1) Î{-1;0}.

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

Рис. 14.13. Ізоморфні графи

Принципово можливо в матриці інцидентності визначити також і петлі графу чи орграфу - у цьому випадку для неорієнтованого графу на перетинанні i-го рядка, що відповідає вершині xi, і j-го стовпця, що відповідає ребру-петлі vj, ставиться двійка, для орграфу на перетинанні
i-го рядка і j-го стовпця необхідно, наприклад, вказати одночасно як +1, так і -1.

Для модифікованої в такий спосіб матриці інцидентності справедливі усі твердження, що стосуються звичайної матриці інцидентності.

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

1. Як за допомогою двійок визначається граф, чи є таке визначення конструктивним, що дає можливість побудувати граф?

2. Що є неорієнтованим і орієнтованим графами?

3. Що є ребром, дугою, петлею, рівнобіжними ребрами, строго і нестрого рівнобіжними дугами?

4. Що є ступенем, напівступенем заходу і напівступенем виходу?

5. Що є простим графом, мультиграфом та псевдографом?

6. Яка різниця між порожнім і повним графом?

7. Що є біграфом або двочастковим графом, що є регулярним графом r-го ступеня?

8. Що декларують суміжність та інцидентність, що є позитивною та негативною інцидентністю?

9. Як визначити граф за допомогою трійки, чи є таке завдання конструктивним?

10. Які графи є ізоморфними?



  18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   Наступна

Перестановки | Сполучення | Рекурентні співвідношення | Біном Ньютона | Список літератури | Поліноміальні твірні функції | Експонентні твірні функції | Принцип включення і виключення | Розбивки | Зважені (відзначені) графи |

© um.co.ua - учбові матеріали та реферати