ершин є тільки по одному шляху. На Рис. 1.3 представлено двійкове дерево .
Двійкове дерево - деревоподібна структура даних, в якій кожен вузол має не більше двох нащадків (дітей). Як правило, перший називається батьківським вузлом , а діти називаються лівим і правим спадкоємцями .
3. Матричне подання графів
Матриця інціденцій.
Розвиток алгоритмічних підходів до аналізу властивостей графів вимагає певних способів опису графів, більш придатних для практичних обчислень, в тому числі з використанням ЕОМ. Розглянемо три найбільш поширених способу представлення графів.
Припустимо, що всі вершини і всі ребра неориентированного графа або всі вершини і всі дуги (включаючи петлі) орієнтованого графа пронумеровані починаючи з одиниці. Граф (неорієнтований або орієнтований) може бути представлений у вигляді матриці типу, де - число вершин, а - число ребер (або дуг). Для неорієнтованого графа елементи цієї матриці задаються таким чином:
Для орієнтованого графа елементи матриці задаються так:
Матрицю типу, певну зазначеним чином, називають матрицею інціденцій.
Приклад отримання матриці інціденцій. Для зображеного нижче графа ( Рис. 2.1 а ) матрицею інціденцій буде матриця, представлена ??на ( Рис. 2.1 б).
Матриця суміжності.
Незважаючи на те, що подання графа у вигляді матриці інціденцій грає дуже велику роль в теоретичних дослідженнях, практично цей спосіб досить неефективний. Насамперед, в матриці в кожному стовпці тільки два ненульових елемента, що робить цей спосіб представлення графа неекономним при великій кількості вершин. Крім того, вирішення практичних завдань за допомогою матриці інціденцій дуже занадто.
Оцінимо, наприклад, тимчасові витрати на рішення за допомогою матриці інціденцій такого простого завдання в орієнтованому графі: для даної вершини знайти її «оточення» - безліч наступників і безліч попередників вершини, тобто безліч всіх вершин, безпосередньо досяжних з, і безліч всіх вершин, з яких вона безпосередньо досяжна.
Для вирішення цього завдання на матриці інціденцій орієнтованого графа потрібно йти по рядку з номером до появи ненульового елемента (+1 або - 1). У разі якщо виявлена ??+1, у відповідному стовпці треба знайти рядок, в якій записано число - 1. Номер рядка, в якій коштує це число, дає номер вершини, безпосередньо досяжною з даної вершини. Якщо виявлена ??- 1, в стовпці треба знайти рядок, в якій записана 1, і отримати номер вершини, з якої безпосередньо досяжна дана вершина. Для отримання всього «оточення» треба виконати зазначений пошук для всіх ненульових елементів k-го рядка. Найбільш трудомісткою процедурою є пошук ненульового елемента в стовпці. Число таких процедур пошуку дорівнює ступеня вершини. Будемо в цьому випадку говорити, що складність алгоритму аналізу оточення вершини становить (порядку).
Можна побачити, що пошук «оточення» всіх вершин займе час порядку твори числа вершин орієнтованого графа на суму ступенів усіх вершин...
