Delta-matroid - Delta-matroid

Matematikada a delta-matroid yoki B-matroid a to'plamlar oilasi ning aksiyomini umumlashtiruvchi almashinuv aksiomasiga bo'ysunish matroidlar. Bo'sh bo'lmagan to'plamlar guruhi, agar har ikki to'plam uchun bo'lsa, bu delta-matroid ${ displaystyle E}$ va ${ displaystyle F}$ oilada va har bir element uchun ${ displaystyle e}$ ularning ichida nosimmetrik farq ${ displaystyle E uchburchak F}$, mavjud ${ displaystyle f in E uchburchak F}$ shu kabi ${ displaystyle E triangle {e, f }}$ oilada. Matroidning asosiy to'plamlari uchun tegishli almashinuv aksiomasi qo'shimcha ravishda talab qilinadi ${ displaystyle e in E}$ va ${ displaystyle f in F}$, buni ta'minlash ${ displaystyle E}$ va ${ displaystyle F}$ bir xil kardinallikka ega. Delta-matroid uchun ikkala elementning ikkalasi ham ikkala to'plamga tegishli bo'lishi mumkin va ikkala elementning teng bo'lishiga ham ruxsat beriladi.^[1]Muqobil va ekvivalent ta'rifi shundaki, to'plamlar oilasi delta-matroid hosil qiladi qavariq korpus uning ko'rsatkich vektorlari (a ning analogi matroid politop ) har bir qirralarning uzunligi bitta yoki bo'lgan xususiyatga ega ikkitadan kvadrat ildiz.

Delta-matroidlar 1987 yilda André Bouchet tomonidan aniqlangan.^[2]Algoritmlari matroid kesishishi va matroid parite muammosi delta-matroidlarning ayrim holatlariga ham kengaytirilishi mumkin.^[3][4]

Delta-matroidlardan o'rganish uchun ham foydalanilgan cheklov qoniqish muammolari.^[5] Maxsus holat sifatida hatto delta-matroid barcha deltalar juft sonli elementlarga ega bo'lgan delta-matroid yoki barcha to'plamlar toq sonli elementlarga ega. Agar cheklov qoniqish muammosi a Mantiqiy o'zgaruvchi planar grafaning har bir chetida va agar grafaning har bir tepasiga tushgan qirralarning o'zgaruvchilari tekis delta-matroidga tegishli bo'lishi cheklangan bo'lsa (ehtimol har bir vertex uchun har xil, hatto delta-matroid ham bo'lishi mumkin), unda muammo bo'lishi mumkin ichida hal qilindi polinom vaqti. Ushbu natija, polinomlar vaqtida echilishi mumkin bo'lgan planli mantiqiy cheklashlarni qondirish muammolarini tavsiflashda muhim rol o'ynaydi.^[6]

Adabiyotlar