вершин називається квадратна бінарна матриця
А (G) n x
n , c нулями на діагоналі. Число одиниць в рядку дорівнює ступеня відповідної вершини. p> Матрицею інціденцій орієнтованого графа
G (X, U) називається прямокутна матриця порядку
[m x
n] n - потужність множини
Х, m - потужність множини
U. Кожен елемент якої визначається наступним чином:
1, якщо х i - початок дуги U j
a ij = -1, якщо х i - кінець дуги U j
0, якщо х i - не інцидентна дузі U j
В
Приклад.
Побудуємо матриці суміжності (М1) і інціденцій (М2) для графа G (X, U) (рис 2.1). br/>В
Рис 2.1
Додаткова матриця графа G (X, U) являє собою квадратну матрицю А 1 , яка виходить з матриці суміжності цього графа шляхом заміни всіх нулів одиницями і навпаки.
Дерева і прадеревья
В
Деревом називається неорієнтоване зв'язний граф з числом вершин не менше двох, що не містить петель і циклів. Вершини, інцідентние тільки однієї дузі дерева, називаються висячими. p> Прадрево - орієнтоване дерево.
Корінь прадерева - вершина у якої Р + (х) = 0 .
Глава 2
Максимальні повні підграфи (кліки)
Максимальний повний підграф (Кліка) графа G є породжений підграф, побудований на підмножині S вершин графа і є повним і максимальним в тому сенсі, що будь-який інший подграф графа G , побудований на безлічі вершин H , що містять S , не є повним. Отже, в кліці всі вершини попарно суміжні. Можливо також визначити Клікова число графа (відоме також як густота або щільність) - це максимальне число вершин у кліках даного графа. <В В
Частина 2
Практична реалізація курсового проекту
В
Завдання
У неорієнтованому графі заданому матрицею смежностей виділити кліки. Написати програму виконує це дію.
Рішення
В
Мій алгоритм знаходження клік в графі
В
Нехай заданий неорієнтоване граф G1 матрицею смежностей M1 (рис 3.1)
Рис 3.1
Помічаємо наступне:
1) Що матриця М1 симетрична щодо головної діагоналі, так як вершини неорієнтованого графа попарно суміжні.
2) Якщо виділити кліку з даного графа і представити її у вигляді матриці смежностей то отримаємо матрицю види:
01111 Тоесть теж симетричну відносно головної діагоналі і в верхньому
10111 і нижньому трикутниках її будуть знаходиться 1 а на головній діагоналі 0,
11011 так виходить тому, що всі вершини попарно суміжні (см визна.
11101 кліки.
На осн...
