p>
з
3
f
d
4
b
з
f
e
5
d
e
Для машинної обробки більш зручним є символічне уявлення графів у вигляді списку ребер з зазначенням, які вершини це ребро з'єднує, а також табличне представлення, де рядки і стовпці - назви вершин, а значення комірок вказують на те, з'єднані дані вершини чи ні.
Приклад
Графи, представлені на рис.7 можуть бути описані, наприклад, такими способами. Символічна запис: а (1,2) b (l, 4) c (2,4) d (3,5) e (4,5), (3,4)
Таблична запис:
В
Рис.7. Графи, що мають однакові описи у вигляді таблиці і символічного запису
Представлення даних у формі дерева
Особливим видом графа є дерево. Дана форма моделі застосовується тоді, коли елементи модельованого об'єкта знаходяться в стані якогось підпорядкування і супідрядності, коли є ставлення ієрархічності.
Приклад
Модель управління підприємством (Школою, театральним колективом і т. д.) дуже зручно представляти у вигляді дерева.
Приклад
Вам добре відомо поняття В«родовідне деревоВ» і ви можете зобразити в такій формі ваші родинні відносини.
Приклад
Каталог файлів на диску, також як і бібліотечний каталог - приклади інформаційних моделей у формі дерева. Дерево - це граф, призначений для відображення таких зв'язків між об'єктами, як вкладеність, підпорядкованість, спадкування тощо
Будується він у такий чином
Спочатку малюємо В«головнуВ» вершину, яка не залежить ні від однієї іншої вершини. Ця вершина називається коренем дерева і є єдиною вершиною 1-го рівня. Далі додаємо вершини 2-го рівня. Їх може бути скільки завгодно, і всі вони обов'язково пов'язані з коренем - вершиною 1-го рівня, але не пов'язані між собою. На наступному кроці додамо вершини 3-го рівня. Кожна з них буде пов'язана рівно з однією вершиною 2-го рівня (більше ні з однією іншою вершиною). До будь-якої вершині 2-го рівня може бути приєднане скільки завгодно вершин 3-го рівня (у тому числі, жодної). Наступний крок - добавка вершин 4-го рівня, кожна з яких буде пов'язана рівно з однією вершиною 3-го рівня (і не пов'язана більше ні з чим). І так далі. На кожному кроці додаємо вершини чергового рівня, кожна з яких буде пов'язана рівно з однією вершиною попереднього рівня і не буде мати ніяких інших зв'язків. Отриманий граф нагадує розгалужених кущ, який В«Росте зверху внизВ»: верхні рівні мають менші номери, нижні - великі. Взагалі кажучи, дерево може бути і неорієнтованим графом, але частіше дерево орієнтоване, причому дуги спрямовані від верхніх вершин до нижніх. Верхня вершина називається предком для пов'язаних з нею нижніх вершин, а нижні вершини - Нащадками відповідної верхньої вершини. На будь-якому дереві існує єдина вершина, яка не має предка, - корінь - і може бути скільки завгодно вершин, що не мають нащадків, - листя. Всі інші вершини мають рівно одного предка і скільки завгодно нащадків. Якщо не брати до уваги спрямованість зв'язків, то в дереві з будь-якої вершини можна по лініях дійти до будь-якої іншої вершини, причому по одному єдиному шляху. У вигляді дерева зручно зображувати системи, в яких нижні вершини в якомусь сенсі В«підпорядкованіВ» верхнім. Верхня вершина може зображати начальника, нижні - підлеглих; верхня - систему, нижні - її компоненти; верхня - безліч об'єктів, нижні - вхідні в нього підмножини; верхня вершина - предка, нижні - нащадків і т. д. Формалізація в разі побудови дерева (ієрархічного графа) зводиться до виявленню основного (головного, центрального) елемента розглянутого об'єкта (Вершина нульового рівня, яку часто називають коренем), елементів, які знаходяться в безпосередньому підпорядкуванні від основного (вершини 1-го рівня). Потім визначаються вершини, що знаходяться в безпосередньому В«підпорядкуванніВ» від вершин 1-го рівня (вершини 2-го рівня) і так далі. Зображати побудоване дерево відносин можна в будь-якому напрямку - це вже справа естетичного смаку розробника моделі. У науковій та навчальній діяльності за допомогою дерев часто представляють класифікацію досліджуваних об'єк...
