розглядатися як моделі програм, даних і процесів. Вони служать зручною структурою даних для представлення об'єктів обробки інформації. Розширення традиційного кола завдань, що вирішуються на ЕОМ (переклад тексту, розпізнавання мови, складання розкладів, ігрові програми, експертні та інформаційні системи тощо), за останні кілька десятків років перетворили комбинаторику і теорію графів в основний інструмент вирішення величезного числа завдань.
Граф - це сукупність об'єктів зі зв'язками між ними. Об'єкти представляються як вершини, або вузли графа, а зв'язки - як дуги, або ребра. Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків і додатковими даними про вершинах або ребрах. Геометричний спосіб завдання графа зображений на малюнку 1.
Граф, в якому напрям ліній не виділяється (всі лінії є ребрами), називається неорієнтованим; граф, в якому напрям ліній принципово (лінії є дугами) називається орієнтованим.
Рисунок 1 - Геометричний спосіб представлення графа
Дві вершини називаються суміжними, якщо вони з'єднані ребром (дугою). Суміжні вершини називаються граничними вершинами відповідного ребра (дуги), а це ребро (дуга) - інцідентним відповідним вершинам.
Ланцюгом називається безліч ребер (в неорієнтованому графі), які можна розташувати так, що кінець (в цьому розташуванні) одного ребра є початком іншого. Інше визначення: ланцюг - послідовність суміжних вершин. Проста ланцюг - ланцюг, в якій жодне ребро не зустрічається двічі. Елементарна ланцюг - ланцюг, в якій жодна вершина не зустрічається двічі. Довжиною ланцюга називається число ребер ланцюга (або сума довжин її ребер, якщо останні задані).
Якщо будь-які дві вершини графа можна з'єднати ланцюгом, то граф називається зв'язковим. Якщо граф не є зв'язковим, то його можна розбити на зв'язкові підграфи, звані компонентами. Подграфом називається частина графа, утворена підмножиною вершин разом з усіма ребрами, що з'єднують вершини з цієї множини.
Розглянемо кілька способів машинного представлення графів.
Матриця суміжності - квадратна матриця nЧn , елемент a ij якої дорівнює одиниці, якщо ребро ( i, j) V , і нулю, якщо ребро ( i, j) V , i, j X . X - кінцеве безліч вершин, V - кінцеве безліч ребер, n - число вершин. Недоліком є ??вимоги до пам'яті.
Матриця інціденцій для ребер графа - прямокутна матриця nЧm , елемент r ij якої дорівнює одиниці, якщо вершина i инцидентна ребру j , і нулю в іншому випадку, i=1. n , j=1. m , m - число ребер.
Списки інцидентності: кожній вершині i X ставиться у відповідність список вершин, з'єднаних ребрами з вершиною i . Для неорієнтованого графа кожне ребро ( i, j) буде представлено двічі: у списку для i і в списку для j .
Приклад подання неориентированного графа за допомогою списків інцидентності наведений на малюнку 2. Відзначимо, що для неорієнтовані графів кожне ребро представлено в списках інцидентності двічі.
Малюнок 2 - Представлення графа за допомогою списків інцидентності
Число осередк...
