Головна

Елементи теорії графів. Види і способи завдання графів

  1. II. ЗАВДАННЯ ДЛЯ ТИПОВИХ РОЗРАХУНКІВ
  2. III. Артилерійський ПОСТРІЛ І ЙОГО ЕЛЕМЕНТИ
  3. III. Виконання завдання
  4. III.4.3) Види і елементи провини.
  5. Інструмент контрольно ЗАВДАННЯ для самоперевірки
  6. VII.2.2) Способи набуття права власності.
  7. XI. Пристосування ТА ІНШІ ЕЛЕМЕНТИ, властивості. Здібностей та обдарувань АРТИСТА

У багатьох прикладних задачах вивчаються системи зв'язків між різними об'єктами. Об'єкти називаються вершинами і позначаються точками, а зв'язку - дугами. Такі системи утворюють графи. Наприклад: граф зображує мережу вулиць а місті; мережу доріг, трубопроводів, блок - схеми програмування і багато інших моделей.

Визначення. Графом називається сукупність двох множин - непорожньої безлічі V вершин і безліч Е двоелементний підмножин безлічі V (безліч ребер Е).

Позначаються G (V, E) = , V ? O

Безліч двох елементних підмножин визначає симетричне бінарне відношення на множині Е = V ? V, E = E-1; тому ребро можна вважати не тільки як безліч  , Але і як пару  число вершин позначають Р, число ребер - q; якщо дугами є пари вершин  то дуга вважається що виходить із v1 і заходить в v2; граф G зображують діаграмою.

2

1 V =  - Безліч вершин

 3 Е = -

безліч дуг

За наявності кількох дуг, що виходять з вершини v1 в вершину v2 , Такі дуги називаються кратними, граф називається кратним.

Якщо всі елементи множини Е - впорядковані пари, то граф G називається орієнтованим (орграф), елементи V називаються вузлами, а безліч Е дугами, тобто якщо  (А, b)  E, (b, a) ? E

Якщо елементом Е може бути пара однакових (НЕ різних) елементів V, то такий елемент називається петлею, а граф називається графом з петлями (псевдографом). Якщо Е містить кілька однакових елементів, то ці елементи називаються кратними ребрами, a G - мультиграфом.

якщо  (А, b)  E / \ (b, a)  E, то G називається неорієнтованим (Неограф). В цьому випадку дуга називається ребром і позначається у вигляді відрізка, що з'єднує вершини, а вершини а і b називаються кінцями ребра  і інформацію про ці дугах пишуть: =

 або  - Ребро графа

 



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

МАТЕМАТИКА | Вступ | Вказівка ??до виконання та оформлення контрольних робіт | Теми контрольної роботи | Елементи теорії множин. Безлічі і його елементи. Підмножини. | Основні логічні символи | Матриця інціденцій вершин і ребер | Матриця суміжності вершин | Застосування формул Крамера до вирішення систем лінійних рівнянь. | Тема 4. Диференціювання |

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