Алгоритъмът за разпознаване на изоморфизма на графа, описан в [5]

На тази стъпка ще разгледаме алгоритми, които определят изоморфизма на графиките.

Нека първо ви напомним няколко определения. Определение 1. Нека G и H са графики, f е едно към едно преобразуване на набор V(G) към множество V(H) и g е едно към едно преобразуване на E(G) към E(H). Нека Q означава подредена двойка (f,g). Казваме, че Q е изоморфно преобразуване (изоморфизъм) на граф G върху граф H, ако е изпълнено следното условие: връх x е инцидентен на ребро A в граф G тогава и само ако връх fx е инцидентен на ребро gA в график H .

Ако съществува такъв изоморфизъм Q, тогава казваме, че графите G и H са изоморфни. Ясно е, че в случая

Можем да мислим за Q като за операция, която трансформира графика G в графика H и съответно да напишем QG=H. Също така е удобно да се напише Qv=fv и QA=gA (за всеки връх v и всяко ребро A на графа G ).

Автоморфизъм на граф G е изоморфизъм на граф G върху себе си.

Всеки граф G има идентичен (или тривиален) автоморфизъм I, така че Ix=x за всяко ребро x и всеки връх x от G .

Може да се покаже [1, p.21], че отношението на изоморфизъм между графите е отношение на еквивалентност, т.е. той е симетричен, транзитивен и рефлексивен. Следователно, той разделя класа на всички графи на непразни и по двойки несвързани подкласове, наречени класове на изоморфизъм или класове на изоморфни графи. Два произволни графа принадлежат към един и същ клас изоморфизъм тогава и само ако са изоморфни един на друг.

Естествено е да се идентифицират изоморфни графи, т.е. считани за съвпадащи (те могат да бъдат изобразени на една фигура). Те биха могли да се различават по специфичния характер на своите елементи, но точно това се пренебрегва, когато се въвежда понятието "графика".

Математическа теория на графитесе интересува от такива свойства на графи, които са инвариантни при изоморфизъм (например броят на върховете в графа, броят на циклите или броят на върховете с дадена валентност и т.н.). Естествено е теоретик на графите да идентифицира изоморфни графи. Следователно обикновено се говори за класове на изоморфизъм (наричани още абстрактни графи).

Въпросът дали два дадени графа са изоморфни се оказва сложен в общия случай (виж например [2]).

Тази ситуация, разбира се, тласна много математици към класическия път: да се опитат да намерят такъв инвариант (число или система от числа), който, от една страна, може лесно да се изчисли от дадена графика (и, ако е възможно, да има ясен смисъл), а от друга страна, да има свойството пълнота, т.е. дефинира граф еднозначно с точност до изоморфизъм.

Първоначално е естествено да се зададе въпросът: кои характеристики на графите са инвариантни при изоморфизъм [3, стр.21]?

Известни са примери за такива инварианти на граф G: броят на върховете n(G) , броят на ребрата m(G) и векторът на степените s(G)=(s 1 , s 2 , . s n ) , който по-специално дава числени инварианти

Определение 2. Нека f е функция, присвояваща на всеки граф G някакъв елемент f(G) от множество M с произволен характер. Ще наречем тази функция инвариант, ако нейните стойности съвпадат на изоморфни графики, т.е. за всеки G и G', изоморфизмът на графите G и G' предполага f(G)=f(G') .

Нека представим някои от най-важните графови инварианти [3, p.21-25]:

плътността f(G) е броят на върховете на кликата на графа G . Инвариантността на тази характеристика следва от факта, че ако две графи са изоморфни, всяко подмножество от върхове на една графа, което генерира клика, съответства в другата графа на подмножество със същия брой върхове, което също генерира клика;
не-плътността e(G) е най-големият брой по двойки несъседни върхове на графа;
хроматично число g(G) ;
брой свързани компоненти K(G) ;
числото на Хадуигер h(G) .

Обърнете внимание, че матрицата на съседство не е инвариант на графика: при преминаване от едно изброяване на нейните върхове към друго, тя претърпява пермутация на редове, състояща се от някаква пермутация на редове и точно същата пермутация на колони. Всяка функция на елементите a ij на матрицата, която не се променя при никакви пермутации на редовете на матрицата на съседство, е инвариант на графиката G . Такива функции включват сумата от всички елементи, неподреден набор от суми от елементи от всеки ред или суми от елементи от всяка колона, детерминанта на матрицата, нейния характерен полином и корените на последния и др.

Определение 3 [3, стр.41-42]. Инвариант f се нарича пълен, ако за всякакви графи G и G' равенството f(G)=f(G') предполага изоморфизъм на графите G и G'.

От разглежданите инварианти, които се класифицират като „лесно изчислими“, дори най-„богатият“ – векторът от степени s(G) – не е пълен. В процеса на разработване на теорията на графите не липсваха хипотези за пълнота или други "трудни за изчисляване" инварианти, но всички тези хипотези рано или късно бяха опровергани с конкретни примери.

Определение 4. Степента s на връх v на граф (V,E) е броят на неговите върхове, съседни на v , или, което е същото, броят на ребра, инцидентни на този връх.

Ясно е, че за всеки изоморфизъм на графите L и L' съответстващите един на друг върхове трябва да имат еднаква степен.

Определение 5 [3, стр.17]. Нека G=(V,E) е n-върхова графа и s 1 , s 2 , . s n - степени на върховете му, записани в ненамаляващ ред: s 1 2 n .

Подредената система (s 1 , s 2 , . s n ) ще се нарича вектор от градусиграфика G и означена накратко с s(G) .

Вместо самия градусен вектор често се използва неговата инверсия t(G)=(t 1 , t 2 , . t n ), където t i =s n-i (i=1,2. n) са същите степени на върхове, но подредени в ненарастващ ред: t 1 >= t 2 >= . >=tn.

От казаното по-горе следва, че за изоморфизма на графите G и G' векторите на техните степени трябва да съвпадат: s(G)=s(G') .

Това условие обаче не е достатъчно: на фигура 1 виждаме две двойки неизоморфни графики с еднакви вектори: s = (1,2,2,2,2,3) :

Фиг.1. Двойка неизоморфни графики

Въпреки че не е идеално средство за разпознаване на изоморфизма, векторът на мощността все пак може да бъде от голяма полза в много случаи.

Първо, ако s(G) не е равно на s(G') , тогава веднага следва, че графиките G и G' не са изоморфни.

Второ, ако s(G)=s(G') , тогава за да проверите графиките G и G' за изоморфизъм, не е необходимо да изброявате всички n! съответствия между върхове, но само тези, в които се сравняват върхове от една и съща степен. Така че в примера е необходимо да сортирате само 4!=24 съвпадения вместо 720 [3, стр.17].

Пример. Разпознаване на изоморфизъм на неориентирани графи чрез векторен анализ на степен. Резултатът от програмата е всички едно-към-едно преобразувания на множеството от върхове на първия граф върху множеството от върхове на втория граф, които определят изоморфизма.

Програмата по същество използва модификация на алгоритъма на Джонсън и Тротър за генериране на всички пермутации с минимален брой транспозиции на съседни елементи.

За графиките, показани на фигура 2,

Фиг.2. Пример за графика

Резултатът от приложението ще бъде както следва:

Фиг.3. Резултатът от приложението

Нетривиален тестов случай може да бъде намерен вмонографии [4, с.207].

Има обаче случаи, когато при определяне на изоморфизма на графите техните вектори на степен са практически безполезни: говорим за хомогенни графи, в които степента на всички върхове е еднаква.

Например, разгледайте графика, където всички степени на върха са 3:

Фиг.4. пример за хомогенна графика

Обратният случай е представен от графики, които са еднозначно определени до изоморфизъм чрез техния градусен вектор (или, еквивалентно, чрез неговата инверсия) и се наричат униграфи.

Алгоритъмът за разпознаване на изоморфизма на графа, описан в [5]

Този подход е използван при изграждането на алгоритъм за установяване на изоморфизма на насочени графи в монографията [5, с.398].

Да предположим, че са ни дадени две насочени графи G X =(V X ,E X ) и G Y =(V Y , E Y ) и искаме да разберем дали те са изоморфни. Вярваме, че V X =V Y = , защото ако V X не е равно на V Y , тогава насочените графи не могат да бъдат изоморфни.

Нека една от насочените графики, да речем G X, бъде избрана като референтна. Нека G X (k) е подграф на графа G X, индуциран от върховете , 0 . Ясно е, че G X (0) е празен подграф и G X (1) е подграф, състоящ се от един връх 1 и несъдържащ ребра.

Когато определяме дали графиките G X и G Y са изоморфни, ние използваме техниката за обратно проследяване.

Очевидно G X (0) е изоморфен на празния подграф G Y . Да предположим, че на някаква стъпка е намерен подграф G Y, състоящ се от върхове S, принадлежащи на V Y , който е изоморфен на G X (k) .

Нека се опитаме да разширим изоморфизма до G X (k+1), като изберем връх v, принадлежащ на V Y -S, съответстващ на k+1 от V X .

Ако се намери такъв връх v, тогава фиксираме съответствие f k+1 и се опитваме да разширим изоморфизма до G X (k+2) .

Ако такъв връхне съществува, тогава се връщаме към G X (k-1) и се опитваме да изберем друг връх, съответстващ на k от V X .

Този процес продължава, докато се намери изоморфизъм между G X (n)=G X и G Y, в противен случай се връщаме към G X (0) , заключавайки, че графиките G X и G Y не са изоморфни.

S.Goodman и S.Hidetniemi [6, p.62] предлагат алгоритъм да се нарича евристичен, който има следните две свойства:

Той намира, като правило, добри, макар и не непременно оптимални решения.
Той е по-лесен и по-бърз за изпълнение от който и да е от известните точни алгоритми (т.е. алгоритми, които гарантират оптимално решение).

Евристиката за решаване на проблеми с изоморфизма обикновено се състои в опит да се покаже, че въпросните графики не са изоморфни. За да направите това, се съставя списък с различни инварианти в реда, определен от сложността на изчисляване на инварианта. След това стойностите на параметрите на тези графики се сравняват последователно. Веднага щом се намерят две различни стойности на един и същ параметър, се прави заключението, че тези графики не са изоморфни.

Помислете за пример за доста сложна евристика, която работи с матрицата на съседство A(G) [6, стр.63-64].

Алгоритъм за сравнение на съседство

A 2 (G i ) се изчислява за i=1, 2 . След това редовете и колоните на A 2 (G 1 ) и A 2 (G 2 ) се разменят, така че елементите на главния диагонал да са в низходящ ред.

Ако G 1 и G 2 са изоморфни и всички диагонални елементи са различни, тогава тази пермутация трябва да доведе до идентични матрици.

Ако не, тогава тези две графики не могат да бъдат изоморфни.

Ако матриците са идентични, тогава можете да продължите проверката с A 3 (G i ) , A 4 (G i ), . A k (G i ) за i=1, 2 . Стойността на k се определя от наличния бюджет за машинни ресурси.Ако всички тествани матрици са еднакви, тогава е много правдоподобно, но не непременно вярно, че G 1 и G 2 са изоморфни.

Забележки.

Графите са изоморфни тогава и само ако техните матрици на съседство са получени една от друга чрез същите пермутации на редове и колони [7, p.28].

Графите (насочени графове) са изоморфни тогава и само ако техните матрици на инцидентност се получават една от друга чрез произволни пермутации на редове и колони [7, p.28].

Има доста дълбоки и трудни проблеми, свързани с изоморфизма на графите, и най-известният от тях е проблемът с обновяването.

Нека върховете на графа G са номерирани както следва: v 1 , v 2 , . v k . Означаваме с G j графа, получен от G след премахване на върха v j и инцидентните му ребра. Всички k подграфа G j 0 на графа G ще се наричат първични [1, стр.154].

C 1 (хипотеза за възстановяване).

Ако са дадени класовете на изоморфизъм на всички k първични подграфа на графа G, тогава за k>=3 класът на изоморфизъм на графа G е еднозначно определен.

Към момента на написване на книгата от W.Tatta [1] хипотезата за възстановяването остава недоказана.

Ограничението на k (k>=3) е лесно обосновано.

Ако k=1, тогава единственият първичен подграф на G е празен график, който не носи никаква информация за броя на циклите в G. Ако k=2 , тогава всеки от двата основни подграфа на графа G съдържа само един връх и следователно не знаем нищо за броя на ребрата в графа G . Следователно, наистина трябва да приемем, че V(G)>=3.

Ако някакво свойство или характеристика на граф G може да бъде идентифицирано чрез разглеждане на класовете на изоморфизъм на всички негови първични подграфи G j , тогава то (това) се нарича възстановимо (възстановимо) и графики, които иматтова свойство или характеристика се наричат разпознаваеми. Пример за възстановима характеристика е броят на върховете в графика. Това число е с единица по-голямо от броя на върховете във всеки първичен подграф на дадения граф и съвпада с броя на дадените класове изоморфизъм.

Нека G е граф с номерирани ребра A 1 , A 2 , . A k . Означаваме с G j подграфа на графа G , който се получава след премахване на ребро A j от G.

C 2 (хипотеза за възстановяване на ребрата).

Ако са дадени класовете на изоморфизъм на всички k подграфа G j, тогава за k>=4 класът на изоморфизъм на графа G е еднозначно определен.

Причината за въвеждане на ограничението върху k (k>=4) е ясна от следващата фигура [1, p.164], която показва две графи G и H, така че чрез премахване на произволно ребро от тях, ние получаваме, с точност до изоморфизма, един и същ подграф.

Фиг.5. Пример за графика

[7, стр.14]. В някои ситуации все още трябва да се прави разлика между изоморфни графи и тогава понятието "маркирана графа" е полезно. Граф от ред n се нарича етикетиран, ако някои етикети са присвоени на неговите върхове, например числа 1, 2, . н.

След като идентифицирахме всеки от върховете на графа с неговия номер (и, следователно, множеството от върхове - с множеството от числа), ние дефинираме равенството на обозначените графове G и H от същия ред: G=H, когато множеството от ребра на графа G съвпада с множеството от ребра на графа H.

(1) Tutt W. Теория на графите. - М.: Мир, 1988. - 424 с. (2) Земляченко В.Н., Корнеенко Н.М., Тишкевич Р.И. Проблем с изоморфизма на графа // Теория на изчислителната сложност, I. Сборници от научни семинари ЛОМИ. - 1982. - Т.118. - С.83-158. (3) Зиков А.А. Основи на теорията на графите. М.: Наука, 1987. - 384 с. (4) Белов В.В., Воробьов Е.М., Шаталов В.Е. Теория на графите. - М.: Vyssh.shk., 1976. - 392 с. (5) Reingold E., Nivergelt Yu., Deo H. Комбинаторни алгоритми. Теория и практика. - М.: Мир, 1980. - 476 с. (6) Goodman S., Hidetniemi S. Въведение в разработването и анализа на алгоритми. - М.: Мир, 1981. - 368 с. (7) Лекции по теория на графите / Емеличев В.А., Мелников О.И., Сарванов В.И., Тишкевич Р.И. - М.: Наука, 1990. - 384 с.

Със следващата стъпка ще започнем кратък преглед на мрежите.