Кіріспе

K-дан кем жиектер алынып тасталғанда байланысын сақтайтын граф. Графтар теориясында, егер k-дан кем жиектер алынып тасталғанда граф байланыстылығын сақтайтын болса, онда ол k жиекті байланысқан граф деп аталады. Графтың жиек байланысы – графтың k жиекті байланысқан ең үлкен k мәні. Жиек байланысы және k жиекті байланысқан графтарды санау мәселесін 1869 жылы Камил Джордан зерттеген.

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

Кез келген график болсын. Егер барлық i үшін, мұндағы i = 1, 2, ..., n, G графигінің ішкі графигі байланысты болса, онда G графигі k жиекті байланысқан деп айтылады. G графигінің жиектік байланыстылығы – G графигі k жиекті байланысқан болатын k-ның ең жоғары мәні. G графигін ажырататын ең кіші жиын X – G графигіндегі ең кішкентай кесілім.

Менгер теоремасының жиектік байланыс нұсқасы, графиктердегі жиектер бойынша ажыратылған жолдар арқылы балама және теңдестірілген сипаттама береді. G графигінің кез келген екі төбесі k жолдың соңғы нүктелерін құрайтын болса, және ешқандай екі жолдың ортақ жиегі болмаса, онда G графигі k жиекті байланысқан болады. Бір жағынан, бұл оңай: егер мұндай жолдар жүйесі болса, онда k-дан кем жиектері бар кез келген X жиыны жолдардың кем дегенде біреуінен ажыратылады, және X жойылғаннан кейін де төбелер жұбы бір-бірімен байланысты болып қалады. Екінші жағынан, жиектердің аз санын алып тастау арқылы ажыратылмайтын графиктердегі әрбір төбелер жұбы үшін жолдар жүйесінің бар екендігін желілік ағындар теориясынан алынған максимумдық ағым және минимумдық кесілім теоремасын қолдану арқылы дәлелдеуге болады.

Қарым-қатынас ұғымдары

Минималды төбелік дәрежесі шеттік байланыстың тривиальды жоғарғы шегін береді. Яғни, егер граф k шетімен байланысқан болса, онда k ≤ δ(G), мұндағы δ(G) – кез келген v ∈ V төбесінің ең төменгі дәрежесі. v төбесіне инцидентті барлық шеттерді жою v төбесін графтан ажыратады. Шеттік байланыс – бұл графиктегі ең қысқа циклдің ұзындығы, яғни, жазық графтың шеттік байланысы оның дуалды графигінің шеттік байланысына тең, және керісінше. Бұл ұғымдар матроид теориясында матроидтың айналымы арқылы біріктіріледі, ол матроидтағы ең кіші тәуелді жиынның өлшемімен анықталады. Графикалық матроид үшін матроид айналымы негізгі графтың айналымына тең, ал кографикалық матроид үшін ол шеттік байланысқа тең. 2 шетімен байланысқан графтарды көпірлердің болмауымен, құлақтың ыдырауының болуымен немесе Роббинстің теоремасымен де сипаттауға болады, соған сәйкес бұл – күшті бағдарламаға ие графтар.