загрузка...
загрузка...
На головну

Позначення теорії графів

  1. III. Нейрофізіологічні або нейродинамические теорії темпераменту.
  2. XII. Теорії суспільного розвитку в 20 столітті.
  3. Z4.3. ТЕОРІЇ ЛІДЕРСТВА І СТИЛІ КЕРІВНИЦТВА
  4. Абсолютизм (абсолютно-гетерономний, абсолютно-автономні, інтуїтивні теорії)
  5. Автори теорії.
  6. Аксіоми теорії ймовірностей
  7. Аксіоми теорії ймовірностей. Дискретні простору елементарних фіналів. Класичне визначення ймовірності

Граф можна розглядати як нотацію для бінарного відносини двох множин. В даний час прийнято визначення графа давати в термінах теорії множин.

Графом називається сукупність двох множин: G = (V, Е), де V = {v1, v2, ..., vn} - Непорожня (зазвичай рахункова) безліч вершин графа, а Е = {е1, е2, ..., еm} - Безліч пар вершин (ребер) графа. числа n и m определяяют потужності множин вершин і ребер графа відповідно. Граф називається орієнтованим, якщо ребра и  невиразні; в іншому випадку граф неорієнтований. ребра виду  називаються петлями. Наочно вершини графа зображуються точками, а ребра - відрізками прямих ліній. Поруч з вершинами і ребрами записується інформація, що дозволяє однозначно їх ідентифікувати і описати їх властивості. Зокрема, числовою характеристикою ребра може бути його довжина або вага (в цьому випадку граф називається зваженим).

На рис. 2.4 дані два приклади графів - .неоріентірованного (рис. 2.4а) і орієнтованого (рис. 2.4б). Іа плоскому малюнку зображення деяких ребер перетинаються, але точки їх перетинів до вершин граа не належать.

(А) (б)

Мал. 2.4. Зображення неориентированного і орієнтованого графів.

Застосування графів характерно для подання інформації про структуру процесів і систем. Такими є: схеми телекомунікацій та автодоріг, причинно-наслідкові зв'язки явищ, схеми алгоритмів і т.п.

для графів поняття шляху (маршруту) відображає послідовні переміщення між вершинами по з'єднує їх ребрах. Шлях визначається як впорядкована послідовність ребер S = , де кожні два сусідніх ребра мають загальну вершину. ребро el називається початком, а ребро ek - Кінцем маршруту S. Шлях можна задати і послідовністю суміжних вершин графа S = . Шлях в графі, що не включає повторюваних ребер або вершин, називається простий ланцюгом, А шлях, що починається і закінчується однією і тією ж вершиною - циклом. .

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

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

Деревом T = називаютькінцевий неорієнтовний зв'язний граф без циклів. Одна з вершин дерева може бути названа коренем, а ребра дерева зазвичай називаються гілками. Тоді корінь з будь-якою іншою вершиною пов'язує тільки один шлях; в корінь не "входить» жодної гілки, а в будь-яку іншу вершину з боку кореня - тільки одна (це т.зв. ступінь або ступінь заходу вершини.) Аналогічне визначення можна дати дереву в орієнтованому графі. орієнтоване дерево - Орієнтований слабо зв'язний граф без циклів, в якому тільки одна вершина має нульову ступінь заходу, а всі інші вершини - ступінь заходу 1. При цьому корінь дерева - Вершина з нульовим ступенем заходу, а вершини з нульовим ступенем результату (без вихідних гілок) - його листя.

Приклади неориентированного і орієнтованого дерев дані на рис. 2.5.

Мал. 2.5. Приклади неориентированного (а) і орієнтованого (б) дерев.

У неориентированном графі дерева (рис. 2.5а) будь-яку вершину можна призначити коренем, що визначається особливостями розв'язуваної задачі. Наприклад, коренем можна назвати вершину v1. Для дерева в оріентірованнм графі (рис. 2.5б) тільки вершина v2 може бути коренем і позначена v0.

Дерева прийнято зображати у вигляді ієрархічної структури, коли корінь дерева є вершиною рівня 0 (верхнього) і безпосередньо пов'язаний з вершинами рівня 1, і т.д. Зображені вище дерева (рис. 2.5) можна перетворити до вигляду ієрархій. Наприклад, неорієнтоване дерево (рис. 2.5а) може бути представлено у вигляді ієрархічного дерева наступним чином (рис. 2.6а). В цьому випадку коренем ієрархії є вершина v1. Орієнтоване дерево (рис. 2.5б) також може бути зображено у формі ієрархічного дерева (рис. 2.6); таке уявлення є єдиним.

У першому випадку перший рівень ієрархії представлений вершиною v2, вершини v4 и v3 - Лежать на другому, а вершина v5 - На останньому, третьому рівні. вершини v3 и v5 є листям дерева (рис. 2.5а). На рис. 2.6б вершини v1 и v5 лежать на першому, вершини v4 и v6 - На другому, а вершина v3 - На третьому рівні ієрархії ;. v3 и v6 - лістья.

Мал. 2.6. Схеми ієрархії неориентированного (а) і орієнтованого (б) дерев

В теорії графів розроблено методи аналізу різних класів графів і алгоритми побудови спеціальних графових об'єктів, викладених в численних джерелах. Найбільш часто теорія графів в інформатиці застосовується для дослідження логіко-інтуїтивного опису знань або при аналізі будь-якої конкретної предметної області природної мови і поданні її у вигляді тезауруса. (Див. ГОСТ 7.24-90 "СИБИД. Тезаурус інформаційно-пошуковий багатомовний. Склад, структура і основні вимоги до побудови.).



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

Козлов А. Д., лекала В. А. | Вступ | Мета, завдання, структура, система, системність | Класифікація систем. Великі і складні системи. | Управління в системі та управління системою. | Приклад використання системного аналізу предметної області | Організувати процес навчання | Етапи та область застосування програмно-цільового підходу | Дерево цілей. | Стадії аналізу і синтезу |

загрузка...
© um.co.ua - учбові матеріали та реферати