Page 49 - 197_

широко використовуються як засіб формалізованого проміжного
опису ОП перед його описом на вхідній мові проектування,
створення алгоритмів проектування, наприклад для задач опису
об’єкту виробництва, бази даних, задач синтезу й аналізу.

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

Точки, в яких сходяться лінії, називаються вершинами або
вузлами графа.
Лінії з односторонніми стрілками називаються
орієнтованими ребрами або дугами. Вони вказують не лише на

зв’язок між вершинами, а й на орієнтацію цього зв’язку.
Стрілка дуги вказує напрямок орієнтації.
Ланка або неорієнтоване ребро відповідає можливому

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

Граф, що не має кратних ребер, називають деревом.

Рисунок 6.1 – Зображення графа

Якщо х позначити і-ту вершину, U – ребро, яке зв’язує цю
і
і
вершину з іншою (х ), то перехід від початкової вершини х до
0
і-1
кінцевої х можна описати ланцюгом графа виду x U x …U x .
1 1
n
n n
0
Вершини х і х називаються відповідно початковою і кінцевою
n
0
вершинами ланцюга. Ланцюг графа називають простим, якщо
усі х різні. Якщо в ланцюгу графа кожне ребро U – дуга,
і
і
орієнтована від х до х , то ланцюг називають орієнтованим.
і
і-1
Якщо ланцюг графа має х =х , а решта вершин ланцюга різні,
0
n
то він називається простим циклом.
Граф, у якому кожному ребру зіставлене число (“вага” цього
ребра), називається зваженим. Зважені графи широко
49