Кіріспе

Математикада, әсіресе комбинаторикада, жиынтардың бір отбасы берілген, бұл жерде C жиыны деп аталады. Көлденең қима (немесе көлденең) – бұл жиынның әрбір мүшесінен дәл бір элементті қамтитын жиын. Егер жиын отбасының жиындары өзара шектес болса, көлденең қиманың әрбір элементі C-нің дәл бір мүшесіне сәйкес келеді (сол жиынның мүшесі болатын). Егер бастапқы жиындар шектес болмаса, көлденең қиманы анықтаудың екі мүмкіндігі бар:

Бір нұсқасы – көлденең қимадан C жиынына f биекциясы бар, онда көлденең қиманың әрбір x элементі f(x) жиынының мүшесі болады. Бұл жағдайда көлденең қима ерекше өкілдер жүйесі (SDR) деп те аталады. Екінші, сирек қолданылатын нұсқа, көлденең қима элементтері мен C жиындары арасында бір-бірге сәйкестік талабын қоймайды. Бұл жағдайда өкілдер жүйесінің мүшелері міндетті түрде әртүрлі болмайды. Компьютер ғылымында көлденең қиманы есептеу бірнеше қолданбалы салаларда пайдалы, ал жиынтардың кіріс отбасы көбінесе гиперграф ретінде сипатталады.

Барлығы және саны

SDR-ді зерттеудегі негізгі сұрақ – SDR-дің болуы мүмкін бе, болмайды ма. Холлдың үйлесімділік теоремасы, кейбіреуі бір-бірін кесіп өтетін жиынтықтардың шекті жиындығы үшін, көлденеңнің болуына қажетті және жеткілікті шарттарды келтіреді. Бұл шартқа сәйкес, әрбір k бүтін саны үшін, k жиынтықтың кез келген тобында кем дегенде k түрлі элемент болуы керек. Теорема. S1, S2, …, Sm жиындарынан тұратын жиынды қарастырайық, мұнда k = 1, 2, …, m үшін жиындықта кем дегенде k элемент бар, сондай-ақ 1, 2, …, m сандарының барлық k комбинациясы үшін де осы шарт орындалады. Егер t ≤ m болса, онда жиындықта кем дегенде t! SDR болады, ал егер t > m болса, онда жиындықта кем дегенде t! / (t – m)! SDR болады.

Сәйкестікті және жабуды анықтау

Біреу екі жақты граф құрастыра алады, онда бір жағындағы төбелері жиынтар, екінші жағындағы төбелері элементтер, ал қабырғалары жиынды оның құрамындағы элементтермен байланыстырады. Одан кейін, көлденең (ерекшеленген өкілдер жүйесі ретінде анықталған) осы графтағы толық шайқасқа тең. Сондай-ақ, гиперграф құрастыруға болады, онда төбелер элементтер, ал гиперқабырғалар жиындар болып табылады. Одан кейін, көлденең (қажетті түрде ерекшеленбеген өкілдер жүйесі ретінде анықталған) гиперграфтағы төбелік жабу болып табылады.

Мысалдар

Топтар теориясында, G тобының H кіші тобы берілгенде, оң (сәйкесінше сол) көлденең – H-ның әрбір оң (сәйкесінше сол) косетінен дәл бір элементті қамтитын жиын. Бұл жағдайда "жиындар" (косеттер) өзара бөлінген, яғни косеттер топтың бөлінісін құрайды. Бұрынғы мысалдың ерекше жағдайы ретінде, егер топтардың тікелей көбейтіндісі берілсе, онда H, K косеттері үшін көлденең болады.

Жалпы алғанда, кез келген эквиваленттік қатынас кез келген жиынға бөлініс тудыратындықтан, әрбір эквиваленттік класстан кез келген өкілді таңдау көлденеңді құрайды. Бөлініске негізделген көлденеңнің тағы бір мысалы, функцияның (жинақтар теориясы) ядросы деп аталатын эквиваленттік қатынасты қарастырғанда пайда болады. Бұл функция, X доменін эквиваленттік классқа бөліп, f арқылы сыныптағы барлық элементтерді бірдей мәнге бейнелейтін доменнің бөлінісі ретінде анықталады. Егер f инъективті болса, онда f үшін тек бір ғана көлденең болады. Ал f инъективті болмаған жағдайда, T көлденеңін бекіту, T және f-тің кескіні арасындағы бір-бірге сәйкестікке әкеледі, бұл әрі қарай деп белгіленеді. Осыған байланысты, барлық z үшін функция жақсы анықталған, мұнда x – T-дегі бірегей элемент; сонымен қатар, g-ді (қажетті түрде бірегей емес) кеңейтуге болады, сондықтан ол f-тің бүкіл кодоменінде анықталады, z, f кескінінен тыс болғанда g(z) үшін кез келген мәнді таңдау арқылы. g осылайша анықталғанын тексеру үшін қарапайым есептеу , бұл толық түрлендіру жарты тобы тұрақты жарты топ екендігінің дәлелі (егер f домені мен кодомені бірдей болса). g, f үшін (қажетті түрде бірегей емес) квази-инверс ретінде әрекет етеді; жартылай топтар теориясында бұл жай ғана инверс деп аталады. Дегенмен, жоғарыда аталған қасиетке ие кез келген g үшін "қос" теңдеу дұрыс болмауы мүмкін екеніне назар аударыңыз. Алайда, егер біз деп белгілесек, онда f, h-ның квази-инверсі болады, яғни .

Жалпы көлденең

A және B жиындарының ортақ көлденеңі (еріде) – A және B жиындарының екеуінің де көлденеңі болатын жиын. A және B жиындарының ортақ көлденеңі бар, егер және тек қана егер кез келген үшін

Жалпылау

Қисма көлденең – жиынның әрбір мүшесінен ең көп дегенде бір элементті қамтитын жиын, немесе (тұжырымның қатаң түрінде) жиыннан C-ге инъекциясы бар жиын. Шекті жиынның C көлденеңдері матроидтың негізгі жиындарын құрайды, C көлденең матроидін. Көлденең матроидтың тәуелсіз жиындары – C көлденеңдері.

Тәуелсіз көлденең (сондай-ақ, «радуга тәуелсіз жиын» немесе «тәуелсіз өкілдер жүйесі» деп аталады) – графтың тәуелсіз жиыны болып табылатын көлденең. Айырмашылықты түсіндіру үшін, m кафедрасы бар факультетті қарастырайық, онда факультет деканы әр кафедрадан бір мүшеден тұратын m мүшелі комитет құруды қалайды. Мұндай комитет – көлденең. Бірақ енді, кейбір профессорлық-оқытушылар құрамы бір-бірін ұнатпайды және комитетте бірге отыруға келіспейді делік. Бұл жағдайда комитет тәуелсіз көлденең болуы керек, онда негізгі граф «ұнатпау» қатынастарын сипаттайды. Көлденең тұжырымдаманың тағы бір жалпылауы – C-дің әрбір мүшесімен бос емес қиылысы бар жиын болады. Соңғысының мысалы – Бернштейн жиыны, ол C-дің әрбір жиынымен бос емес қиылысы бар жиын ретінде анықталады, бірақ C жиынын қамтымайды, мұнда C – топологиялық поляк кеңістігінің барлық тұйық жиындарының жиыны. Тағы бір мысал ретінде, егер C проективті жазықтықтың барлық түзулерінен тұрса, онда осы жазықтықтағы тоқтату жиыны – әр түзуді қиып өтетін, бірақ түзуді қамтымайтын нүктелер жиыны болады.

Категориялық теория

Категория теориясының тілінде, өзара толық ажыратылған жиындар жинағының көлденең қиылысы – осы жинақ тудырған бөлу картасының қимасы.

Есептеу күрделілігі

Жинақтардың кіріс отбасының барлық көлденеңін табудың есептеу күрделілігі, әсіресе санамалау алгоритмдері шеңберінде зерттелді.