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

Основні види графів

Дивіться також:
  1. I. Кислотно-основні властивості органічних сполук
  2. I. Кислотно-основні властивості органічних сполук
  3. I. Основні
  4. I. Основні категорії страхування.
  5. I. Основні підходи до управління реалізацій стратегічних змін.
  6. I. Основні риси російської історії до початку XI ст.
  7. I. Основні етапи СТАРОГО ЗАВІТУ
  8. I. Сутність і основні функції перестрахування.
  9. I. Цілі та основні етапи портфельного аналізу.
  10. I.1. Основні визначення.
  11. II. Неофрейдизмом: Загальна характеристика, ОСНОВНІ ПРЕДСТАВНИКИ
  12. II. Суспільство як соціальна система, її основні системні ознаки

Мал. 1.

 V ребро дуга

х1 . . х2 х1 .. х2

Ставлення инцидентности R - може бути описано наступним чином. якщо -ребро, то пишемо , коли є кінцем ребра, причому кожне ребро має 2 кінці и , Можливо, збігаються. якщо -дуга, то пишемо , коли - Початок дуги , і , коли - Кінець дуги . У всіх випадках говоримо, що и інцідентни.

Визначення 2. Дві вершини графа називаються суміжними, якщо вони інцидентні одному ребру або дузі.

У графах на малюнку 1 вершини и - Суміжні, а в графі на малюнку 2 - немає.


Мал. 2.


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


Мал. 3.мультіграф


Визначення 4. ступіньвершини графа дорівнює числу ребер (дуг) інцідентних .

Зауважимо, що в графі .

Визначення 5. Граф називається орієнтованим, якщо він містить хоча б одну дугу і не містить ребер ..

Визначення 6. Граф називається неорієнтованим, якщо він містить тільки ребра.

Наприклад, графи и - Неорієнтовані, а - Орієнтований.

Визначення 7. Полустепені результату (заходу) називається число дуг виходять з вершини (заходять в вершину).

позначення: - Полустепені заходу; - Полустепені результату.

.


Мал. 4.Ступеня і полустепені вершин.

Г5

V1 V2 х3

х1 х2 V5

V3 V4

х4

Визначення 8. Петля - дуга (ребро), початок і кінець якої збігаються.

Визначення 9. Вершина називається ізольованою, якщо.

Затвердження 1. Для орієнтованого графа без петель справедливі рівності

и .

Доведення. Для орієнтованого графа без петель . Звідси випливає перша рівність. Друге рівність випливає з визначень.

Затвердження 2. У графі без петель справедливо рівність: , де число ребер і дуг.

Доведення. Так як петель немає, то кожне ребро (або дуга) має два різних кінця. Отже, у зазначеній сумі вони враховуються двічі. Ч. т. Д.

Затвердження 2. Для орієнтованого графа без петель справедливі рівності

и .

Визначення 9.Вершина називається ізольованою, якщо

Визначення 10. Вершина називається висячої (листом), якщо

Визначення 11. Вершина називається вузлом, якщо

Визначення 12. Граф називається однорідним якщо всі ступені його вершин однакові.

Визначення 13. Граф (простий) називається повним якщоn - Число вершин


Мал. 5.Однорідний і повний графи.


однорідний граф

   
 
 
 


повний граф


Визначення 14. Шлях в орієнтованому графі - це послідовність дуг

в якій початок наступної дуги збігається з кінцем попереднього.

Визначення 15. Ланцюг в неориентированном графі - послідовність ребер

, В якій для кожного ребра один кінець збігається з кінцем попереднього ребра, а інший кінець є початком наступного ребра.

для Г5 послідовність - Шлях, а послідовність - Не шлях.


Рис 6.Ланцюги в неориентированном графі.

Г6

V1

x2 V2

x1 V3 x3 V5

V6 V4

x4

ланцюги:

Визначення 16. Замкнута ланцюг (шлях) називається циклом (контуром).

Зауважимо, що ланцюг є замкнутою, якщо її початок збігається з кінцем.

В графі ланцюг - Контур; в графі ланцюг - Цикл, а - Цикл (але не контур)!

Зауваження. Якщо в орієнтованому графі ігнорувати орієнтацію, тобто замінити всі дуги на ребра, то отримуємо неорієнтовані граф, в якому визначені ланцюга і цикли.

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

Визначення 18. Шлях (ланцюг) називається елементарним (елементарної), якщо кожна вершина зустрічається не більше 1 разу.

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

В графі шлях можна записати у вигляді

Визначення 19: Цикл називається ейлеровим, якщо він містить всі ребра графа і є простим.

Визначення 20: Граф називається ейлеровим якщо він містить Ейлером цикл.

Визначення 21: Цикл називається Гамільтона, якщо він містить всі вершини графа і є елементарним.

Визначення 22: Граф називається Гамільтона якщо він містить гамільтонів цикл.

Теорема 1: якщо граф Ейлеров, то все його вершини - парні.

Доведення. нехай - Ейлером цикл і . Початком і кінцем циклу можна вважати деяку вершину . Напрямок обходу циклу можна вибрати довільно. Нехай при обході циклу перший раз ми входимо в вершину по некото-рому ребру і виходимо по ребру . Якщо інших ребер, інцидентних , Немає, то ступінь вершини дорівнює 2 і теорема доведена. Інакше, прибираємо ребра , і помічаємо, що цикл повторно входить в вершину по деякому ребру і виходить по ребру , Так, що або і теорема доведена, або міркування можна продовжити. В результаті будуть вичерпані всі інцидентні ребра, що і завершує доказ.

Основні поняття «-- попередня | наступна --» Лекція № 2. Введення в теорію графів (продовження).
загрузка...
© om.net.ua