Кіріспе

Түйіндік байланыс графтары арасындағы құрылымды сақтайтын сәйкестік. Графтар теориясының математикалық саласында граф гомоморфизмі – екі графтың құрылымын сақтайтын бейнелеу. Нақтырақ айтқанда, бұл екі графтың төбелік жиындары арасындағы функция, ол жапсарлас төбелерді жапсарлас төбелерге бейнелейді. Гомоморфизмдер графтарды бояудың әртүрлі ұғымдарын жалпылайды және белгілі бір кестелеу немесе жиілік тағайындау мәселелері сияқты шектеулерді қанағаттандыру мәселелерінің маңызды класын беруге мүмкіндік береді. Гомоморфизмдерді біріктіруге болатындықтан, бай алгебралық құрылымдар пайда болады: графтардағы преордер, дистрибутивтік тор және категория (бағытталмаған графтар үшін біреуі, бағытталған графтар үшін біреуі). Берілген графтар арасында гомоморфизмді табудың есептеу қиындығы, әдетте, тым жоғары, бірақ полиномиалдық уақытта шешілетін арнайы жағдайлар туралы көп мәлімет бар. Шешімге ие және шешімге ие емес жағдайлар арасындағы шекаралар зерттеудің белсенді саласы болып табылады.

Ұзақ жолсыз бағдарлар

Тағы бір қызықты байланыс графтардың бағыттарына қатысты. Бағытталмаған граф G-нің бағыты – әр қабырғасы үшін екі мүмкін бағыттың бірін таңдау арқылы алынған кез келген бағытталған граф. Kk толық графигінің бағытының мысалы – 1, 2, ..., k төбелері және i < j болғанда i-ден j-ге дейінгі доғалары бар k транзитивті турнир. Графтардың G және H бағыттары арасындағы гомоморфизм, бағыттарды ескермей, G және H бағытталмаған графтары арасындағы гомоморфизмді тудырады. Екінші жағынан, бағытталмаған графтар арасындағы G → H гомоморфизмі берілгенде, H-ның кез келген бағыты G-нің бағыты ретінде кері қайтарылуы мүмкін, сонда ол гомоморфизмге ие болады. Сондықтан, граф G, k түсті болуы (Kk-ге гомоморфизмге ие болуы) үшін, G-нің кейбір бағыты k-ға гомоморфизмге ие болуы керек.

Халық арасында кең таралған теорема бойынша, кез келген k үшін, бағытталған граф G, k-ға гомоморфизмге ие болуы үшін, одан k+1 бағытталған жолы болмауы керек. Мұнда n – 1, 2, ..., n төбелері және i = 1, 2, ..., n-1 үшін i-ден i+1-ге дейінгі қабырғалары бар бағытталған граф. Сондықтан, граф k түсті болуы үшін, оның k+1 гомоморфизмін қабылдамайтын бағыты болуы керек. Бұл мәлімдемені күшейтуге болады: граф k түсті болуы үшін, оның кейбір бағытында k ұзындықтағы бағытталған жол болмауы керек (к+1 қосалқы граф ретінде). Бұл – Галай-Хассе-Рой-Витавер теоремасы.

Мысалдар

Кейбір кестелеу мәселелерін граф гомоморфизмдерін табу туралы сұрақ ретінде модельдеуге болады. Мысалы, бір студент қатысатын екі курс уақыт бойынша тым жақын болмауы үшін, семинарлық курстарды күнтізбедегі уақыт тілімдеріне тағайындау қажет. Курстар G графигін құрайды, кез келген екі курс арасында ортақ студенті бар болса, олардың арасында жиек болады. Уақыт тілімдері H графигін құрайды, егер екі тілім уақыт бойынша жеткілікті алыс болса, олардың арасында жиек болады. Мысалы, егер әрбір студент семинарлық курстарын қатарынан келмейтін күндері алуын қаласақ, онда H, C7 графигінің толықтырылған графигі болады. G-ден H-ға граф гомоморфизмі – бұл курс пен уақыт тілімін сәйкестендіретін кесте, яғни курс уақыт тіліміне тағайындалады. Мысалы, егер бірде-бір студенттің жұма және дүйсенбі күндері сабағы болмауын қажет етсек, H графигінен тиісті жиекті алып тастау жеткілікті.

Жай жиілік тағайындау мәселесін былай сипаттауға болады: сымсыз желідегі бірнеше хабар таратушылар дерек жіберу үшін жиілік арнасын таңдауы керек. Кедергіге жол бермеу үшін, географиялық жағынан жақын орналасқан хабар таратушылар жиіліктері бір-бірінен алыс каналдарды пайдалануы керек. Егер «географиялық жақындық» және «алыстық» ұғымдарын анықтау үшін бір шектік мән қолданылса, онда дұрыс арна таңдау тағы да граф гомоморфизміне сәйкес келеді. Бұл модель өте қарапайым болғанымен, біршама икемділікке ие: географиялық ерекшеліктерге байланысты кедергі тудыруы мүмкін, бірақ жақын емес хабар таратушылар жұптарын G графигінің жиектеріне қосуға болады. Ал бір уақытта байланыспайтын таратушылар жұптарын одан алып тастауға болады. Сол сияқты, бір-бірінен алыс орналасқан, бірақ гармоникалық кедергі тудыратын арналар жұптарын H графигінің жиектерінен алып тастауға болады.

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

Ресми көрініс

Графтар мен бағытталған графтарды реляциялық құрылымдар деп аталатын, қатынастар жиынтығымен анықталатын, әлдеқайда жалпы ұғымның ерекше жағдайы ретінде қарастыруға болады. Бағытталған графтар – доменде (түйіндер жиынтығы) бір ғана бинарлық қатынасы (жапсарлылық) бар құрылымдар. Осы тұрғыдан алғанда, мұндай құрылымдардың гомоморфизмдері – нақты граф гомоморфизмдері болып табылады. Жалпы алғанда, бір реляциялық құрылымнан екіншісіне гомоморфизм табу мәселесі – бұл шектеуді қанағаттандыру мәселесі (CSP). Графтардың жағдайы күрделі КЖЖ түсінуге көмектесетін нақты алғашқы қадамды ұсынады. Граф гомоморфизмдерін табудың кері іздеу, шектеу тарату және жергілікті іздеу сияқты көптеген алгоритмдік әдістері барлық CSP-ге қолданылады. Егер G және H графтары болса, G-нің H-ге гомоморфизмі бар ма деген сұрақ, келесідей, тек бір түрлі шектеуі бар CSP мысалына сәйкес келеді. Айнымалылар – G графының түйіндері, ал әр айнымалының домені – H графының түйіндер жиынтығы. Бағалау – бұл әр айнымалыға доменнен элемент тағайындайтын функция, яғни V(G)-ден V(H)-ға дейінгі f функциясы. G графының әрбір қабырғасы немесе доғасы (u,v) ((u,v), E(H)) шектеуіне сәйкес келеді. Бұл шектеу бағалаудың (u,v) доғасын E(H) қатынасындағы (f(u),f(v)) жұбына бейнелеу керектігін көрсетеді, яғни H графының доғасына. CSP-ге шешім – барлық шектеулерді сақтайтын бағалау, демек ол G-ден H-ге гомоморфизм.

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

Граф гомоморфизмі мәселесінде, инстанция – графиктер жұбы (G, H), ал шешім – G-ден H-ге гомоморфизм. Жалпы шешімді анықтау мәселесі, яғни шешімнің болуы немесе болмауы, NP-толық. Дегенмен, рұқсат етілген инстанцияларды шектеу әртүрлі мәселелерге әкеледі, олардың кейбіреулерін шешу әлдеқайда оңай. Сол жақтан G-ні шектеу үшін қолданылатын әдістер, оң жақтан H-ні шектеуге қарағанда мүлдем басқа, бірақ әр жағдайда дихотомия (оңай және қиын жағдайлар арасындағы нақты шекара) белгілі немесе болжанады.

Желілік теория мен категориялар теориясында

(AMSI жазғы зерттеу стипендиялары, Брайан Дейви мен Джейн Питкетлидің жетекшілігімен Ла Тробе университетінде жасалған студенттік зерттеу есебі).