3.5. Задання графа за допомогою списку.
Відношення інцидентності
можна задати у вигляді списку ребер.
Такий список зручно оформити у вигляді
таблиці, яка має
-
рядків (кількість ребер або дуг), в
кожному із яких записані номера вершин
інцидент них ребру або дузі. Для ребер
список вершин в принципі може бути
довільним, а для дуг першою в списку
повинна йти вершина, яка є її початком,
а другою – вершина, яка є кінцем дуги.
Ребро |
Вершина |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ребро |
Вершина |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.6 Задання графа за допомогою матриці суміжності.
Матриця суміжності, це
квадратна матриця
розміром
(
-
кількість вершин графа), елементи якої
величини
,
,
,
де
Для неорієнтованого графа
,
тобто матриця суміжності – симетрична
матриця.
Для орієнтованого графа
.Для
орієнтованого графа
в тому випадку коли дуга починається в
-ті
і закінчується в
-тій
вершині. Складемо матриці суміжності
для розглянутих вище прикладів.
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Таблиці суміжності .
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
Для неорієнтованого графа
і всі його ребра визначаються верхньою
трикутною підматрицею матриці E.
Причому кількість ребер дорівнює
,
де
-всі
елементи трикутної підматриці E.
Для орієнтованого графа – кількість
ребер дорівнює
,
де
- всі елементи матриці E.