Matroid бөлімі - Partition matroid

Математикада а matroid бөлімі немесе бөлуге арналған матроид Бұл матроид қалыптасқан тікелей сома туралы біркелкі матроидтар.[1] Ол элементтер әртүрлі санаттарға бөлінетін базалық жиынтықта анықталады. Әр санат үшін а бар сыйымдылықтың шектеулілігі - осы санаттан рұқсат етілген элементтердің максималды саны. Бөлім матроидінің дербес жиынтықтары дегеніміз - бұл әр категория үшін осы санаттағы элементтер саны ең көп дегенде категорияның сыйымдылығы болатын жиынтықтар.

Ресми анықтама

Келіңіздер жиынтығы болуы бөлінбеген жиынтықтар («санаттар»). Келіңіздер бүтін сандар болуы керек («қуаттылықтар»). Ішкі жиынды анықтаңыз әр индекс үшін «тәуелсіз» болу , . Осы шартты қанағаттандыратын жиындар а-ның тәуелсіз жиынтықтарын құрайды матроид, а деп аталады matroid бөлімі.

Жинақтар деп аталады блоктар немесе санаттар матроидтің бөлімі.

A негіз matroid бөлімнің бөлігі - бұл барлық блоктармен қиылысы дәл өлшемі бар . A тізбек матроид - бұл бір блоктың жиынтығы дәл өлшемімен . The дәреже матроидтің .[2]

Әрқайсысы біркелкі матроид бұл жалғыз блокты, қалқандық бөлім туралы элементтерімен және . Кез-келген матроид - бұл әр блок үшін біркелкі матроидтар жиынтығының тікелей қосындысы.

Кейбір жарияланымдарда бөлімнің матроид ұғымы шектеулі түрде анықталады . Осы неғұрлым шектеулі анықтамаға бағынатын бөлімдер болып табылады көлденең матроидтар олардың блоктары бойынша бөлінген жиынтықтар тобының.[3]

Қасиеттері

Біртекті матроидтар сияқты, олардан түзіледі қосарлы матроид бөлімнің матроид бөлігі де матроидтік бөлім болып табылады және әрқайсысы кәмелетке толмаған бөлу матроид бөлігі де матроидтік бөлім болып табылады. Бөлім матроидтарының тікелей қосындылары, сонымен қатар, бөлу матроидтары болып табылады.

Сәйкестік

A максималды сәйкестік графикте - шеткі нүкте екі шетпен бірдей болмау шартымен мүмкіндігінше үлкен жиектер жиынтығы. Ішінде екі жақты граф екі бөліммен , шеттер жиыны соңғы нүктені екі шетпен бөліспейтін шартты қанағаттандырады - бұл шегі үшін бір блогы бар матроидтің жеке жиынтығы және сандардың әрқайсысымен бірге біреуіне тең. Шеттер жиыны екі шеткіде де соңғы нүктені бөліспейтін шартты қанағаттандырады matroid екінші бөлімнің дербес жиынтығы. Демек, екі жақты максималды сәйкестендіру а ретінде ұсынылуы мүмкін матроид қиылысы осы екі матроид.[4]

Көбінесе графиктің сәйкес келуі екі матроидтың қиылысы ретінде ұсынылуы мүмкін, егер графикадағы тақ тақталардың әрқайсысы екі немесе одан да көп дәрежелі екі төбеден тұратын үшбұрыш болса.[5]

Клик кешендері

A клика кешені - бұл график шыңдарының жиынтығы толық субографиясын тудыратын . Клика кешені матроидты құрайды, егер ол болса Бұл толық көпжақты график, және бұл жағдайда алынған матроид бөлімді матроид болып табылады. Кликалық кешендер дегеніміз - қалыптасқан жүйелер қиылыстар матроидтармен бөлінетін отбасылар .[6]

Санақ

Жиынтығы бойынша анықталуы мүмкін бөлу матроидтарының саны таңбаланған элементтер, үшін , болып табылады

1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (реттілік A005387 ішінде OEIS ).

The экспоненциалды генерациялау функциясы осы реттілік болып табылады .[7]

Әдебиеттер тізімі

  1. ^ Рецки, А. (1975), «Қосымшалары бар бөлуге арналған матроидтар туралы», Шексіз және шексіз жиынтықтар (Коллок., Кештели, 1973; П. Ердостың 60-жылдығына арналған), т. III, Коллок. Математика. Soc. Янос Боляй, 10, Амстердам: Солтүстік-Голландия, 1169–1179 бет, МЫРЗА  0389630.
  2. ^ Лоулер, Евгений Л. (1976), Комбинаторлық оңтайландыру: желілер және матроидтер, Райнхарт және Уинстон, Нью-Йорк: Холт, б. 272, МЫРЗА  0439106.
  3. ^ Мысалы, қараңыз Кашивабара, Окамото және Юно (2007). Лоулер (1976) кеңірек анықтаманы қолданады, бірақ шектеу көптеген қосымшаларда пайдалы.
  4. ^ Пападимитриу, Христос Х.; Штайглиц, Кеннет (1982), Комбинаторлық оңтайландыру: алгоритмдер және күрделілік, Englewood Cliffs, NJ: Prentice-Hall Inc., 289–290 б., ISBN  0-13-152462-3, МЫРЗА  0663728.
  5. ^ Фекете, Шандор П .; Фирла, Роберт Т .; Spille, Bianca (2003), «Матроидтардың қиылысы ретінде сәйкестікті сипаттайтын», Операцияларды зерттеудің математикалық әдістері, 58 (2): 319–329, arXiv:математика / 0212235, дои:10.1007 / s001860300301, МЫРЗА  2015015.
  6. ^ Кашивабара, Кенджи; Окамото, Йосио; Юно, Такеаки (2007), «Клика кешендерінің матроидтік көрінісі», Дискретті қолданбалы математика, 155 (15): 1910–1929, дои:10.1016 / j.dam.2007.05.004, МЫРЗА  2351976. Дәл сол нәтижелер үшін қосымша жиынтық түрінде, кликтердің орнына тәуелсіз жиынтықтар қолданылады, қараңыз Тышкевич, Р.И.; Урбанович, О. П .; Зверович, I. È. (1989), «Графиктің матроидалды ыдырауы», Комбинаторика және график теориясы (Варшава, 1987), Банах орталығы баспасы, 25, Варшава: PWN, 195–205 б., МЫРЗА  1097648.
  7. ^ Рецки, А. (1974), «Бөлімді матроидтарды санау», Studia Scientiarum Mathematicarum Hungarica, 9: 247–249 (1975), МЫРЗА  0379248.