Короткі теоретичні відомості

Теорія графів.

Лабораторна робота №1.

Тема. Створення моделі графу за допомогою матриці суміжностей.

Мета. Використовуючи довільну мову програмування, побудувати модель графу через матрицю суміжностей згідно завдання.

Короткі теоретичні відомості.

Граф складається зі скінченної множини вершин та скінченної множини ребер . Кожне ребро визначається парою вершин , які воно з’єднує. В графічному зображенні графа вершини подаються точками, а ребра – лініями, що з’єднують вершини.

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

Кажуть, що вершина інцидентна ребру, якщо вона є кінцевою вершиною цього ребра. Дві кінцеві вершини ребра становлять пару суміжних вершин.

Граф називають орієнтованим (орграфом), якщо пара вершин кожного ребра впорядкована. Ребра орграфу позначаються графічно дугою зі стрілкою.

Для опису простого графу зручно використовувати матрицю суміжностей. Це квадратна матриця, розміром , де п – кількість вершин графу . при чому, кожен елемент цієї матриці рівний Іншими словами, елемент матриці рівний одиниці, коли вершини суміжні; в противному випадку елемент матриці рівний нулю.

Очевидно, що для неорієнтованого графа матриця суміжностей буде симетричною, а для орієнтованого – несиметричною.

Вказівки до ходу виконання роботи.

Для моделювання графу за допомогою матриці суміжностей скористатись засобами довільної мови програмування. З метою раціонального використання обчислювальних ресурсів комп’ютера (оперативна пам’ять, час виконання програми) для матирці суміжностей бажано використати не двомірний масив логічних величин, а одномірний масив натуральних чисел. Порядковий номер числа у масиві означатиме номер рядка матриці суміжностей, а кожен біт двійкового представлення кожного елементу масиву – відповідний стовбець матриці суміжностей.

Тоді операції добавлення/видалення ребра зводяться до встановлення/скидання відповідного біту потрібного елементу матриці.

З врахуванням можливості програми змінювати кількість вершин графу замість масиву доцільно використати один з динамічних типів даних лінійної структури (зв’язаний список, вектор і т.п.).

Використовуючи об’єктно-орієнтований підхід до поставленої задачі, можна створити новий клас (або тип даних у загальній термінології) з наступними членами: 1 – цілочисельного беззнакового типу для зберігання кількості вершин графу; 2 – одна з лінійних структур (масив, список, вектор) для зберігання натуральних чисел, кожне з яких відповідає за свій рядок матриці суміжностей; 3 – метод добавлення нового ребра між несуміжними вершинами, 4 – метод витирання існуючого ребра між суміжними вершинами. Конструктор класу повинен створювати граф, множина ребер якого порожня.