Ноу Інти, лекція, графи уявлення, досяжність і зв'язність

Матриця (таблиця) суміжності

Визначення 9.5. Матрицею суміжності орієнтованого (або неориентированного) графа G = (V, E) з n вершин і V = називається булева матриця AG розміру n x n з елементами

Матриця (таблиця) инцидентности

Визначення 9.6. Матрицею інцидентності орієнтованого (або неориентированного) графа G = (V, E) з n вершин і V = і m ребрами E = 1. em> називається матриця BG розміру n x m з елементами

списки суміжності

Визначення 9.7. Нехай G = (V, E) - орієнтований граф. v - вершина з V. Список суміжності Lv для вершини v включає всі суміжні з нею вершини. тобто

Подання графа G = (V, E) c n вершин і V = за допомогою списків суміжності складається з списків суміжності всіх вершин: Lv1. Lv2. Lvn.

Розмір цього подання порівняємо з сумою числа вершин і ребер графа. Воно дозволяє легко переходити по ребрах від вершини до її сусідам. У програмах списки суміжності представляються списковим структурами. які легко реалізуються у всіх мовах програмування.

Приклад 9.1. Розглянемо наступний граф G = (V, E):