Ikki tomonlama grafik - Bidirected graph

Ikki tomonlama grafadagi qirralarning har xil turlari

In matematik domeni grafik nazariyasi, a ikki tomonlama grafik (tomonidan kiritilgan Edmonds va Jonson 1970 yil )[1] a grafik unda har bir chetga har bir uchida mustaqil yo'nalish (yoki yo'nalish yoki o'q) beriladi. Shunday qilib, uch tomonlama qirralar mavjud: o'qlar tashqi tomonga, vertikal tomonga, ikkala uchiga qarab yo'naltirilgan; ikkala o'q ham vertikallardan uzoqda, ichkariga ishora qiladiganlar; va bitta o'q o'z tepasidan uzoqlashib, qarama-qarshi tomonga, boshqalari esa birinchi tomonga qarama-qarshi tomondan va o'z vertikaliga qarab yo'naltirilgan o'qlar.

Ushbu uch turdagi qirralarni navbati bilan chaqirish mumkin, haddan tashqari holatga keltirildi, ichkariga kirganva yo'naltirilgan. "Yo'naltirilgan" qirralar a dagi oddiy yo'naltirilgan qirralar bilan bir xil yo'naltirilgan grafik; Shunday qilib, yo'naltirilgan grafik - bu ikki tomonlama grafikaning maxsus turi.

Ba'zan faqat bitta uchi bo'lgan qirralarning bo'lishi kerak (yarim qirralar); bular faqat bitta o'qni oladi. Uchlari bo'lmagan chekka (a bo'sh chekka) o'qlari yo'q. Yarim ham, bo'shashmasdan ham bo'lmagan qirralarni chaqirish mumkin oddiy qirralar.

A nosimmetrik grafik bo'ladi er-xotin qoplama grafigi ikki tomonlama grafik.

Boshqa ma'nolar

Nosimmetrik yo'naltirilgan grafik (ya'ni har bir qirraning teskarisi ham chekka bo'lgan yo'naltirilgan grafik) ba'zan "ikki tomonlama grafik" deb ham ataladi.[2]

Shuningdek qarang

Adabiyotlar

  1. ^ Edmonds, Jek; Jonson, Ellis L. (1970), "Matching: chiziqli dasturlarning yaxshi echilgan klassi", Kombinatoriya tuzilmalari va ularning qo'llanilishi: Kalgari simpoziumi materiallari, 1969 yil iyun, Nyu-York: Gordon va buzilish. Qayta nashr etilgan Kombinatorial optimallashtirish - Evrika, siz qisqarasiz!, Springer-Verlag, Kompyuter fanidan ma'ruza eslatmalari 2570, 2003, 27-30 betlar, doi:10.1007/3-540-36478-1_3.
  2. ^ Mehlxorn, Kurt; Sanders, Piter (2008), Algoritmlar va ma'lumotlar tuzilishi: asosiy vositalar qutisi, Springer Science & Business Media, 49 va 170–171 betlar, ISBN  978-3-540-77978-0