В теорії графів, міст — ребро, видалення якого збільшує кількість (компонент зв'язності) (або, інакше кажучи, відокремлює (підграф)). Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли воно не є частиною будь-якого (циклу).
Подвійне покриття циклами
Графи без мостів породжують цікаву проблему, рішення якої не знайдено досі. Чи вірно, що в будь-якому неорієнтованому графі без мостів існує такий набір циклів, що кожне ребро графу зустрічається в ньому рівно двічі.
Алгоритм знаходження мостів
Перший алгоритм для знаходження мостів в зв'язному графі за (лінійний час) був віднайдений Робертом Тарджаном в 1974 році.
Алгоритм складається з наступних кроків:
- Знайти кістякове дерево для
- Створити дерево з коренем з кістякового дерева
- Обійти дерево в прямому порядку і пронумеровати вершини. Тепер номери батьківських вершин менші за номери нащадків.
- Для кожної вершини при обході у прямому порядку робимо:
- Підраховуємо кількість нащадків для цієї вершини.
- Підраховуємо і
- Для кожної такої, що : якщо і , тоді ребро буде мостом.
Визначення: Ребро поза деревом між і позначається . Ребро в дереві з батьківською позначається .
де батьківська вершина для .
кількість нащадків v (включно із собою) в кістяковому дереві.
і позначки вершин з найменшою і найбільшою позначкою обходу прямого порядку, досяжних з проходом по піддереву з коренем у , разом з щонайбільше одним ребром не в дереві.
Ребро є мостом тоді і тільки тоді, коли з піддерева з коренем у неможливо потрапити у вершину, яка не є нащадком . Це легко перевірити, бо піддерево з коренем у (об'єднує всіх нащадків w) містить наступні вершини , тож ми можемо просто перевірити, знаходяться в цій множині чи ні для перевірки чи є ребро мостом.
Примітки
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Розділ 22: Елементарні алгоритми на графах. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Tarjan, R. Endre (1974), A note on finding the bridges of a graph, Information Processing Letters, 2 (6): 160—161, doi:10.1016/0020-0190(74)90003-9, MR 0349483.
Посилання
- Bridges and Articulation points Algorithm на YouTube
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv mist rebro vidalennya yakogo zbilshuye kilkist komponent zv yaznosti abo inakshe kazhuchi vidokremlyuye pidgraf Rivnoznachne viznachennya rebro ye mostom todi i tilki todi koli vono ne ye chastinoyu bud yakogo ciklu Graf iz 6 mostami poznacheni chervonim Podvijne pokrittya ciklamiGrafi 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 mostivPershij algoritm dlya znahodzhennya mostiv v zv yaznomu grafi za linijnij chas O V E displaystyle O V E buv vidnajdenij Robertom Tardzhanom v 1974 roci Algoritm skladayetsya z nastupnih krokiv Znajti kistyakove derevo dlya G displaystyle G Stvoriti derevo T displaystyle T z korenem z kistyakovogo dereva Obijti derevo T displaystyle T v pryamomu poryadku i pronumerovati vershini Teper nomeri batkivskih vershin menshi za nomeri nashadkiv Dlya kozhnoyi vershini v displaystyle v pri obhodi u pryamomu poryadku robimo Pidrahovuyemo kilkist nashadkiv N D v displaystyle ND v dlya ciyeyi vershini Pidrahovuyemo L v displaystyle L v i H v displaystyle H v Dlya kozhnoyi w displaystyle w takoyi sho v w displaystyle v to w yaksho L w w displaystyle L w geq w i H w lt w N D w displaystyle H w lt w ND w todi rebro v w displaystyle v w bude mostom Viznachennya Rebro poza derevom mizh v displaystyle v i w displaystyle w poznachayetsya v w displaystyle v w Rebro v derevi z batkivskoyu v displaystyle v poznachayetsya v w displaystyle v to w N D v 1 v w N D w displaystyle ND v 1 sum v to w ND w de v displaystyle v batkivska vershina dlya w displaystyle w N D v displaystyle ND v 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 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 L v displaystyle L v i H v displaystyle H v poznachki vershin z najmenshoyu i najbilshoyu poznachkoyu obhodu pryamogo poryadku dosyazhnih z v displaystyle v prohodom po pidderevu z korenem u v displaystyle v razom z shonajbilshe odnim rebrom ne v derevi Rebro v w displaystyle v to w ye mostom todi i tilki todi koli z piddereva z korenem u w displaystyle w nemozhlivo potrapiti u vershinu yaka ne ye nashadkom w displaystyle w Ce legko pereviriti bo pidderevo z korenem u w displaystyle w 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 tozh mi mozhemo prosto pereviriti znahodyatsya L w H w displaystyle L w H w v cij mnozhini chi ni dlya perevirki chi ye rebro mostom PrimitkiTomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 Rozdil 22 Elementarni algoritmi na grafah Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Tarjan R Endre 1974 A note on finding the bridges of a graph Information Processing Letters 2 6 160 161 doi 10 1016 0020 0190 74 90003 9 MR 0349483 Posilannya Bridges and Articulation points Algorithm na YouTube Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi