- Способи опису графів Теоретико-множинне уявлення графів
- Завдання графів відповідністю
- Матричне подання графів
Способи опису графів Теоретико-множинне уявлення графів
Граф описується перерахуванням безлічі вершин і дуг. Приклади опису наведені для орграфов на Мал. 1.3 і Мал. 1.4 .
G4 = (Х, А),
де Х = {хi}, i = 1, 2, 3, 4 - безліч вершин; А = {ai}, i = 1, 2, ..., 6 - безліч дуг, причому А = {(х1, х2), (х4, х2), (х2, х4), (х2, х3), ( х3, х3), (х4, х1)}.
G5 = (X, A),
де X = {B, C, D, E, F} - безліч вершин графа, A = {ai}, i = 1, 2, ..., 5 - безліч дуг графа, причому a1 = (F, B), a2 = (F, D), a3 = (B, E), a4 = (E, C), a5 = (C, D).
Завдання графів відповідністю
Опис графів полягає в завданні безлічі вершин Х і відповідності Г, яке показує, як між собою пов'язані вершини.
Відповідністю Г називається відображення безлічі Х в Х, а граф в цьому випадку позначається парою G = (X, Г).
Відображенням вершини хi - Г (хi) є безліч вершин, в які існують дуги з вершини хi, т. Е. 
.
Так для орграфа на Мал. 1.3 опис завданням безлічі вершин і відповідності виглядає наступним чином:
G4 = (X, Г),
де X = {хi}, i = 1, 2, ..., 4 - безліч вершин, Г (х1) = {х2}, Г (х2) = {х3, х4}, Г (х3) = {х3} , Г (х4) = {х1, х2} - відображення.
Для неорієнтованого або змішаного графів передбачається, що відповідність Г задає такий еквівалентний орієнтований граф, який виходить з вихідного графа заміною кожного неориентированного ребра двома протилежно спрямованими дугами, що з'єднують ті ж самі вершини. Наприклад, для графа на Мал. 1.2 , Б Г (х2) = {х1, х3, х5}, Г (х4) = {х3, х5} і т. Д.
Матричне подання графів
Для обробки на ЕОМ графи зручно представляти у вигляді матриць суміжності і інціденцій.
Матриця суміжності - це квадратна матриця розмірністю nxn, (де n - число вершин графа), однозначно представляє його структуру.
A = {aij}, i, j = 1, 2, ..., n, а кожен елемент матриці визначається наступним чином:
aij = 1, якщо 
дуга (хi, хj),
aij = 0, якщо немає дуги (хi, хj).
Якщо елемент на діагоналі (i = j) дорівнює одиниці, означає, вершина i має петлю.
Матриця інціденцій являє собою прямокутну матрицю розміром nxm, де n - кількість вершин графа, а m - кількість дуг графа. Позначається матриця інціденцій B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m.
Кожен елемент матриці визначається наступним чином:
bij = 1, якщо хi є початковою вершиною дуги aj,
bij = -1, якщо хi є кінцевою вершиною дуги aj,
bij = 0, якщо хi не є кінцевою вершиною дуги aj або якщо aj є петлею.
Таким чином, нульовий стовпець j в матриці інціденцій свідчить про те, що дуга aj яляется петлею.
на Мал. 1.5 , А, б наведено граф і його матриця суміжності, по якій можна знайти характеристики вершин. Так сума елементів i -ої рядки матриці дає полустепені результату вершини хi, а сума елементів i-го стовпця дає полустепені заходу вершини хi. По матриці суміжності можна знайти прямі і зворотні відображення. Розглянемо i -ю рядок матриці. Якщо елемент aij = 1, то елемент графа хj входить в відображення Г (хi). Наприклад, у 2-му рядку матриці А ( Мал. 1.5 , Б) одиниці стоять в 2-м і 5-м шпальтах, отже, Г (х2) = {х2, х5}.
Мал.1.5.
Орграф і його матричне уявлення: а - орграф; б - матриця суміжності; в - матриця інціденцій
Для графа на Мал. 1.5 , А матриця інціденцій приведена на Мал. 1.5 , В. Оскільки кожна дуга инцидентна двом різним вершин, за винятком того випадку, коли дуга утворює петлю, то кожен стовпець або містить один елемент рівний 1 і один - рівний - 1, або всі елементи стовпця дорівнюють 0.
Для неорієнтованого графа, матриця інціденцій визначається так само, за винятком того, що всі елементи, рівні -1, замінюються на 1.