На головну

Орієнтовані і неорієнтовані мережі

  1. БАЙТ - ОРІЄНТОВАНІ ПРОТОКОЛИ
  2. БІТ-ОРІЄНТОВАНІ ПРОТОКОЛИ
  3. Комплексно-орієнтовані моделі теоретичного обґрунтування соціальної роботи
  4. Концепції, орієнтовані на психічний розвиток
  5. Особистісно-орієнтовані технології початкової освіти
  6. Методо-орієнтовані ППП
  7. Об'єктно-орієнтовані методи аналізу і проектування ПЗ

дугу (i, j) Називають спрямованої від вузла i до вузла j, Якщо додатковий потік з i в j, Що протікає по цій дузі, збільшує величину вже існуючого в ній потоку, а протилежний додатковий потік зменшує цю величину. Спрямовані дуги іноді позначають у такий спосіб: [i, j]. Спрямована дуга називається орієнтованої і в  графічному поданні мережі позначається лінією зі стрілкою (див. рис. 2а). Дуга, яка не має напряму, називається неориентированной і в графічному поданні мережі позначається лінією (див. Рис. 2б).

Мережі (графи) також можуть бути орієнтованими (що містять орієнтовані дуги - орграф) і неорієнтованими (що містять тільки неорієнтовані дуги).

ланцюгом [i, j, ..., k] З вузла i в вузол k називають підграф G1 мережі G, Що складається з послідовності дуг і вузлів, в якій кінцевий вузол кожної дуги (виключаючи вузли i и k) Є початковим вузлом наступної дуги. Ланцюг може включати неорієнтовані дуги.

шляхом (i, j, ..., k) З вузла i в вузол k називають підграф G2 мережі G, Що складається з послідовності дуг і вузлів, в якій кожен вузол (виключаючи вузли i и k) Є початковим або кінцевим вузлом тільки двох дуг з G2 і кожна дуга шляху починається і закінчується в вузлах з G2.

Контур - кінцевий ланцюг з початком і кінцем в одному і тому ж вузлі.

Цикл - кінцевий шлях з початком і кінцем в одному і тому ж вузлі.

Петля - цикл або контур з однієї дуги і одного вузла.

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

Мережа (граф) связна, якщо для будь-яких двох її вузлів існує з'єднує їх шлях.

Мережа сильно связна (граф повний), якщо для будь-яких двох її вузлів існує з'єднує їх ланцюг.

Граф G=G(V, E) називається дводольним, якщо V можна уявити як об'єднання непересічних множин, скажімо V=AEB, Так що кожне ребро має вигляд (vi, vj), Де viIA и vjIB. Двочастковий граф називається повним дводольним графом Km, n, якщо A містить m вершин, B містить n вершин і для кожного viIA, vjIB маємо (vi, vj) IE.

приклад Повний двочастковий граф K2,4 і повний граф K4.

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

У незв'язного графа будь компонента зв'язності складається не більше, ніж з n-1 вершин. Якщо відомо, що у графа k компонент зв'язності, то даємо ще більш сувору оцінку: будь-яка компонента зв'язності складається з не більше, ніж з n-k + 1 вершин.

Якщо у незв'язного графа k компонент зв'язності, то для отримання зв'язкового графа потрібно додати в граф як мінімум k-1 ребро.

Псевдографом - граф, який може містити петлі і / або кратні ребра

Мультіграф - граф, в якому може бути пара вершин, яка з'єднана більш ніж одним ребром (ненаправленим), або більш ніж двома дугами протилежних напрямків.

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

Теорема про суму ступенів вершин графа: У графі G сума ступенів усіх його вершин - число парне, рівне подвоєному числу ребер графа. Формула суми ступенів для графа G= (V, E):

Слідство. Число непарних вершин будь-якого графа парне.

Властивості ступеня вершини:

· В графі G (V, E) сума ступенів усіх його вершин - число парне, рівне подвоєному числу ребер графа.

· Число непарних вершин будь-якого графа парне.

· У всякому графі з n вершинами, де n ? 2 завжди знайдуться, щонайменше, дві вершини з однаковими ступенями.

· Якщо в графі з n вершинами (n ? 2) в точності дві вершини мають однаковий ступінь, то в цьому графі завжди знайдеться або в точності одна вершина ступеня 0, або в точності одна вершина ступеня n-1.

Гамильтонов граф це граф, що містить Гамільтонових ланцюг або гамильтонов цикл.

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

Простий цикл -цикл, що не проходить двічі через одну вершину.

Остов - підграф, що містить всі вершини графа.

Цикломатичне число графа - мінімальне число ребер, які треба видалити, щоб граф став ациклічним. Для зв'язного графа існує співвідношення: p1(G) =p0(G) + |E(G) | - |V(G) | де p1(G) - Цикломатичне число, p0 - число компонент зв'язності графа, |E(G) | - число ребер, А |V(G) | - число вершин.

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

Теорема (критерій ейлерову):

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

Доведення: Припустимо, що граф G має Ейлером цикл. Граф є зв'язковим, так як кожна вершина належить циклу. Для будь-якої вершини v графа G кожен раз, коли Ейлером цикл проходить через v, Він вносить 2 в ступінь v. Тому ступінь v парна.

Назад, потрібно показати, що кожен зв'язний граф, у якого ступеня вершин парні, має Ейлером цикл. Доведемо цю теорему, використовуючи індукцію по числу вершин. Оскільки теорема тривіально справедлива при n<3, почнемо індукцію з n = 3. Припустимо, що кожен зв'язний граф, який має менш k вершин, і всі вершини якого мають парної ступенем, містить Ейлером цикл. Нехай G - зв'язний граф, що містить k вершин, ступеня яких парні. Припустимо, що v1 и v2  - Вершини графа G. Оскільки граф G - зв'язний, існує шлях з v1 в v2 . оскільки ступінь v2 - Парна, існує невикористане ребро, по якому можна продовжити шлях. Оскільки граф кінцевий, то шлях, в кінці кінців, повинен повернутися в v1 , І Ейлером цикл З1  можна вважати побудованим. Якщо з1 є ейлеровим циклом для G, тоді доказ закінчено. Якщо немає, то нехай G/  - Підграф графа G, отриманий видаленням всіх ребер, що належать С1. оскільки С1 містить парне число ребер, інцидентних кожній вершині, кожна вершина подграфа G/  має парну ступінь.

Нехай e - ребро графа G/ , Нехай Ge - Компонента графа G/ , Що містить е. Оскільки G/  має менше, ніж k, вершин, і у кожної вершини графа G/  парна ступінь, граф G/  має Ейлером цикл. нехай С2 . Далі у С1 і С2  є загальна вершина, припустимо, а. Тепер можна продовжити Ейлером цикл, починаючи його в а, пройти З1 , Повернутися в а, потім пройти З2 і повернутися в а. Якщо новий Ейлером цикл не є ейлеровим циклом для G, продовжуємо використовувати цей процес, розширюючи наш Ейлером цикл, поки, до врешті-решт, не отримаємо Ейлером цикл для G .

 
 

 На рис. 3 наведені приклади орієнтованої і неориентированной (а), (е) мереж і містяться в них ланцюги (б) і контуру (в); шляху (б, д), циклу (в, е) і петлі (г); бесконтурной (ж) і ациклической (з); зв'язковий (а, е, ж, з) і сильно зв'язковий (а, е) мереж.

розріз C в графі - безліч його дуг, виключення яких з мережі G розділяє її на два незв'язних між собою подграфа G1, G2 вихідної мережі. Тобто:

C = {(i, j): (i, j)  A}:

G = G1 G2  C; G1CG2 =  , G1CC =  , G2CC = ;  i, j  G: i G1, j G2; (I, j) C.

величина розрізу C, Його пропускна здатність Rc (G1 G2) в напрямку від G1 к G2- Це сума пропускних спроможностей rij всіх дуг [i, j] розрізу C, Що починаються в G1 і закінчуються в G2(Див. Рис. 4):

Rc (G1 G2) = rij.

Таким чином, кожен розріз орієнтованої мережі характеризується двома пропускними здатностями: Rc (G1 G2) и Rc (G2 G1). У додатках теорії графів для мереж з одним джерелом s і одним стоком r велике значення мають розрізи, що розділяють стік і джерело, причому важливою виявляється тільки величина розрізу в напрямку від джерела до стоку. Для таких розрізів s G1, r G2; а Rc (s  r) = Rc. У кожній конкретній мережі розрізів цього типу може бути кілька. Той з них, величина якого найменша, називається мінімальним розрізом, а той, величина якого найбільша - максимальним розрізом.



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

Вступ | Перелік використовуваних надалі позначень | Ізоморфізм і гомеоморфизм графів. | Дерева і деревовидних | Матричні уявлення мереж | Постановка задачі | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

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