Міст (теорія графів)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф із 6 мостами (позначені червоним)

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

Подвійне покриття циклами[ред.ред. код]

Графи без мостів породжують цікаву проблему, рішення якої не знайдено досі. Чи вірно, що в будь-якому неорієнтованому графі без мостів існує такий набір циклів, що кожне ребро графа зустрічається в ньому рівно двічі[1].

Алгоритм знаходження мостів[ред.ред. код]

O(|V|+|E|) алгоритм для знаходження мостів в зв'язному графі був віднайдений Робертом Тар'яном в 1974.[2] Також існує розподілена версія алгоритму.[3]

Алгоритм:

  1. Знайти кістякове дерево для G
  2. створити дерево T з корним з кістякового дерева
  3. Обійти дерево T в прямому порядку і пронумеровати вершини. Тепер батьківські вершини мають меньши номери ніж дочірні.
  4. Для кожної вершини з v_1 (листя дерева) до 1 (корінь дерева) робимо:
    1. Підраховуємо кількість нащадків ND(v) для цієї вершини.
    2. Підраховуємо L(v) і H(v)
    3. Для кожної w такої, що v \to w: якщо L(w) \geq w і H(w) <  w + ND(w) тоді (v, w) міст.

Визначення: Ребро поза деревом між v і w познчається v--w. Ребро в дереві з батьківською v позначається v\to w.

ND(v) = 1 + \sum_{v \to w} ND(w) де v батьківська вершина для w.

ND(v) кількість нащадків v (включно із собою) в кістяковому дереві.

L(v) = \min(\{v\} \cup \{L(w) \mid v \to w\} \cup \{w \mid v--w\})

H(v) = \max(\{v\} \cup \{H(w) \mid v \to w\} \cup \{w \mid v--w\})

L(v) і H(v) позначки вершин з найменшою і найбільшою позначкою обходу прямого порядку, досяжних з v проходом по піддереву з коренем у v, разом з щонайбільше одним ребром не в дереві.

Ребро v \to w є мостом тоді ітільки тоді, коли з піддерева з коренем у w неможливо потрапити у вершину, яка не є нащадком w. Це легко перевірити, бо піддерево з коренем у w (об'єднує всіх нащадків w) містить наступні вершини \{w, w+1, \ldots, w+ND(w)-1\}, тож ми можемо просто перевірити, знаходяться L(w), H(w) в цій множині чи ні для перевірки чи є ребро мостом.

Примітки[ред.ред. код]

  1. http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm
  2. "A note on finding the bridges of a graph", Robert Endre Tarjan, Information Processing Letters, April 1974 pp160-161.
  3. http://sma.epfl.ch/~pritchar/math/2006/podc-bicon-a0-poster.pdf