ваний граф G = (V, E) визначає відношення на V.
б) Нехай V - к-нечное безліч. Тоді відношення на V визначає орієнтований граф, у якого безліч вершин - V-
Доказ.
а) Як і у випадку неорієнтованих графів, визначимо R (E) таким чином: vR (E) w тоді і тільки тоді, коли (v, w) in E. Очевидно, що R (E) - про-носіння. p> б) Якщо R - про-носіння на V, то орієнтований граф G = (V, E), який визначається R, має безліч дуг Е, де (v, w) in E тоді і тільки тоді, коли vRw.
Напрямок дуги позначають порядком у V * V, якщо (v, w) in E, то говорять, що дуга виходить з v і входить до w. На діаграмі в цьому випадку для вказівки напряму використовують стрілки.
Матрицю суміжності A для орграфа визначимо наступним чином:
Aij = 1, якщо дуга (vi, vj) in E, 0 в іншому випадку.
# # # Нехай G = ({v1, v2, v3}, {(v1, v2), (v2, v3), (v3, v1)}). Тоді матриця суміжності і зображення орграфа мають вигляд:
|/--------> +
1 січня -1 + <--------- v1 <-------- + |
0 0 1 | |/
1 0 0 v2 -------------------> v3
Оскільки реберне ставлення для орграфа не обов'язково Нерефлексівное або симетрично, те взагалі кажучи, не обов'язково, щоб А = А ^ T або Aii = 0. Дуги типу (v, v) називають петлею. p> СТУПІНЬ ВЕРШИНИ v in V, може бути записана у вигляді суми
delta (v) = delta + (v) + delta-(v),
де delta + (v) - чис-о дуг, що виходять з v (полустепені результату);
delta-(v) - чис-о дуг, що входять до v (полустепені заходу);
Для орграфов справедливо твердження:
Сума полустепені результату всіх вершин орграфа дорівнює сумі полустепені заходу і дорівнює числу його дуг:
SUM delta + (v) = SUM delta-(v) = | E |.
v in V v in V
Визначимо матрицю інцидентності I орграфа. Нехай G = (V, E) - орг-аф, | V | = n, | E | = m. Якщо перенумерувати деяким чином дуги, то матриця інцидентності - бін-рная n * m матриця виду:
| 1, якщо вершина vk є початком дуги el;
Ikl = | -1, якщо вершина vk є кінцем дуги el;
| 0, якщо вершина vk і дуга el НЕ інцидентні.
орграфов ізоморфні тоді і тільки тоді, коли їх матриці інцидентності виходять один з одного послідовністю однакових перестановок рядків і стовпців.
Нехай G-позначений граф порядку n, VG = {1, 2, ... , N}. Визначимо бінарну n Г— n-матрицю A = A (G), поклавши
пЈ± 1, {i, k} в€€ EG
Aik = пЈІ.
 0, {i, k} ∉ EG
A (G) називається матрицею суміжності графа G. Це симетрична матриця з нулями на діагоналі. Число одиниць у рядку дорівнює ступеня відповідної вершини. Очевидно, що відповідність G в†’ A (G) визначає біекція безлічі помічених графів порядку n на безліч бінарних симетричних n Г— n-матриць з нульовою діагоналлю. Аналогічно визначаються матриці суміжності A мульти-і псевдографів: Aik дорівнює числу ребер, що з'єднують вершини i і k (при цьому петля означає два ребра). Також визначається матриця суміжності A (G) орієнтованого графа.
Очевидно, що якщо A (G) - матриця суміжності орграфа G порядку n, то
n n
ОЈ Aik = d + (i), ОЈA i = 1
k = 1 ik = d - (I),
I.е. число одиниць в i-й рядку матриці A (G) дорівнює полустепені результату i-й вершини, а число одиниць у k-му стовпці одно полустепені заходу k-й вершини.
Теорема. Графи ізоморфні тоді і тільки тоді, коли їх матриці суміжності виходять один з одного однаковими перестановками рядків і стовпців.
Теорема вірна також для мультіграф, псевдографів і орграфов.
Нехай G - (n, m)-граф, VG = {1, 2, ... , N} EG = {e1, e2, ... , Em}. Визначимо бінарну n Г— m-матрицю I = I (G) умовами
пЈ± 1, якщо вершина k і ребро ei інцидентні I ki = пЈІ
пЈі 0, якщо вершина k і ребро ei НЕ інцидентні
Матриця I називається матрицею інцидентності графа G. У кожному її стовпці рівно дві одиниці, рівних стовпців немає. Як і вище, відповідність G в†’ I (G) є біекція безлічі помічених (n, m)-графів з занумерувати ребрами на безліч n Г— m- матриць, що задовольняють описаним умовам.
Матриця інцидентності I для орграфа:
пЈ± 1 - якщо вершина k є початком дуги
I ki = пЈІ -1 - якщо вершина k є кінцем дуги
пЈґ 0 - якщо вершини k і i не суміжні
Теорема. Графи ізоморфні тоді і тільки тоді, коли їх матриці інцидентності виходять один з одного довільними перестановками рядків і стовпців.
Теорема вірна також для мультіграф, псевдографів і орграфов.
Властивості матриць суміжності і інцидентності:
1) Сума елементів матриці A (G), де G = (V, E) - мультіграф, V = {v1, v2, ..., vn}, по i-й рядку (або по i-му стовпцю) дорівнює Оґ (vi).
2) Сума елементів матриці A (G), де G = (V, E) - орієнтований псевдографом,
V = {v1, v2, ... , Vn}, по i-му рядку і по i-му стовпцю відповідно рівні Оґ + (vi), Оґ-(vi...
