Modulli grafik - Modular graph
Yilda grafik nazariyasi, matematikaning bir bo'lagi modulli grafikalar bor yo'naltirilmagan grafikalar unda har uchtasi tepaliklar x, yva z kamida bittasi bor median vertex m(x,y,z) tegishli eng qisqa yo'llar har bir juftlik o'rtasida x, yva z.[1]Ularning nomi cheklangan ekanligidan kelib chiqadi panjara a modulli panjara agar va faqat u bo'lsa Hasse diagrammasi bu modulli grafik.[2]
Modulli grafada toq uzunlik tsikli bo'lishi mumkin emas. Uchun, agar C grafadagi eng qisqa toq tsikl, x ning tepasi Cva yz tsiklning eng chekkasi x, o'rtacha bo'lishi mumkin emas m(x,y,z), eng qisqa yo'lda yagona tepaliklar uchun yz bor y va z o'zlari, lekin ikkalasi ham eng qisqa yo'lga tegishli bo'lishi mumkin emas x yorliqsiz boshqasiga C va qisqaroq g'alati tsiklni yaratish. Shuning uchun har bir modulli grafik a ikki tomonlama grafik.[1]
Modulli grafikalar maxsus holat sifatida o'z ichiga oladi o'rtacha grafikalar, unda har uch vertikal noyob medianaga ega;[1] median grafikalar bilan bog'liq tarqatuvchi panjaralar xuddi shu tarzda modulli grafikalar modulli panjaralar bilan bog'liq. Biroq, modulli grafikalar tarkibiga boshqa kabi grafikalar ham kiradi to'liq ikki tomonlama grafikalar bu erda medianlar noyob emas: uchta tepalik bo'lganda x, yva z barchasi to'liq bipartit grafigi ikki qismining bir tomoniga tegishli, boshqa tomonidagi har bir tepalik medianadir.[2] Har bir akkord ikki tomonlama grafigi (to'liq ikki tomonlama grafikalar va ikki partiyali o'z ichiga olgan grafikalar klassi) masofadan-irsiy grafikalar ) modulli.[1]
Adabiyotlar
- ^ a b v d Modulli grafikalar, Grafika sinflari va ularning qo'shilishlari to'g'risidagi axborot tizimi, 2016-09-30.
- ^ a b Bandelt, H.-J .; Dahlmann, A .; Schütte, H. (1987), "Bipartitli grafikalarning mutlaq retraktsiyalari", Diskret amaliy matematika, 16 (3): 191–215, doi:10.1016 / 0166-218X (87) 90058-8, JANOB 0878021.