Граф - це складна нелінійна багатозв’язна динамічна структура, що відображає властивості і зв'язки складного об'єкта і має наступні властивості:
- на кожен елемент (вузол, вершину) може бути довільна кількість посилань;
- кожен елемент може мати зв'язок з будь-якою кількістю інших елементів;
- кожне зв'язування (ребро, дуга) може мати напрямок і вагу.
У вузлах графа утримується інформація про елементи об'єкта. Зв'язки між вузлами задаються ребрами графа. Ребра можуть мати спрямованість, показувану стрілками, тоді вони називаються орієнтованими. Коли ребра без стрілок - неорієнтовані. Граф, усі зв'язки якого орієнтовані, називається орієнтованимграфом або орграфом; граф із усіма неорієнтованими зв'язками - неорієнтованим графом; граф зі зв'язками обох типів - змішаним графом. Позначення зв'язків: неорієнтованих - (A,B), орієнтованих - <A,B>.
Приклади зображень графів дані на рис.7.5. Скобкове представлення графів: а). (<A,B>,<B,A>) та б). ((A,B),(B,A)).
Рис.7.5. Зображення графа
а) – орієнтований,
б) - неорієнтований
Для орієнтованого графа число ребер, що входять у вузол, називається напівступенем заходу вузла, що виходять з вузла - ступенем виходу. Кількість вхідних і вихідних ребер може бути будь-яким, у тому числі і нульовим. Граф без ребер є нуль-графом. Якщо ребрам графа відповідають деякі значення, то граф і ребра називаються зваженими. Мультиграфом називається граф, що має паралельні ребра (що з'єднують ті самі вершини), у противному випадку граф називається простим.
Шлях у графі - це послідовність вузлів, зв'язаних ребрами. Елементарним називається шлях, у якому всі ребра різні, простим називається шлях, у якому усі вершини різні. Шлях від вузла до самого себе називається циклом, а граф, що містить такі шляхи - циклічним. Два вузли графа суміжні, якщо існує шлях від одного з них до іншого. Вузол називається інцидентним до ребра, якщо він є його вершиною, тобто ребро спрямоване до цього вузла. Логічно структура графа може бути представлена матрицею суміжності або матрицею інцидентності.
Матрицею суміжності для n вузлів називається квадратна матриця adj порядку n. Елемент матриці a(i,j) дорівнює 1, якщо вузол j суміжний з вузлом i (є шлях <i,j>), і 0 - у противному випадку. Якщо граф неорієнтований, то a(і,j)=a(j,і), як наслідок, матриця суміжності буде симетрична щодо головної діагоналі.
Матриці суміжності використовуються при побудові матриць шляхів, що дають представлення про граф по довжині шляху: шлях довжиною в 1 - суміжну ділянку <A,B>, шлях довжиною 2 - (<A,B>,<B,C>), ... у n суміжних ділянок: де n - максимальна довжина, що дорівнює числу вузлів графа.
На рис. 7.7 дані шляхові матриці шляху adj1, adj2, adj3, adj4 для графа рис. 7.6.
Рис.7.6. Граф
(A)(B)(C)(D) | (A)(B)(C)(D) | (A)(B)(C)(D) | (A)(B)(C)(D) | ||||
(A) (B) (C) (D) | 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 | (A) (B) (C) (D) | 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 | (A) (B) (C) (D) | 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 | (A) (B) (C) (D) | 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 |
adj1 adj2 adj3 adj4
Рис.7.7. Матриці шляхів
На рис. 7.8 показана матриця інцидентності для графа рис. 7.5.
Вузли/номера зв'язків 1 2
A B -
B C D
C D -
D A C
Рис.7.8. Матриця інцидентності
Матриці інцидентності використовуються тільки для орграфів. У кожнім рядку записується упорядкована послідовність імен вузлів, з якими даний вузол зв'язаний ориєнтованими (вихідними) ребрами.