Матриця суміжності та матриця інцидентності графа

Для обробки на ЕОМ графи зручно представляти як матриць суміжності і інцидентності.

Подання графа за допомогою квадратної булевої матриці, що відображає суміжність вершин, називається матрицею суміжності, де

Vi	Vj
V1	V2	V3	V4
V1
V2
V3
V4

Матриця суміжності - квадратна матриця порядку n, де n-число вершин.

Хоча формально кожна вершина завжди суміжна сама з собою, у матриці суміжностей ставлять mkk = 0, якщо в неї немає петлі, і mkk = 1, якщо є одна петля. Якщо граф має матрицю суміжності і немає петель, на головній діагоналі в нього завжди стоять нулі. Матриця суміжності неорієнтованого графа є симетричною щодо головної діагоналі.

Матриця інцидентностівідображає інцидентність вершин та ребер.

Це таблиця, що складається з n рядків (вершини) і m стовпців (ребра), в якій:

bij=1, якщо вершина Vi інцидентна ребру Xj

bij=0, якщо вершина Vi не інцидентна ребру Xj

Vi	Xj
X1	X2	X3	X4	Х5
V1
V2
V3
V4

Відстанню між двома вершинами називається мінімальна довжина з усіх можливих шляхів між цими вершинами за умови, що існує хоча б один такий шлях

У таблиці відстаней фіксується відстань між вершинами графа.

Ексцентриситетом вершини vзв'язковому графі G(V,E) називається максимальна відстань від вершини v до інших вершин графа G.

Радіусом графа G називається найменший з ексцентриситетів вершин.

Вершина v називається центральною, якщо її ексцентриситет збігається із радіусом графа.

Дві вершини графа називаються зв'язковими, якщо у графі існує шлях із кінцями у цих вершинах. Якщо такого шляху немає, вершини називаються незв'язними.

Граф називається зв'язковим, якщо будь-яка пара його вершин - зв'язкова. Граф називається нескладним, якщо в ньому є хоча б одна незв'язкова пара вершин.

Граф G можна розбити на безлічі Vi, що не перетинаються, за ознакою зв'язності. Вершини однієї множини є зв'язковими між собою, а вершини різних множин – незв'язні. Тоді всі підграфи Vi (класи еквівалентності) графа G називають зв'язковими компонентами або компонентами зв'язності. Зв'язковий граф має одну компоненту зв'язності.

Цикломатичним числом графа G називається число

де m (G) - Число його ребер; c(G) – кількість зв'язкових компонентів графа; n (G) - Число вершин графа.

---