Кіріспе
Есептеу күрделілігі теориясындағы шешілмеген мәселе
Граф изоморфизмі — екі шекті графтың изоморфты екенін анықтаудың есептеу мәселесі. Бұл мәселе полиномдық уақытта шешілетіні немесе NP-толық екені әлі белгілі емес, сондықтан ол NP аралық есептеу күрделілігі класына жатуы мүмкін. Граф изоморфизмі мәселесі NP класының төменгі иерархиясында екені белгілі, бұл полиномдық уақыт иерархиясы екінші деңгейге дейін құлаған жағдайда ғана NP-толық бола алмайтынын көрсетеді. Сонымен қатар, графтардың көптеген арнайы сыныптары үшін изоморфизм полиномдық уақытта шешіледі, ал тәжірибеде граф изоморфизмін көбінесе тиімді түрде шешуге болады. Бұл мәселе субграф изоморфизмі мәселесінің ерекше жағдайы болып табылады, ол берілген G графында басқа H графына изоморфты субграф бар ма деген сұраққа жауап береді; бұл мәселе NP-толық екені белгілі. Бұл симметриялық топтағы абельдік емес жасырын кіші топ мәселесінің де ерекше жағдайы болып табылады. Бейне тану саласында бұл дәл графты сәйкестендіру деп аталады.
Техниканың жай-күйі
2015 жылдың қарашасында Ласло Бабаи барлық графтар үшін квазиполиномдық уақыт алгоритмін жариялады, яғни жұмыс істеу уақыты белгілі бір тұрақты үшін болатын алгоритм. 2017 жылдың 4 қаңтарында Бабаи квазиполиномдық талаптан бас тартып, Харальд Хельфгот дәлелдемедегі қателік тапқаннан кейін субэкспоненциалдық уақыт шегін көрсетті. 2017 жылдың 9 қаңтарында Бабаи түзету жариялады (толық нұсқасы 19 қаңтарда жарияланды) және Хельфгот түзетуді растағаннан кейін квазиполиномдық талапты қалпына келтірді. Хельфгот 1=c = 3 деп алуға болатынын айтады, сондықтан жұмыс уақыты 2^(O((log n)^(3))) болады. Осыған дейін ең жақсы қабылданған теориялық алгоритмге және В.Н. Земляченконың субфакториалдық алгоритмімен үйлесімде ертедегі жұмыстар негіз болған. Алгоритмнің орындалу уақыты n төбесі бар графтар үшін 2O шамасында, және ол шекті қарапайым топтарды жіктеуге сүйенеді. Бұл классификация теоремасы болмаған жағдайда, әлсіз шек алдымен күшті тұрақты графтар үшін , содан кейін жалпы графтарға таратылды. Күшті тұрақты графтар үшін дәреже көрсеткішін жақсарту арқылы шекті гиперграфтар үшін, графтардағы жағдайға сәйкес келетін субэкспоненциалдық жоғарғы шек алынды. Граф изоморфизмі мәселесіне қатысты, , , және авторларының алгоритмдері сияқты бірнеше практикалық алгоритмдер бар. Олар кездейсоқ графтарда жақсы жұмыс істейтін болса да, осы алгоритмдердің ең нашар жағдайда экспоненциалдық уақытпен жұмыс істеуі үлкен кемшілік болып табылады. Граф изоморфизмі мәселесі графтың автоморфизм тобын есептеу мәселесімен есептеу жағынан эквивалентті, және ол пермутация тобы изоморфизмі мәселесінен және пермутация тобы қиылысу мәселесінен нашар. Соңғы екі мәселе үшін, график изоморфизміне ұқсас күрделілік шектері алынды.
was obtained first for strongly regular graphs by , and then extended to general graphs by Improvement of the exponent for strongly regular graphs was done by For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs was obtained by
There are several competing practical algorithms for graph isomorphism, such as those due to , , , and While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case. The graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem and the permutation group intersection problem. For the latter two problems, obtained complexity bounds similar to that for graph isomorphism.
Күрделілік сыныбы GI
Граф изоморфизмі мәселесінің NP-толық екені немесе оны шешуге болатыны әлі белгілі емес, сондықтан зерттеушілер осы мәселені жақсырақ түсіну үшін GI деп аталатын жаңа класс жасады – бұл полиномиалдық уақытта граф изоморфизмі мәселесіне Тьюринг азайтуға болатын мәселелер жиыны. Егер граф изоморфизмі мәселесі полиномиалдық уақытта шешілсе, GI классы P класына тең болады. Ал егер бұл мәселе NP-толық болса, GI классы NP класына тең болады және NP класындағы барлық мәселелер квазиполиномиалдық уақытта шешіледі. Полиномиалдық уақыт иерархиясындағы күрделілік сыныптарында қабылданғандай, егер GI класындағы кез келген мәселеден берілген мәселеге полиномиалдық уақытта Тьюринг азайтуы болса, онда бұл мәселе GI-ға қатысты қиын деп аталады, яғни GI-ға қатысты қиын мәселені шешу үшін полиномиалдық уақыт жеткілікті болса, онда граф изоморфизмі мәселесін де полиномиалдық уақытта шешуге болады (сонымен қатар GI класындағы барлық мәселелерді де). Егер мәселе GI-ға қатысты қиын болса және граф изоморфизмі мәселесін полиномиалдық уақытта шешу осы мәселені полиномиалдық уақытта шешуге мүмкіндік берсе, онда бұл мәселе GI үшін толық немесе GI-толық деп аталады. Граф изоморфизмі мәселесі NP және co AM кластарына кіреді. GI классы Parity P үшін төмен және оған кіреді, сондай-ақ SPP класына да кіреді, бұл сынып ықтимал түрдде әлдеқайда кіші. Parity P класына кіруі граф изоморфизмі мәселесін шешу, полиномиалдық уақытта жұмыс істейтін, бірақ жауабын кездейсоқ түрде табатын Тьюринг машинасының қабылданатын жолдарының жұп немесе тақ екенін анықтаудан қиын емес екенін білдіреді. GI классы ZPPNP класына да кіреді және оған төмен. Бұл, негізінен, NP оракулына қол жеткізетін тиімді Лас-Вегас алгоритмі граф изоморфизмін оңай шеше алады, сондықтан оған тұрақты уақытта осы мәселені шешу мүмкіндігі берілсе, ол ешқандай артық мүмкіндік алмайды.
The graph isomorphism problem is contained in both NP and co AM. GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP. That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPPNP. This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.
ГИ-толық графиктер кластары
Графиктер класы, егер осы подкластағы графиктер үшін изоморфизмді тану GI толық проблемасы болса, GI толық деп аталады. Келесі кластар GI толық: V сипаттамасы немесе H сипаттамасымен берілген екі дөңес политоптың проективті немесе аффиндік изоморфты екенін анықтау мәселесі. Соңғысы екі политопты қамтитын кеңістіктер арасында проективті немесе аффиндік түрлендірудің болуын білдіреді (олар міндетті түрде бірдей өлшемде болмауы мүмкін), бұл политоптар арасында биекцияны тудырады.
The problem of deciding whether two convex polytopes given by either the V description or H description are projectively or affinely isomorphic. The latter means existence of a projective or affine map between the spaces that contain the two polytopes (not necessarily of the same dimension) which induces a bijection between the polytopes.
Қолданбалар
Графтар көптеген салаларда, соның ішінде компьютерлік көру және үлгілерді тануда құрылымдық ақпаратты кодтау үшін жиі қолданылады, ал графтарды сәйкестендіру, яғни графтар арасындағы ұқсастықты анықтау, осы салалардағы маңызды құрал болып табылады. Осы салалардағы граф изоморфизмі мәселесі графтың нақты сәйкестігі деп аталады. Химиялық информатикада және математикалық химияда граф изоморфизмін тексеру химиялық деректер базасындағы химиялық қосылысты анықтау үшін пайдаланылады. Сонымен қатар, органикалық математикалық химияда граф изоморфизмін тексеру молекулалық графтарды жасау және компьютерлік синтез үшін тиімді. Химиялық деректер базасын іздеу – графикалық деректерді талдаудың бір мысалы, онда графты канонизациялау әдісі көбінесе қолданылады. Атап айтқанда, молекулалық ақпаратты кодтаудың стандартты және адам оқи алатын тәсілін қамтамасыз етуге және деректер базаларында және интернетте осындай ақпаратты іздеуді жеңілдетуге арналған SMILES және InChI сияқты химиялық заттардың бірнеше идентификаторлары, олардың есептеулерінде канонизация кезеңін қолданады, бұл, негізінен, молекуланы бейнелейтін графты канонизациялау болып табылады. Электрондық дизайнды автоматтандыруда граф изоморфизмі – схемалық схемаға қарсы макетті (LVS) тексеру кезегінің негізі болып табылады, бұл схемалық схемамен және интегралдық схемамен бейнеленген электр тізбектерінің бірдей екендігін тексеруден тұрады.
Сауалнамалар мен монографиялар
. . (В. А. Стеклова атындағы КСРО Ғылым академиясының Математика институтының Ленинград бөлімшесінің ғылыми семинарларының жинағы), 118-том, 83–158-беттер, 1982 ж.) (Графтар, сақиналар және топтар үшін изоморфизм мәселесіне қатысты ашық сұрақтардың қысқаша шолуы.) (Кітаптың мұқабасынан: Кітап мәселенің есептеу күрделілігіне қатысты мәселеге тоқталады және NP класындағы, сондай-ақ басқа күрделілік кластарындағы мәселенің салыстырмалы орнын жақсырақ түсінуге көмектесетін бірнеше жаңа нәтижелерді ұсынады.) (Бұл бағанның 24-ші нөмірі "Компьютерлер және шешілмейтін мәселелер" кітабындағы және бұрынғы бағандардағы ашық мәселелердің, әсіресе Граф изоморфизмінің қазіргі жай-күйін талқылайды.) .
Бағдарламалық жасақтама
Граф изоморфизмі, іске асырулардың шолуы, Стони Брук алгоритмдері қоймасы.