Кіріспе
Екі графиктің төбелік жиынтығы арасындағы биекция. Графтар теориясында, G және H графиктерінің изоморфизмі – G және H графиктерінің төбелік жиындары арасындағы биекция болып табылады, егер G графигіндегі кез келген екі төбе u және v төбелері G-де жанындас болса, сонда ғана H графигінде де жанындас болады. Мұндай биекция әдетте «жақтарды сақтайтын биекция» деп сипатталады, бұл изоморфизмнің жалпы ұғымына сәйкес, құрылымды сақтайтын биекция болып табылады. Егер екі граф арасында изоморфизм болса, онда графтар изоморфты деп аталады және былай белгіленеді: . Егер биекция графтың өзіне бейнелеу болса, яғни G және H бірдей граф болса, онда биекция G графының автоморфизмі деп аталады. Граф шекті болса, оны биективті екенін көрсету үшін, бір-бірге сәйкестігін ғана көрсету жеткілікті, екеуін де көрсетудің қажеті жоқ. Граф изоморфизмі – графтардағы эквиваленттілік қатынас, және осылай ол барлық графтар класын эквиваленттілік кластарына бөледі. Бір-біріне изоморфты графтар жиынтығы графтардың изоморфизм класы деп аталады. Граф изоморфизмін полиномиалдық уақытта анықтауға бола ма деген сұрақ компьютерлік ғылымдағы шешілмеген маңызды мәселе болып табылады, ол граф изоморфизмі мәселесі деп белгілі. Төменде көрсетілген екі граф, әртүрлі көріністерге қарамастан, изоморфты болып табылады.
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge preserving bijection", in accordance with the general notion of isomorphism being a structure preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as In the case when the bijection is a mapping of a graph onto itself, i. e., when G and H are one and the same graph, the bijection is called an automorphism of G.
If a graph is finite, we can prove it to be bijective by showing it is one one/onto; no need to show both. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The question of whether graph isomorphism can be determined in polynomial time is a major unsolved problem in computer science, known as the graph isomorphism problem. The two graphs shown below are isomorphic, despite their different looking drawings
Graph G Graph H An isomorphismbetween G and Hf(a) = 1
f(b) = 6
f(c) = 8
f(d) = 3
f(g) = 5
f(h) = 2
f(i) = 4
f(j) = 7
Граф G Граф H G және H арасындағы изоморфизм: f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H
such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge preserving bijection", in accordance with the general notion of isomorphism being a structure preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as In the case when the bijection is a mapping of a graph onto itself, i. e., when G and H are one and the same graph, the bijection is called an automorphism of G.
If a graph is finite, we can prove it to be bijective by showing it is one one/onto; no need to show both. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The question of whether graph isomorphism can be determined in polynomial time is a major unsolved problem in computer science, known as the graph isomorphism problem. The two graphs shown below are isomorphic, despite their different looking drawings
Graph G Graph H An isomorphismbetween G and Hf(a) = 1
f(b) = 6
f(c) = 8
f(d) = 3
f(g) = 5
f(h) = 2
f(i) = 4
f(j) = 7
Вариациялар
Жоғарыдағы анықтамада графиктер бағытталмаған, белгіленбеген, салмақталмаған графиктер деп түсініледі. Дегенмен, изоморфизм ұғымын график ұғымының басқа барлық түрлеріне де қолдануға болады, осы ретте тиісті қосымша құрылымдық элементтерді сақтау талаптарын қосу арқылы: доғалардың бағыттары, қабырғалардың салмақтары және т.б., бірақ бір ерекшелік бар.
Белгіленген графиктердің изоморфизмі
Белгіленген графтар үшін изоморфизмнің екі анықтамасы қолданылады. Бір анықтама бойынша, изоморфизм – бұл қабырғаларды және белгілеулерді сақтайтын төбелік биекция. Екінші анықтама бойынша, изоморфизм – бұл қабырғаларды сақтайтын және белгілеулердің эквиваленттілік кластарын сақтайтын төбелік биекция, яғни эквивалентті (мысалы, бірдей) белгілері бар төбелер эквивалентті белгілері бар төбелерге шамалансады, және керісінше; сондай-ақ қабырға белгілері үшін де осы принцип сақталады. Мысалы, 1 және 2 белгіленген екі төбесі бар графтың бірінші анықтама бойынша бір автоморфизмі бар, ал екінші анықтама бойынша екі автоморфизмі бар. Екінші анықтама, егер графтарға 1, ..., n бүтін сандар диапазонынан алынған бірегей белгілер берілген жағдайларда қолданылады, мұнда n – графтың төбелерінің саны, төбелерді бірегей анықтау үшін ғана пайдаланылады. Мұндай жағдайларда екі белгіленген граф сәйкес келетін белгісіз графтар изоморфты болса, изоморфты деп айтылады (әйтпесе изоморфизмнің анықтамасы мәнсіз болар еді).
Мотивация
"Изоморфизм" формалды ұғымы, мысалы, "граф изоморфизмі", кейбір нысандардың "бірдей құрылымы" бар деген бейресми түсінікті қамтиды, егер сөз болатын нысандардың "атомдық" компоненттерінің жеке ерекшеліктеріне мән берілмесе. Егер "атомдық" компоненттердің (графтар үшін төбелер мен қабырғалар) жекелігі графтар арқылы модельделген нәрсені дұрыс көрсету үшін маңызды болса, модель құрылымға қосымша шектеулер қойылып жетілдіріледі және басқа математикалық объектілер қолданылады: бағытталған графтар, белгіленген графтар, түсті графтар, тамырланған ағаштар және т.б. Изоморфизм қатынасы осы графтардың барлық жалпылама түрі үшін де анықталуы мүмкін: изоморфизм биекциясы нысан түрін анықтайтын құрылым элементтерін сақтауы керек: доғалар, белгілер, төбелер/қабырғалардың түстері, тамырланған ағаштың тамыры және т.б. "Граф изоморфизмі" ұғымы графтардың құрылымына тән қасиеттерді, графтарды бейнелеумен байланысты қасиеттерден ажыратуға мүмкіндік береді: графтардың сызбалары, графтар үшін дерек құрылымдары, графтарға белгі қою және т.б. Мысалы, егер графтың дәл бір цикл болса, онда оның изоморфизм класындағы барлық графтардың да дәл бір циклі болады. Ал егер графтың төбелері (көрсетілсе) бүтін сандар 1, 2, N болса, онда екі изоморфты граф үшін өрнек әртүрлі болуы мүмкін.
may be different for two isomorphic graphs.
Уитни теоремасы
Уитнидің граф изоморфизмі туралы теоремасы, Хаслер Уитни көрсеткендей, екі байланысқан графтардың сызықтық графтары изоморфты болса ғана, олар изоморфты болады. Бір ғана ерекшелік бар: K3, үш төбесі бар толық граф, және K1,3 толық екібөлікті граф, олар изоморфты емес, бірақ екеуінің де сызықтық графы K3 болып табылады. Уитнидің граф теоремасын гиперграфтарға да қолдануға болады.
Граф изоморфизмін тану
Граф изоморфизмі классикалық математикалық жолмен зерттелуі мүмкін, оны Уитни теоремасы көрсетеді, бірақ бұл мәселені алгоритмдік тәсілмен шешу қажет екені мойындалады. Екі шекті графтың изоморфты екенін анықтаудың есептеулік мәселесі граф изоморфизмі мәселесі деп аталады. Оның практикалық қолданысы негізінен химиялық информатика, математикалық химия (химиялық қосылыстарды анықтау) және электрондық дизайнды автоматтандыру (электрондық схема дизайнының әртүрлі бейнелерінің сәйкестігін тексеру) болып табылады. Граф изоморфизмі мәселесі есептеу күрделілігі теориясындағы NP класына жататын, бірақ оның P және NP-толық кластарында екені белгісіз. Бұл 12 мәселенің ішінде күрделілігі шешілмеген екі мәселенің бірі, екіншісі бүтін сандарды жіктеу. Дегенмен, егер мәселе NP-толық болса, онда полиномиалдық иерархия шекті деңгейге дейін төмендейді. 2015 жылдың қарашасында Чикаго университетінің математигі және компьютерлік ғалымы Ласло Бабаи граф изоморфизмі мәселесін квазиполиномиалдық уақытта шешуге болатынын дәлелдегенін мәлімдеді. Ол осы нәтижелердің алдын ала нұсқаларын 2016 жылғы Компьютерлік теория жөніндегі симпозиум мен 2018 жылғы Халықаралық математиктер конгресінің материалдарында жариялады. 2017 жылдың қаңтарында Бабаи квазиполиномиалдық тұжырымын уақытша кері қайтарып, оның орнына субекспоненциалды уақыт күрделілігін көрсетті. Ол бастапқы тұжырымын бес күннен кейін қайта орнатты. 2020 жылға дейін Бабаидың толық мақаласы журналда жарияланбады. Оның жалпыламасы, субграф изоморфизмі мәселесі, NP-толық екені белгілі. Мәселені зерттеудің негізгі салалары – жылдам алгоритмдерді жасау және оның есептеу күрделілігін теориялық тұрғыдан зерттеу, жалпы мәселе үшін де, графтардың арнайы кластары үшін де. Вайсфейлер-Леман граф изоморфизмі тестісін граф изоморфизмін тексеру үшін қолдануға болады. Егер тест сәтсіз аяқталса, екі кіріс графтың изоморфты емес екеніне кепілдік беріледі. Егер тест сәтті аяқталса, графтар изоморфты болуы мүмкін немесе болмауы мүмкін. Изоморфизмді анықтауға кепілдік беретін тест алгоритмінің жалпыламалары бар, бірақ олардың жұмыс уақыты экспоненциалды. Граф изоморфизмі үшін тағы бір танымал алгоритм – Корделла және тағы басқалар жасаған vf2 алгоритмі (2001 жыл). vf2 алгоритмі – тереңдікке бірінші іздеу алгоритмі, ол екі граф арасында изоморфизмді кезең-кезеңмен құруға тырысады. Ол іздеу кеңістігін қысқарту үшін мүмкіндік ережелерінің жиынтығын қолданады, бұл оған мыңдаған түйіндері бар графтарды тиімді өңдеуге мүмкіндік береді. vf2 алгоритмі үлгіні тану, компьютерлік көру және биоинформатика сияқты әртүрлі салаларда кеңінен қолданылады. Оның ең нашар жағдайдағы уақыт күрделілігі экспоненциалды болғанымен, көптеген графтар үшін жақсы жұмыс істейді.