Кіріспе

Графтың барлық түйіндерін қамтитын сәйкестік

Граф теориясында, графтың толық сәйкестігі – графтың барлық төбелерін қамтитын сәйкестік. Формальды түрде, G = (V, E) графигі берілгенде, G-дегі толық сәйкестік – бұл жиектер жиыны E-нің M кіші жиыны, мұнда төбелер жиыны V-нің әрбір төбесі M жиынындағы дәл бір жиекке іргелес жатады.

Толық сәйкестік 1-фактор деп те аталады; осы терминді түсіндіру үшін Графты факторлауды қараңыз. Кейбір әдебиеттерде "толық сәйкестік" термині қолданылады. Кез келген толық сәйкестік – максималды кардиналды сәйкестік, бірақ керісінше дұрыс емес. Мысалы, келесі графтарды қарастырайық:

(b) графигінде барлық 6 төбе сәйкес келгендіктен толық сәйкестік (өлшемі 3) бар; (a) және (c) графтарында толық емес, кейбір төбелер сәйкес келмейтін максималды кардиналды сәйкестік (өлшемі 2) бар. Толық сәйкестік – ең аз жиек жабудың да түрі. Егер толық сәйкестік болса, онда сәйкестік саны мен жиек жабу саны тең болады. Толық сәйкестік тек графтың төбелерінің саны жұп болғанда ғана мүмкін. Жақын толық сәйкестік – дәл бір төбе сәйкес келмейтін сәйкестік. Бұл тек графтың төбелерінің саны тақ болғанда ғана мүмкін, және мұндай сәйкестік максималды болуы керек. Жоғарыдағы суретте (c) бөлігі жақын толық сәйкестікті көрсетеді. Егер графтың әрбір төбесі үшін тек сол төбені ғана қалдыратын жақын толық сәйкестік болса, онда граф факторлық сынды деп аталады.

Қасиеттері

Холлдың үйлену теоремасы толық сәйкестікке ие екібөлікті графиктердің сипаттамасын береді. Тютте теоремасы кез келген графиктер үшін сипаттама береді. Толық сәйкестік – 1-ретті кеңейтімге ие кішіграф, яғни 1-фактор. Жалпы алғанда, k-ретті кеңейтімге ие кішіграф k-фактор болып табылады. График толық сәйкестікке ие болуының спектрлік сипаттамасын Хасани Монфаред пен Маллик былай берген: Графтың жұп саны төбелері болсын, ал – бір-бірінен өзгеше, нөлден әртүрлі, таза жолғасатын сандар болсын. Онда граф толық сәйкестікке ие, егер және тек қана егер графигі және өзіндік мәндері бар нақты қисайған-симметриялық матрица болса. Ескеріңіз, нақты симметриялық немесе қисайған-симметриялық матрицаның (жалпы) графигінің төбелері мен қабырғалары матрицасының нөлдік емес диагональдық элементтерімен анықталады.

Графикті бояулаумен байланыс

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

Кемел сәйкесті политоп

Графтың толық сәйкестік политопы – бұл R|E| кеңістігіндегі политоп, оның әр төбесі толық сәйкестіктің инциденттік векторы болып табылады.