Delta-matroid - Delta-matroid

Математикада а дельта-матроид немесе Roid-матроид Бұл жиынтықтар отбасы аксиомасын жалпылайтын алмасу аксиомасына бағыну матроидтер. Бос емес жиынтықтар тобы - бұл әрбір екі жиынға арналған, егер дельта-матроид ${ displaystyle E}$ және ${ displaystyle F}$ отбасында және әрбір элемент үшін ${ displaystyle e}$ оларда симметриялық айырмашылық ${ displaystyle E үшбұрышы F}$ бар, бар ${ displaystyle f in E үшбұрышы F}$ осындай ${ displaystyle E triangle {e, f }}$ отбасында. Матроидтың базалық жиынтығы үшін сәйкес келетін аксиома қосымша қажет ${ displaystyle e in E}$ және ${ displaystyle f in F}$ , мұны қамтамасыз ету ${ displaystyle E}$ және ${ displaystyle F}$ бірдей күшке ие. Дельта-матроид үшін екі элементтің кез-келгені екі жиынның біріне тиесілі болуы мүмкін, сонымен қатар екі элементтің тең болуына жол беріледі.^[1]Балама және эквивалентті анықтама - жиынтықтар отбасы дельта-матроид түзетіндігі дөңес корпус оның индикатор векторлары (а. аналогы матроидты политоп ) әрбір жиектің ұзындығы бір немесе болатын қасиетке ие екінің квадрат түбірі.

Дельта-матроидтарды Андре Бушет 1987 жылы анықтаған.^[2]Үшін алгоритмдер матроид қиылысы және матроид паритетінің проблемасы дельта-матроидтардың кейбір жағдайларына таралуы мүмкін.^[3]^[4]

Дельта-матроидтар зерттеу үшін де қолданылған шектеулерді қанағаттандыру проблемалары.^[5] Ерекше жағдай ретінде тіпті дельта-матроид барлық жиындарда элементтердің жұп саны болатын немесе барлық жиындарда тақ элементтер саны болатын дельта-матроид. Егер шектеулерді қанағаттандыру проблемасы а Логикалық айнымалы жазық графтың әр шетінде және егер графиктің әр шыңына түскен жиектердің айнымалылары біркелкі дельта-матроидқа (әр шың үшін әр түрлі жұп дельта-матроидаға) тиесілі болса, онда есеп шығарылуы мүмкін шешілді көпмүшелік уақыт. Бұл нәтиже полиномдық уақытта шешуге болатын жоспарлы бульдік шектеулерді қанағаттандыру мәселелерін сипаттауда шешуші рөл атқарады.^[6]

Пайдаланылған әдебиеттер

^ Чун, Каролин (2016 жылғы 13 шілде), «Delta-matroids: Origins», Matroid одағы
^ Бушет, Андре (1987), «Ашкөз алгоритм және симметриялық матроидтар», Математикалық бағдарламалау, 38 (2): 147–159, дои:10.1007 / BF02604639, МЫРЗА 0904585
^ Бушет, Андре; Джексон, Билл (2000), «Паритет жүйелері және дельта-матроид қиылысы мәселесі», Комбинаториканың электронды журналы, 7: R14: 1 – R14: 22, МЫРЗА 1741336
^ Джилин, Джеймс Ф.; Ивата, Сатору; Мурота, Казуо (2003), «Сызықтық дельта-матроид паритетінің проблемасы», Комбинаторлық теория журналы, B сериясы, 88 (2): 377–398, дои:10.1016 / S0095-8956 (03) 00039-X, МЫРЗА 1983366
^ Федер, Томас; Форд, Даниэль (2006), «Дельта-матроид қиылысы арқылы екі жақты логикалық шектеулерді қанағаттандыру классификациясы», Дискретті математика бойынша SIAM журналы, 20 (2): 372–394, CiteSeerX 10.1.1.124.8355, дои:10.1137 / S0895480104445009, МЫРЗА 2257268
^ Казда, Александр; Колмогоров, Владимир; Ролинек, Михал (желтоқсан 2018 ж.), «Тіпті дельта-матроидтар және жазықтық Бульдік СҚҚ-ның күрделілігі», Алгоритмдер бойынша ACM транзакциялары, 15 (2): 22:1–22:33, arXiv:1602.03124, дои:10.1145/3230649

[chun-1] Чун, Каролин (2016 жылғы 13 шілде), «Delta-matroids: Origins», Matroid одағы

[bouchet-2] Бушет, Андре (1987), «Ашкөз алгоритм және симметриялық матроидтар», Математикалық бағдарламалау, 38 (2): 147–159, дои:10.1007 / BF02604639, МЫРЗА 0904585

[bj-3] Бушет, Андре; Джексон, Билл (2000), «Паритет жүйелері және дельта-матроид қиылысы мәселесі», Комбинаториканың электронды журналы, 7: R14: 1 – R14: 22, МЫРЗА 1741336

[gim-4] Джилин, Джеймс Ф.; Ивата, Сатору; Мурота, Казуо (2003), «Сызықтық дельта-матроид паритетінің проблемасы», Комбинаторлық теория журналы, B сериясы, 88 (2): 377–398, дои:10.1016 / S0095-8956 (03) 00039-X, МЫРЗА 1983366

[ff-5] Федер, Томас; Форд, Даниэль (2006), «Дельта-матроид қиылысы арқылы екі жақты логикалық шектеулерді қанағаттандыру классификациясы», Дискретті математика бойынша SIAM журналы, 20 (2): 372–394, CiteSeerX 10.1.1.124.8355, дои:10.1137 / S0895480104445009, МЫРЗА 2257268

[kkr-6] Казда, Александр; Колмогоров, Владимир; Ролинек, Михал (желтоқсан 2018 ж.), «Тіпті дельта-матроидтар және жазықтық Бульдік СҚҚ-ның күрделілігі», Алгоритмдер бойынша ACM транзакциялары, 15 (2): 22:1–22:33, arXiv:1602.03124, дои:10.1145/3230649

[1]

[2]

[3]

[4]

[5]

[6]