www.wikidata.uk-ua.nina.az

Міст теорія графів В теорії графів міст ребро видалення якого збільшує кількість компонент зв язності або інакше кажучи

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

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

Граф із 6 мостами (позначені червоним)

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

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

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

Перший алгоритм для знаходження мостів в зв'язному графі за лінійний час був віднайдений Робертом Тарджаном в 1974 році.

Алгоритм складається з наступних кроків:

  1. Знайти кістякове дерево для
  2. Створити дерево з коренем з кістякового дерева
  3. Обійти дерево в прямому порядку і пронумеровати вершини. Тепер номери батьківських вершин менші за номери нащадків.
  4. Для кожної вершини при обході у прямому порядку робимо:
    1. Підраховуємо кількість нащадків для цієї вершини.
    2. Підраховуємо і
    3. Для кожної такої, що : якщо і , тоді ребро буде мостом.

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

де батьківська вершина для .

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

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

Ребро є мостом тоді і тільки тоді, коли з піддерева з коренем у неможливо потрапити у вершину, яка не є нащадком . Це легко перевірити, бо піддерево з коренем у (об'єднує всіх нащадків w) містить наступні вершини , тож ми можемо просто перевірити, знаходяться в цій множині чи ні для перевірки чи є ребро мостом.

Примітки ред.

  1. Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 22: Елементарні алгоритми на графах. Вступ до алгоритмів (вид. 3). К.І.С. с. 633. ISBN 978-617-684-239-2. 
  2. Tarjan, R. Endre (1974). A note on finding the bridges of a graph. Information Processing Letters 2 (6): 160–161. MR 0349483. doi:10.1016/0020-0190(74)90003-9. .

Посилання ред.


Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V teoriyi grafiv mist rebro vidalennya yakogo zbilshuye kilkist komponent zv yaznosti abo inakshe kazhuchi vidokremlyuye pidgraf 1 Rivnoznachne viznachennya rebro ye mostom todi i tilki todi koli voni ne ye chastinoyu bud yakogo ciklu Graf iz 6 mostami poznacheni chervonim Zmist 1 Podvijne pokrittya ciklami 2 Algoritm znahodzhennya mostiv 3 Primitki 4 PosilannyaPodvijne pokrittya ciklami red Grafi bez mostiv porodzhuyut cikavu problemu rishennya yakoyi ne znajdeno dosi Chi virno sho v bud yakomu neoriyentovanomu grafi bez mostiv isnuye takij nabir cikliv sho kozhne rebro grafu zustrichayetsya v nomu rivno dvichi Algoritm znahodzhennya mostiv red Pershij algoritm dlya znahodzhennya mostiv v zv yaznomu grafi za linijnij chas O V E displaystyle O V E nbsp buv vidnajdenij Robertom Tardzhanom v 1974 roci 2 Algoritm skladayetsya z nastupnih krokiv Znajti kistyakove derevo dlya G displaystyle G nbsp Stvoriti derevo T displaystyle T nbsp z korenem z kistyakovogo dereva Obijti derevo T displaystyle T nbsp v pryamomu poryadku i pronumerovati vershini Teper nomeri batkivskih vershin menshi za nomeri nashadkiv Dlya kozhnoyi vershini v displaystyle v nbsp pri obhodi u pryamomu poryadku robimo Pidrahovuyemo kilkist nashadkiv N D v displaystyle ND v nbsp dlya ciyeyi vershini Pidrahovuyemo L v displaystyle L v nbsp i H v displaystyle H v nbsp Dlya kozhnoyi w displaystyle w nbsp takoyi sho v w displaystyle v to w nbsp yaksho L w w displaystyle L w geq w nbsp i H w lt w N D w displaystyle H w lt w ND w nbsp todi rebro v w displaystyle v w nbsp bude mostom Viznachennya Rebro poza derevom mizh v displaystyle v nbsp i w displaystyle w nbsp poznachayetsya v w displaystyle v w nbsp Rebro v derevi z batkivskoyu v displaystyle v nbsp poznachayetsya v w displaystyle v to w nbsp N D v 1 v w N D w displaystyle ND v 1 sum v to w ND w nbsp de v displaystyle v nbsp batkivska vershina dlya w displaystyle w nbsp N D v displaystyle ND v nbsp kilkist nashadkiv v vklyuchno iz soboyu v kistyakovomu derevi L v min v L w v w w v w displaystyle L v min v cup L w mid v to w cup w mid v w nbsp H v max v H w v w w v w displaystyle H v max v cup H w mid v to w cup w mid v w nbsp L v displaystyle L v nbsp i H v displaystyle H v nbsp poznachki vershin z najmenshoyu i najbilshoyu poznachkoyu obhodu pryamogo poryadku dosyazhnih z v displaystyle v nbsp prohodom po pidderevu z korenem u v displaystyle v nbsp razom z shonajbilshe odnim rebrom ne v derevi Rebro v w displaystyle v to w nbsp ye mostom todi i tilki todi koli z piddereva z korenem u w displaystyle w nbsp nemozhlivo potrapiti u vershinu yaka ne ye nashadkom w displaystyle w nbsp Ce legko pereviriti bo pidderevo z korenem u w displaystyle w nbsp ob yednuye vsih nashadkiv w mistit nastupni vershini w w 1 w N D w 1 displaystyle w w 1 ldots w ND w 1 nbsp tozh mi mozhemo prosto pereviriti znahodyatsya L w H w displaystyle L w H w nbsp v cij mnozhini chi ni dlya perevirki chi ye rebro mostom Primitki red Kormen Tomas Lejzerson Charlz Rivest Ronald Stajn Kliford 2019 Rozdil 22 Elementarni algoritmi na grafah Vstup do algoritmiv vid 3 K I S s 633 ISBN 978 617 684 239 2 Tarjan R Endre 1974 A note on finding the bridges of a graph Information Processing Letters 2 6 160 161 MR 0349483 doi 10 1016 0020 0190 74 90003 9 Posilannya red nbsp Bridges and Articulation points Algorithm na YouTube nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Mist teoriya grafiv amp oldid 39526329