лише з точністю до ізоморфізму, кажуть: абстрактний граф .
Іноді розглянуте вище поняття граф виявляється недостатнім і доводиться розглядати більш загальні об'єкти, в яких дві вершини можуть з'єднуватися більш ніж одним ребром. Так виникає поняття мультіграф raquo ;. Мультіграф - це пара (V, E), де V- непорожнє безліч (вершин), а E- сімейство підмножин множини V (2) (ребер). Вживання терміну сімейство замість безліч означає, що елементи множини V (2) можуть у E повторюватися, тобто допускаються кратні ребра.
Подальше узагальнення полягає в тому, що крім кратних ребер допускаються ще петлі, тобто ребра, що сполучає вершину саму з собою. Псевдографів - це пара (V, E), де V- непорожнє безліч (вершин), а E- деяке сімейство невпорядкованих пар (ребер), не обов'язково різних.
Вивчаються також орієнтовані графи. Тоді безліч V (2) замінюється декартовим квадратом V 2, що складається з впорядкованих пар елементів множини V. Орієнтований граф (або орграф) - це пара (V, A), де V- безліч вершин, A- безліч орієнтованих ребер, які називаються дугами , AV 2.
Якщо a=(v1, v2) - дуга, то вершини v1 і v2 називаються її початком і кінцем відповідно.
Аналогічно неорієнтована визначається орієнтований мультіграф. Розглядаються також змішані графи, у яких є і дуги, інеоріентірованние ребра. Замінюючи кожну пару (u, v) з безлічі E, орієнтованого (або змішаного) графа G невпорядкованою парою {u, v}, що складається з тих же елементів uі v, отримуємо асоційований з G=(V, E) графом псевдографів H=( V, E 0). Також кажуть, що граф H є підстава графа G.
Орграф називається турніром, якщо його підстава є повним графом.
Для всіх розглянутих узагальнень поняття граф аналогічно вводиться поняття ізоморфізму як Бієкція між множинами вершин, що зберігає суміжність, кратності ребер, петлі та напрямки дуг.
Нехай G - граф, w: EG? R + вещественнозначная функція, яка ставить у відповідність кожному ребру e невід'ємне число w (e) - вага ребра e. Пару (G, w) назвемо зваженим графом. Під вагою будь-якого подграфа (можливо, невласного) зваженого графа будемо розуміти суму ваг його ребер.
. Матричне подання графів
Нехай G -помеченний граф порядку n, VG={1, 2, ..., n}. Визначимо бінарну n? n-матрицю A=A (G), поклавши
A (G) називається матрицею суміжності графа G. Це симетрична матриця з нулями на діагоналі. Число одиниць в рядку дорівнює ступеню відповідної вершини.
Очевидно, що відповідність G? A (G) визначає біекція безлічі помічених графів порядку n на безліч бінарних симетричних n? n-матриць з нульовою діагоналлю.
Аналогічно визначаються матриці суміжності A мульти- і псевдографів: ik дорівнює числу ребер, що з'єднують вершини i і k (при цьому петля означає два ребра).
Також визначається матриця суміжності A (G) орієнтованого графа.
Очевидно, що якщо A (G) - матриця суміжності орграфа G порядку n, то
т.е. число одиниць у i-му рядку матриці A (G) одно полустепені результату i-й вершини, а число одиниць у k-му стовпці одно полустепені заходу k-й вершини.
Теорема. Графи ізоморфні тоді і тільки тоді, коли їх матриці суміжності виходять один з одного однаковими перестановками рядків і стовпців.
Теорема вірна також для мультиграфом, псевдографів і орграфів.
Нехай G - (n, m) -граф, VG={1, 2, ..., n} EG={e1, e2, ..., em}. Визначимо бінарну n? m-матрицю I=I (G) умовами
Матриця I називається матрицею інцидентності графа G. У кожному її стовпці рівно дві одиниці, рівних стовпців немає. Як і вище, відповідність G? I (G) є біекція безлічі помічених (n, m) -графов з занумерован ребрами на безліч n? m-матриць, що задовольняють описаним умовам.
Матриця інцидентності 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).
3) Нехай G- орієнтований мультіграф з н...
