Ko'prik (grafik nazariyasi) - Bridge (graph theory)

16 ta tepalik va 6 ta ko'prikli grafik (qizil rang bilan belgilangan)

Ko'prik qirralari bo'lmagan yo'naltirilgan ulangan grafik

Yilda grafik nazariyasi, a ko'prik, istmus, zamonaviy, yoki yoy kesilgan bu chekka a grafik ularning o'chirilishi grafika sonini ko'paytiradi ulangan komponentlar.^[1] Bunga teng ravishda, chekka ko'prikdir, agar u hech qanday narsada bo'lmasa tsikl. Bog'langan grafika uchun ko'prik noyob tarzda a ni aniqlay oladi kesilgan. Grafik deyiladi ko'priksiz yoki istmussiz agar ko'prik bo'lmasa.

"Ko'prik" ning yana bir ma'nosi bu atamada paydo bo'ladi subgraf ko'prigi. Agar H ning subgrafasi G, a ko'prigi H yilda G ning maksimal subgrafasi G tarkibida mavjud emas H va ajratilmaydi H.

Daraxtlar va o'rmonlar

Bilan grafik ${ displaystyle n}$ tugunlarda ko'pi bo'lishi mumkin ${ displaystyle n-1}$ ko'priklar, chunki qo'shimcha qirralarning qo'shilishi tsiklni yaratishi kerak. To'liq grafikalar ${ displaystyle n-1}$ ko'priklar to'liq daraxtlar va har bir chekka ko'prik bo'lgan grafikalar aynan shu o'rmonlar.

Har bir yo'naltirilmagan grafada ekvivalentlik munosabati ikkita tepalik bir-biriga bog'lab turadigan tepaliklarda, ularni bog'laydigan ikkita qirrali-ajratilgan yo'llar mavjud bo'lganda. (Har bir tepalik o'zi bilan bir xil, ammo baribir chekka-bo'linmagan ikkita uzunlik-nol yo'llari bilan bog'liq.) Ushbu munosabatlarning ekvivalentligi sinflari deyiladi 2 chekka bilan bog'langan komponentlar, va grafika ko'priklari aniq uchlari turli xil tarkibiy qismlarga tegishli bo'lgan qirralardir. The ko'prikli daraxt grafikning har bir noan'anaviy komponenti uchun tepalik va har bir ko'prik uchun chekkasi mavjud.^[2]

Vertikal ulanish bilan bog'liqlik

Ko'priklar tushunchasi bilan chambarchas bog'liq artikulyatsiya tepalari, boshqa tepaliklar juftligi orasidagi har bir yo'lga tegishli tepaliklar. Ko'prikning ikkita so'nggi nuqtasi, agar ular 1 darajaga ega bo'lmasalar, artikulyatsiya cho'qqisidir, ammo ko'prik bo'lmagan chekkada ikkita nuqta sifatida ikkita vertikal tepalikka ega bo'lishi mumkin. Xuddi shu tarzda, ko'priksiz grafikalar 2 qirrali bog'langan, vertikal vertikal bo'lmagan grafikalar 2-vertex bilan bog'langan.

A kubik grafik, har bir kesilgan tepalik - bu kamida bitta ko'prikning so'nggi nuqtasi.

Ko'priksiz grafikalar

A ko'priksiz grafik ko'priklarga ega bo'lmagan grafik. Ekvivalent shartlar - bu har biri ulangan komponent grafikning an ochiq quloq parchalanishi,^[3] har bir bog'langan komponent 2 chekka ulangan, yoki (tomonidan Robbins teoremasi ) har bir bog'langan komponentda a kuchli yo'nalish.^[3]

Ko'priklarni o'z ichiga olgan muhim ochiq muammo bu tsiklning ikki qavatli gipotezasi, sababli Seymur va Sekeres (1978 va 1979 yillarda, mustaqil ravishda), bu har bir ko'priksiz grafada har bir qirrasini to'liq ikki marta o'z ichiga olgan oddiy tsikllarning ko'p to'plamini tan olishini ta'kidlaydi.^[4]

Tarjanning ko'prik topish algoritmi

Birinchi chiziqli vaqt ko'priklarni grafikda topish algoritmi tomonidan tasvirlangan Robert Tarjan 1974 yilda.^[5] U quyidagi amallarni bajaradi:

A ni toping o'rmon o'rmoni ning ${ displaystyle G}$
Ildizli o'rmon yarating ${ displaystyle F}$ daraxtdan
O'rmonni aylanib o'ting ${ displaystyle F}$ yilda oldindan buyurtma va tugunlarni raqamlash. O'rmondagi ota-ona tugunlari endi bolalar tugunlariga qaraganda kamroq songa ega.
Har bir tugun uchun ${ displaystyle v}$ $v$ oldindan buyurtmada (har bir tugunni oldindan buyurtma raqami yordamida belgilash), quyidagilarni bajaring:
- O'rmon avlodlari sonini hisoblang ${ displaystyle ND (v)}$ bu tugun uchun, o'z farzandlarining avlodlari yig'indisiga bitta qo'shib.
- Hisoblash ${ displaystyle L (v)}$ , eng past darajadagi oldindan buyurtma yorlig'i ${ displaystyle v}$ oxirgi chekkasidan boshqa hamma ildiz otilgan daraxt ichida qoladigan yo'l bilan ${ displaystyle v}$ . Bu oldindan buyurtma yorlig'idan iborat to'plamning minimal qiymati ${ displaystyle v}$ ning qiymatlari ${ displaystyle L (w)}$ ning bolalar tugunlarida ${ displaystyle v}$ va tugunlarning oldindan buyurtma qilingan yorliqlari ${ displaystyle v}$ tegishli bo'lmagan qirralar bo'yicha ${ displaystyle F}$ .
- Xuddi shunday, hisoblash ${ displaystyle H (v)}$ , eng so'nggi oldindan buyurtma yorlig'i oxirigacha bo'lgan hamma daraxt tagida joylashgan yo'l orqali erishiladi ${ displaystyle v}$ . Bu oldindan buyurtma yorlig'idan iborat to'plamning maksimal miqdori ${ displaystyle v}$ ning qiymatlari ${ displaystyle H (w)}$ ning bolalar tugunlarida ${ displaystyle v}$ va tugunlarning oldindan buyurtma qilingan yorliqlari ${ displaystyle v}$ tegishli bo'lmagan qirralar bo'yicha ${ displaystyle F}$ .
- Har bir tugun uchun ${ displaystyle w}$ ota tuguni bilan ${ displaystyle v}$ , agar ${ displaystyle L (w) = w}$ va ${ displaystyle H (w)$ keyin chekka ${ displaystyle v}$ ga ${ displaystyle w}$ ko'prik.

Zanjir dekompozitsiyalari bilan ko'prikni topish

Ko'prikni topishning juda oddiy algoritmi^[6] foydalanadi zanjir dekompozitsiyalari.Zanjir dekompozitsiyalari nafaqat grafikaning barcha ko'priklarini hisoblashga imkon beradi, balki ularga imkon beradi o'qing har bir kesilgan tepalik ning G (va kesilgan daraxt ning G), 2-qirrali va 2-vertex-ulanishni sinash uchun umumiy asos (bu chiziqli vaqtli 3-qirrali va 3-vertex-ulanish sinovlariga qadar).

Zanjir dekompozitsiyalari - bu DFS daraxtiga bog'liq bo'lgan maxsus quloq dekompozitsiyalari T ning G va juda sodda tarzda hisoblash mumkin: har bir tepalik ko'rilmagan deb belgilansin. Har bir tepalik uchun v ko'tarilishida DFS - 1-son ...n, sodir bo'lgan har qanday chekkadan (ya'ni DFS daraxtida bo'lmagan har bir chetdan) o'ting v va yana ildizlarigacha daraxt qirralari yo'lidan boring T, tashrif buyurgan deb belgilangan birinchi tepada to'xtash. Bunday o'tish paytida har bir o'tgan vertex tashrif buyurgan deb belgilanadi. Shunday qilib, traversal eng kechi bilan to'xtaydi v va v bilan boshlangan yo yo'naltirilgan yo'lni yoki tsiklni hosil qiladi; biz bu pator tsiklini a deb ataymiz zanjir. The menUshbu protsedura bo'yicha topilgan zanjir deb ataladi C_men. C = C₁, C₂,... keyin a zanjirning parchalanishi ning G.

Keyin quyidagi tavsiflar imkon beradi o'qing ning bir nechta xususiyatlari G dan C barcha ko'priklarni o'z ichiga olgan holda samarali G.^[6] Ruxsat bering C oddiy bog'langan grafikning zanjirli dekompozitsiyasi bo'ling G = (V, E).

G agar zanjirlar bo'lsa, faqat 2 qirraga ulanadi C bo'lim E.
Bir chekka e yilda G agar ko'prik bo'lsa va faqat shunday bo'lsa e har qanday zanjirda mavjud emas C.
Agar G 2 qirraga ulangan, C bu quloq parchalanishi.
G agar faqat shunday bo'lsa, 2 vertex bilan bog'langan G minimal darajaga ega 2 va C₁ ning yagona tsikli C.
Tepalik v 2 qirraga ulangan grafikada G va agar shunday bo'lsa, kesilgan tepalikdir v - tsiklning birinchi tepasi C - C₁.
Agar G 2 vertex bilan bog'langan, C bu ochiq quloq parchalanishi.

Bridgehead

Bridgeheads Grafik nazariyasida A va B mintaqalarini ajratuvchi ko'prikning

Bog'langan grafik uchun ${ displaystyle G}$ , ko'prik ${ displaystyle e}$ ajratishi mumkin ${ displaystyle G}$ mintaqaga ${ displaystyle A}$ va mintaqa ${ displaystyle B}$ , ya'ni kesilgan ${ displaystyle (A, B)}$ . Tepaliklar ${ displaystyle alpha in e cap A}$ va ${ displaystyle beta in e cap B}$ ning ikkita ko'priklari ${ displaystyle A}$ va ${ displaystyle B}$ . ${ displaystyle alpha}$ plyonkaga yaqin ${ displaystyle A}$ va uzoq-ko'prik ${ displaystyle B}$ , va aksincha uchun ${ displaystyle beta}$ .

Shuningdek qarang

Izohlar

^ Bollobas, Bela (1998), Zamonaviy grafik nazariyasi, Matematikadan magistrlik matnlari, 184, Nyu-York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, JANOB 1633290.
^ Westbrook, Jeffery; Tarjan, Robert E. (1992), "On-layn rejimida ko'prik bilan bog'langan va ikkita ulangan qismlarga xizmat ko'rsatish", Algoritmika, 7 (5–6): 433–464, doi:10.1007 / BF01758773, JANOB 1154584.
^ ^a ^b Robbins, H. E. (1939), "Grafiklar teoremasi, transportni boshqarish muammosiga ariza bilan", Amerika matematikasi oyligi, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz / 101517.
^ Jaeger, F. (1985), "Ikkita qopqoqli gipoteza tsikli", Diskret matematika yilnomalari 27 - Grafadagi tsikllar, Shimoliy-Gollandiyalik matematik tadqiqotlar, 27, 1-12 betlar, doi:10.1016 / S0304-0208 (08) 72993-1.
^ Tarjan, R. Endre (1974), "Grafik ko'priklarini topish to'g'risida eslatma", Axborotni qayta ishlash xatlari, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9, JANOB 0349483.
^ ^a ^b Shmidt, Jens M. (2013), "2-vertex- va 2-chekka-ulanish bo'yicha oddiy sinov", Axborotni qayta ishlash xatlari, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016 / j.ipl.2013.01.016.

[1] Bollobas, Bela (1998), Zamonaviy grafik nazariyasi, Matematikadan magistrlik matnlari, 184, Nyu-York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, JANOB 1633290.

[2] Westbrook, Jeffery; Tarjan, Robert E. (1992), "On-layn rejimida ko'prik bilan bog'langan va ikkita ulangan qismlarga xizmat ko'rsatish", Algoritmika, 7 (5–6): 433–464, doi:10.1007 / BF01758773, JANOB 1154584.

[robbins39-3] Robbins, H. E. (1939), "Grafiklar teoremasi, transportni boshqarish muammosiga ariza bilan", Amerika matematikasi oyligi, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz / 101517.

[4] Jaeger, F. (1985), "Ikkita qopqoqli gipoteza tsikli", Diskret matematika yilnomalari 27 - Grafadagi tsikllar, Shimoliy-Gollandiyalik matematik tadqiqotlar, 27, 1-12 betlar, doi:10.1016 / S0304-0208 (08) 72993-1.

[5] Tarjan, R. Endre (1974), "Grafik ko'priklarini topish to'g'risida eslatma", Axborotni qayta ishlash xatlari, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9, JANOB 0349483.

[Schmidt-6] Shmidt, Jens M. (2013), "2-vertex- va 2-chekka-ulanish bo'yicha oddiy sinov", Axborotni qayta ishlash xatlari, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016 / j.ipl.2013.01.016.

[1]

[2]

[3]

[4]

[5]

[6]