![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Перший конструктивний спосіб, як відзначалося, - завдання графу 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.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.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. Які графи є ізоморфними?
Дата публикования: 2014-11-18; Прочитано: 1945 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!