, яка, як можна показати, пропорційна числу дуг орієнтованого графа. Таким чином, складність алгоритму пошуку «оточення» становить, тобто пошук займає час порядку твори числа вершин на число дуг.
Більш ефективною матричної структурою, що представляє граф, служить матриця суміжності вершин , або булева матриця графа. Це квадратна матриця В порядку n , елементи якої визначають наступним чином:
для неориентированного графа:
для орієнтованого графа:
Для зображеного нижче графа ( Рис. 2.2 а ) матрицею інціденцій буде матриця, представлена ??на ( Рис. 2.2 б).
Рис. 2.2 а
Матриця розрізів.
Розглянемо орграф. Якщо - непорожнє підмножина множини, то множина дуг, що з'єднують вершини, є розрізом, що позначається. Орієнтацію можна прийняти як від вершини до вершини, так і навпаки. Припустимо, ми приймаємо орієнтацію від вершини до вершини. Тоді кажуть, що орієнтація дуги з відповідає орієнтації розрізу, якщо дуга орієнтована від вершини з в вершину з.
Матриця розрізів графа з m ребрами має m стовпців і стільки рядків, скільки в цьому графі мається розрізів. Елемент визначається наступним чином.
Якщо граф орієнтований,
Якщо граф неорієнтований,
Рядки матриці називаються векторами розрізів.
цикломатическая матриця
Цикл в графі можна обійти в одному з двох напрямків: по або проти годинникової стрілки. Напрямок, обиране для обходу циклу, визначає його орієнтацію.
Розглянемо дугу e з кінцевими вершинами до і входить в цикл C. Говоритимемо, що орієнтація дуги e відповідає орієнтації циклу, якщо вершина зустрічається при обході циклу C в напрямку, вказаному його орієнтацією, раніше вершини. цикломатическая матриця графа G з m ребрами має m і стільки рядків, скільки циклів мається на графі G . Елемент визначається наступним чином:
Якщо граф орієнтований,
Якщо граф неорієнтований,
Матриця Кирхгофа
Дан простий граф з вершинами. Тоді матриця Кирхгофа даного графа буде визначатися таким чином:
Також матрицю Кірхгофа можна визначити як різницю матриць
де - це матриця суміжності даного графа, а - матриця, на головній діагоналі якої ступеня вершин графа, а інші елементи - нулі:
Якщо граф є зваженим, то визначення матриці Кирхгофа узагальнюється. У цьому випадку елементами головної діагоналі матриці Кирхгофа будуть суми ваг ребер, інцидентних відповідної вершині. Для суміжних (зв'язаних) вершин, де - це вага (провідність) ребра. Для різних несуміжних (незв'язаних) вершин годиться.
Для зваженого графа матриця суміжності записується з урахуванням проводимостей ребер, а на головній діагоналі матриці будуть суми провідностей ребер інцидентних відповідним вершинам.
Приклад матриці Кірхгофа.
4. Спеціальні властивості графів
Нехай G - довільний
