Інформатика – Поглиблений рівень

Виконати вправу

Прочитайте!

Існують декілька способів подання графів у комп’ютері, розглянемо два з них: за допомогою матриць суміжності; за
допомогою списку суміжних вершин. Подання графів за допомогою матриць суміжності. Матриця суміжності для графу з n вершинами подається двовимірним масивом розмірністю n*n.
Якщо вершина i неорієнтованого незваженого графу має ребро з вершиною j, то елемент масиву mas[i, j] набуває значення 1, інакше — 0. Розробимо матрицю суміжності для неорієнтованого графу, зображеного на рис. 8.10.

Матрицю суміжності для неорієнтованого незваженого графу наведено на рис. 8.11.

Для орієнтованого незваженого графу елементи матриці суміжності набувають значення 1, якщо відповідне ребро виходить з вершини, інакше — значення 0. На рис. 8.12 ребро виходить із вершини 1 у вершини 2 і 3, тому елементи mas[1, 2] і mas[1, 3] набувають значення 1, а елемент mas[2, 1] — значення 0. Матрицю суміжності для орієнтованого незваженого графу (див. рис. 8.12) наведено на рис. 8.13.

Розглянемо подання орієнтованого зваженого графу (рис. 8.14). Матрицю суміжності для цього графу наведено
в таблиці на рис. 8.15. Як бачимо, елементи матриці набувають значень ваги відповідних ребер.

Подання графів за допомогою списку суміжних вершин. Для кожної вершини складається список суміжних вершин.
Наприклад, для графу (див. рис. 8.12) список суміжних вершин можна записати так:

Для зваженого графу біля суміжної вершини вказується вага ребра. Наприклад, для графу (див. рис. 8.14) список
можна записати так:

Виконання практичного завдання

Завдання 1. Складіть матрицю суміжності для графу, зображеного на: а) рис. 8.4; б) рис. 8.6; в) рис. 8.8.; г) рис. 8.9.

Завдання 2. Знайдіть в Інтернеті відомості про населені пункти, розташовані у вашій області,  кількістю населення понад 30 000 осіб і довжину автомобільних шляхів між ними. Розробіть граф автомобільних шляхів між
цими населеними пунктами та список суміжних вершин.