Головна

Можливості підключення графів

  1. Ізоморфізм і гомеоморфизм графів.
  2. Використання графів при вирішенні задач
  3. Позначення теорії графів
  4. Основи мережевого моделювання та теорія графів. Основні методи розрахунку мережевих моделей. Узагальнені детерміновані мережеві моделі.
  5. Оцінка числа неізоморфних графів з q ребрами
  6. перерахування графів
  7. Подання графів в комп'ютері

нехай  - Граф з вершинами (  ) І ребрами (  ).

Визначення 1.6. маршрутом (шляхом) довжини з вершини  в вершину  (Або між и  ) Називається послідовність  така, що .

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

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

Аналогічно, як і для графа, для орграфа вводяться поняття орієнтований шлях, орієнтований цикл.

Приклад 1.3. Дан неорієнтовані граф.

,

Визначення 1.7. Граф  називається зв'язковим, якщо є ланцюг між будь-якими двома його різними вершинами.

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

Визначення 1.8.орграф  називається зв'язковим, Якщо його співвіднесений граф є зв'язковим. орграф називається сильно зв'язковим, Якщо для будь-якої пари вершин  існує орієнтований шлях з в .

 



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

Завдання про кенігсберзькими мостах | Подання графів в комп'ютері | Приклад 1.6. | дерева | Приклад 2.1. | остовне дерева | Приклад 2.2. | Алгоритм Краскала і алгоритм Прима | алгоритм Краскала | алгоритм Прима |

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