Кіріспе

Комбинаторика мен граф теориясындағы нәтиже. Математикада Холлдың үйлесімділік теоремасы, екі эквивалентті формулировкасы бар теорема. Әрбір жағдайда теорема, объектінің болуы үшін қажетті және жеткілікті шартты келтіреді: Комбинаторлық формулировка, шекті жиынтықтар жинағында көлденең кесудің болуына жауап береді – яғни, әр жиынтықтан қайталанбастан бір элементті таңдау мүмкіндігі. Холлдың шарты бойынша, жинақтағы кез келген жиынтықтар тобы үшін, олардың қамтитын жалғыз элементтердің жалпы саны, топтағы жиынтықтар санынан кем болмауы керек. Граф теориялық формулировка, шекті екібөлікті графтың толық жұптамаға ие болуына жауап береді – яғни, бір топтағы әрбір төбесін екінші топтағы жапсарлас төбемен бірегей түрде жұптау мүмкіндігі. Холлдың шарты бойынша, бір топтағы кез келген төбелер жинағының маңы тең немесе одан үлкен өлшемге ие болуы керек.

Айтылым

Болсын – жиындардың шекті жиынтығы (өзі шексіз болмауы керек, бірақ жиындар шексіз болуы мүмкін және бір жиын бірнеше рет кіруі мүмкін). Болсын – осы жиынтықтағы барлық жиындардың бірі, яғни олардың кемінде біреуіне тиесілі элементтердің жиыны. -ның трансверсалі – бұл әрбір жиыннан бір-бір элементті таңдау арқылы алынатын жиынның ішкі жиыны. Бұл ұғымды трансверсальды инъективті функцияның бейнесі ретінде анықтауға болады, мұнда әрбір үшін . Трансверсальға баламалы термин – ерекше өкілдердің жүйесі. Жиын неке шартын қанағаттандырады, егер оның кез келген ішкі жиынында оның жиындарының санынан кем емес ерекше мүшелер болса. Яғни, барлық үшін ,

Егер трансверсаль болса, онда неке шарты орындалуы керек: трансверсальді анықтау үшін қолданылатын функция оның біріндісінің сол көлемдегі ішкі жиынына бейнелейді, сондықтан бүкіл бірінді кемінде осы көлемде болуы керек. Холл теоремасы керісін де дұрыс екенін мәлімдейді:

Графикалық теориялық тұжырымдама

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

Қажеттілік

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

Жетілдігі

Контрапозитивті қарастырайық: егер толық сәйкестік болмаса, онда Холл шарты кем дегенде бір рет бұзылуы керек. дегені ең үлкен сәйкестік болсын, ал – сәйкес келмейтін кез келген төбе. төбесінен басталатын барлық кезектесетін жолдарды қарастырайық (сыртқы және ішкі жиектерді кезекпен пайдаланатын жолдар). болып белгілейік осы жолдардағы -ге жататын төбелер жиынын (өзінді қоса алғанда), ал – осы жолдардағы -ге жататын төбелер жиынын. Онда жиынындағы әр төбе сәйкестік арқылы жиынындағы төбеге сәйкес келеді, өйткені сәйкес келмейтін төбеге дейінгі кезектесетін жолды сәйкестіктің өлшемін арттыру үшін пайдалануға болады, оның әр жиегі сәйкестікке жата ма, жоқ па, дегенді ауыстыру арқылы. Сондықтан, жиынының өлшемі кем дегенде жиынындағы осы сәйкес төбелердің саны плюс сәйкес келмейтін төбе үшін біреуі. Яғни, . Бірақ әр төбе үшін , оның әр көршісі -ге жатады: -ге дейінгі кезектесетін жолды табуға болады, немесе -ге дейінгі кезектесетін жолдан сәйкес жиекті алып тастау арқылы, немесе -ге дейінгі кезектесетін жолға сәйкес келмейтін жиекті қосу арқылы. Осылайша, және , Холл шарты бұзылғандығын көрсетеді.

Комбинаторлық формула мен график-теориялық формуланың теңдестігі

Комбинаторлық тұжырымдамадағы мәселе, бірлестігі шекті жиынтықтардың шекті отбасымен анықталғанда, әр қабырғасы жиынтықты сол жиынтықтың бір элементімен байланыстыратын екібөлікті графқа түрлендіріледі. Осы графтың толық сәйкестігі – берілген жиынтықтар отбасы үшін бірегей өкілдер жүйесін анықтайды. Керісінше, кез келген екібөлікті граф бойынша, графтың төбелерінің көршілестерінің отбасын құрайтын шекті жиынтықтар отбасын анықтауға болады, мұнда осы отбасы үшін кез келген бірегей өкілдер жүйесі осы графтың толық сәйкестігіне сәйкес келеді. Осылайша, шекті жиынтықтардың шекті отбасылары үшін комбинаторлық тұжырымдама және шекті графтар үшін граф теориялық тұжырымдама эквивалентті. Сол эквиваленттілік шекті жиынтықтардың шексіз отбасыларына және белгілі бір шексіз графтарға да қолданылады. Бұл жағдайда, әр жиынның шекті болу шарты екібөлікті графтың әр төбесінің шекті дәрежеге ие болуы керек деген шартқа сәйкес келеді. Графтың төбелерінің дәрежелері шектелмеген.

Топологиялық дәлелдеу

Холл теоремасы Спернер леммасы негізінде (конструктивті емес) дәлелдене алады.

Қолданбалар

Теореманың көптеген қолданыстары бар. Мысалы, стандартты карталар жинағын, әрқайсысы 4 картадан тұратын 13 қатарға бөліп қарастырсақ, неке теоремасы әрбір қатардан бір картаны таңдауға болатынын көрсетеді, сонда таңдалған карталардың арасында әр номиналдан (Тұз, 2, 3, ..., Патша, Королева) дәл бір карта болады. Бұл екі бөлікті граф құрастыру арқылы іске асырылады, оның бір бөлігінде 13 қатар, ал екінші бөлігінде 13 номинал болады. Дәлелдің қалған бөлігі неке шартынан шығады. Кез келген реттелген екі бөлікті графтың толық сәйкестігі болады. Көбірек абстрактілі тұрғыдан алғанда, болсын – топ, ал – топтың шекті индекске ие кіші тобы. Онда неке теоремасын пайдаланып, сол жақ және оң жақ косеттер жиыны үшін көлденең болатын жиынның бар екенін көрсетуге болады. Неке теоремасы, әдетте, кез келген *n* латын тіктөртбұрышын *n+1* латын тіктөртбұрышына кеңейтуге болатынын, демек, соңғы нәтижеде латын шаршысына жеткізудің дәлелдерінде қолданылады.

Маршалл Холл-младший нұсқасы

Филип Холлдың бастапқы дәлелін мұқият қарап, Маршалл Холл кіші (Филип Холлмен ешқандай туыстық байланысы жоқ) нәтижені осылай өзгерте алды, бұл дәлелдің шексіз жиындар үшін де жұмыс істеуіне мүмкіндік берді. Бұл түрлендірілген нұсқа Филип Холлдың Неке теоремасын кеңейтеді. Егер , – (мүмкін шексіз) соны жиынтардың жиыны болса, онда оның көлденеңі бар екені, тек және ғана неке шартын орындаса ғана мүмкін.

Некелік шарт қолданылмайды

Маршалл Холл-дың мысалы, неке шарты шексіз жиындарға рұқсат етілген шексіз отбасында көлденеңнің болуын кепілдемейтінін көрсетеді. Отбасы былай болсын, , үшін. Осы шексіз отбасы үшін неке шарты орындалады, бірақ ешқандай көлденең құру мүмкін емес.

Маршалл Холл нұсқасының теориялық графтық тұжырымдамасы

Маршалл Холлдың неке теоремасын кеңейтудің графтық теориялық тұжырымын былай формулиреуге болады: А және В жиындары бар екі бөлікті граф берілген болсын. Егер граф ішінде C жиынынан D жиынына инъекция (яғни, графтың қанағаттандыратын қабырғаларын ғана пайдаланып) болса, онда B жиынының C ішкі жиыны A жиынының D ішкі жиынынан кіші немесе тең деп айтамыз. Егер графтың қарсы бағытында инъекция болмаса, онда ол граф ішінде қатаң кішірек деп айтамыз. Графтан шығару кардиналдықтарды салыстырудың стандартты түсінігіне әкелетінін ескеріңіз. Шексіз үйлесімділік теоремасы граф ішінде A жиынынан B жиынына инъекцияның бар екенін күйейді, егер және тек қана A жиынының C ішкі жиыны болмаса, онда N(C) жиыны граф ішінде C жиынынан қатаң кішірек болады. Бос емес жиындардың (жиындар санына немесе олардың өлшемдеріне қатысқан шектеулерсіз) жинағынан (қажетті түрде әртүрлі емес) бір элементті таңдау мәселесі, жалпы жағдайда, тек таңдау аксиомасы қабылданғанда ғана мүмкін болады.

Бөлшек сәйкестік нұсқасы

Графиктегі бөлшектік сәйкестік – әр қабырғаға теріс емес салмақтарды тағайындау, мұнда әр төбеге жақын қабырғалардың салмақтарының қосындысы 1-ден аспауы керек. Егер әр төбеге жақын қабырғалардың салмақтарының қосындысы дәл 1 болса, онда бөлшектік сәйкестік X-ке толық сәйкес келеді. G = (X+Y, E) екі бөлікті граф үшін келесі шарттар эквивалентті: G, X-ке толық сәйкестікті қабылдайды. G, X-ке толық бөлшектік сәйкестікті қабылдайды. Бұл тұжырым X-ке толық сәйкестіктің, X-ке толық бөлшектік сәйкестіктің ерекше жағдайы болғандықтан тікелей шығады, онда әр салмақ 1-ге (егер қабырға сәйкестікте болса) немесе 0-ге (егер болмаса) тең болады. G Холлдың үйлену шартын қанағаттандырады. Бұл тұжырым дұрыс, себебі X-тің кез келген W ішкі жиыны үшін, W төбелеріне жақын салмақтардың қосындысы |W|-ға тең, сондықтан оларға іргелес қабырғалар міндетті түрде Y-тің кем дегенде |W| төбесіне іргелес болуы керек.

Санаттық нұсқа

Холлдың шарты орындалмаған жағдайда, бастапқы теорема тек толық сәйкестіктің жоқ екенін ғана айтады, бірақ қандай ең үлкен сәйкестік бар екенін көрсетпейді. Бұл ақпаратты білу үшін бізге графтың кемшілік дәрежесі туралы түсінік қажет. Екі бөлікті граф G = (X+Y, E) берілгенде, G-нің X-ке қатысты кемшілік дәрежесі – X-тің барлық W ішкі жиындары бойынша |W| – |NG(W)| айырмасының ең жоғарғы мәні. Кемшілік дәрежесі неғұрлым жоғары болса, граф Холл шартын қанағаттандырудан соғұрлым алыс болады. Холлдың үйлесімділік теоремасын қолданып, егер екі бөлікті граф G-нің кемшілік дәрежесі d болса, онда G кем дегенде |X| – d өлшемінде сәйкестікке ие болады.

Жалпылау

Холл теоремасының кез келген графтарға (қажетті түрде екі жақты емес) жалпылануы Тютте теоремасымен беріледі. Холл теоремасының екі жақты гиперграфтарға жалпылануын гиперграфтарға арналған түрлі Холл сияқты теоремалар қамтамасыз етеді.