На головну

Ізоморфізм і гомеоморфизм графів.

  1. Основи мережевого моделювання та теорія графів. Основні методи розрахунку мережевих моделей. Узагальнені детерміновані мережеві моделі.
  2. Тверді розчини. Поняття про ізоморфізмі
  3. Елементи теорії графів. Види і способи завдання графів

визначенняфункція f : G(V, E) ® G1(V1, E1) є изоморфизмом (позначається G~G1), Якщо f: V®V1 и f: E® E1 являють собою взаємно однозначні відповідності. якщо f:G®G1 - Ізоморфізм, то G и G1 називаються ізоморфними.

приклад Дан неорієнтовний позначений граф G1(V1; E1). Побудувати ізоморфні йому графи.

,

Теорема. Ізоморфізм графів є відношення еквівалентності.

Доведення. Дійсно, ізоморфізм володіє всіма необхідними властивостями відносини еквівалентності:

[рефлексивність.] G ~ G, Де необхідна біекція є тотожна функція;

[Симетричність.] Якщо G1 ~ G2 з біекція h, то G2 ~ G1 з біекція h- 1;

[Транзитивність.] Якщо G1 ~ G2 з біекція h и G2 ~ G3 з біекція g, то G1 ~ G3 з біекція g o h.

Кажуть, що мережі G1 = {N1, A1} и G2 = {N2, A2} ізоморфні, якщо між їх дугами і вузлами може бути встановлено взаємно однозначна відповідність: N1 <=> N2: A1 <=> A2.

Вірно наступне твердження: будь-яке рівняння, справедливе для даної мережі, справедливо і для изоморфной їй мережі. Це властивість ізоморфних мереж може в ряді випадків істотно спрощувати аналіз мереж за рахунок виділення в них подграфов, ізоморфних один одному або раніше дослідженим мереж.

Алгоритм розпізнавання двох ізоморфних графів:

1. Підраховуємо число вершин кожного графа (число вершин має збігатися, в іншому випадку графи неізоморфних).

2. Виписуємо всі елементи обох графів в природної впорядкованості і визначаємо пари (xi, xj) І (yi, yj) Для кожного еле-мента, де xi , yi - Число випадків для кожної вершини графів G1 і G2, а xj, yj - Число заходів для відповідних графів.

3. Для кожного елемента хграфа G1 шукаємо такий елемент у графа G2, Що виконується умова: число випадків х збігається з числом результатів у, І число заходів х збігається з числом заходів у. знайдені елементи х и у з'єднуємо ребром, т. е. будуємо граф відповідності (якщо відповідності немає, то граф не ізоморфні).

4. Виписуємо підстановку, яка переводить граф G1 в граф G2.

Приклад ізоморфізму графів.

 Граф G1  Граф G2  Ізоморфізм між графами G1 і G2  підстановка ізоморфізму f
f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

Визначення. Операція подразбіенія (подрібнення) дуги (U, v) в орграфе D = (V, E) полягає у видаленні з Е дуги (u, v), додаванні до V нової вершини w і додаванні до Е | {(U, v)} двох дуг (u, v), (w, v). Аналогічно визначається операція подразбіенія ребра в графах.

Визначення. Орграф D1 називається подразбіеніем орграфа D2, якщо орграф D1 можна отримати з D2 шляхом послідовного застосування операції подразбіенія дуг.

Визначення. Орграфів D1, D2 називаються гомеоморфними, Якщо існують їх подразбіенія, є ізоморфними.

Аналогічно визначається подразбіеніе графа і гомеоморфизм графів.



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

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

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