Унифицированный подход к решению задач морфизма на графах
Описаны алгоритмы определения изоморфизма и граф-подграф изоморфизма, основанные на использовании матрицы возможных совмещений и применении инвариантов к подграфам окружения вершин. Приведены результаты сравнительного анализа скорости работы алгоритмов. Показана высокая производительность разработан...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2008 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101550 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Унифицированный подход к решению задач морфизма на графах / М.Б. Ильяшенко // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 19-41. — Бібліогр.: 21 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859933532430794752 |
|---|---|
| author | Ильяшенко, М.Б. |
| author_facet | Ильяшенко, М.Б. |
| citation_txt | Унифицированный подход к решению задач морфизма на графах / М.Б. Ильяшенко // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 19-41. — Бібліогр.: 21 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Описаны алгоритмы определения изоморфизма и граф-подграф изоморфизма, основанные на использовании матрицы возможных совмещений и применении инвариантов к подграфам окружения вершин. Приведены результаты сравнительного анализа скорости работы алгоритмов. Показана высокая производительность разработанных алгоритмов для класса графов, не обладающих специальными свойствами.
Наведено алгоритми визначення ізоморфізму та граф-підграф ізоморфізму на базі використання матриці можливих суміщень та застосування інваріантів до підграфів оточення вершин. Наведено результати порівнювального аналізу швидкості роботи алгоритмів. Показано високу продуктивність розроблених алгоритмів для класу графів, що не мають спеціальних властивостей.
Algorithms are presented for isomorphism and graph-subgraph isomorphism determination. They are based on the use of possible coincidence matrix and invariants application to subgraphs for vertexes surrounding. Comparative analysis results are offered for speed of algorithms executing. High performance of algorithms developed is shown for those graphs class which are not possessed special properties.
|
| first_indexed | 2025-12-07T16:08:47Z |
| format | Article |
| fulltext |
ÓÄÊ 004.021; 004.75
Ì. Á. Èëüÿøåíêî, àñïèðàíò
Çàïîðîæñêèé Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò
(Óêðàèíà, 69063, ã. Çàïîðîæüå, óë. Æóêîâñêîãî, 64,
òåë.: 8 (061) 7698508, E-mail: ilmatsoft@mail.ru)
Óíèôèöèðîâàííûé ïîäõîä
ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
Îïèñàíû àëãîðèòìû îïðåäåëåíèÿ èçîìîðôèçìà è ãðàô-ïîäãðàô èçîìîðôèçìà, îñíîâàí-
íûå íà èñïîëüçîâàíèè ìàòðèöû âîçìîæíûõ ñîâìåùåíèé è ïðèìåíåíèè èíâàðèàíòîâ ê
ïîäãðàôàì îêðóæåíèÿ âåðøèí. Ïðèâåäåíû ðåçóëüòàòû ñðàâíèòåëüíîãî àíàëèçà ñêîðîñòè
ðàáîòû àëãîðèòìîâ. Ïîêàçàíà âûñîêàÿ ïðîèçâîäèòåëüíîñòü ðàçðàáîòàííûõ àëãîðèòìîâ
äëÿ êëàññà ãðàôîâ, íå îáëàäàþùèõ ñïåöèàëüíûìè ñâîéñòâàìè.
Íàâåäåíî àëãîðèòìè âèçíà÷åííÿ ³çîìîðô³çìó òà ãðàô-ï³äãðàô ³çîìîðô³çìó íà áàç³ âèêî-
ðèñòàííÿ ìàòðèö³ ìîæëèâèõ ñóì³ùåíü òà çàñòîñóâàííÿ ³íâàð³àíò³â äî ï³äãðàô³â îòî÷åííÿ
âåðøèí. Íàâåäåíî ðåçóëüòàòè ïîð³âíþâàëüíîãî àíàë³çó øâèäêîñò³ ðîáîòè àëãîðèòì³â.
Ïîêàçàíî âèñîêó ïðîäóêòèâí³ñòü ðîçðîáëåíèõ àëãîðèòì³â äëÿ êëàñó ãðàô³â, ùî íå ìàþòü
ñïåö³àëüíèõ âëàñòèâîñòåé.
Ê ë þ ÷ å â û å ñ ë î â à: èçîìîðôèçì, ãðàô-ïîäãðàô èçîìîðôèçì, èíâàðèàíò ïîäãðàôà
îêðóæåíèÿ âåðøèíû, ìàòðèöà âîçìîæíûõ ñîâìåùåíèé.
Ãðàôîâûå ñòðóêòóðû øèðîêî ïðèìåíÿþòñÿ äëÿ ïðåäñòàâëåíèÿ îòíîøåíèé
îáúåêòîâ è êîíöåïöèé. Ïðè ãðàôîâîì ïðåäñòàâëåíèè âåðøèíû ãðàôà
îáû÷íî ñîîòâåòñòâóþò îáúåêòàì, à ðåáðà — îòíîøåíèÿì ìåæäó ýòèìè
îáúåêòàìè. Íàïðèìåð, â êîìïüþòåðíûõ ñåòÿõ âåðøèíû ãðàôîâ ìîãóò ñîîò-
âåòñòâîâàòü óçëàì âû÷èñëèòåëüíîé ñðåäû, à ðåáðà — ñåòåâûì ñîåäèíå-
íèÿì [1]. Íåêîòîðûå èâàðèàíòíûå ñâîéñòâà ãðàôîâ è óäîáñòâî îïèñàíèÿ
ìîäåëåé òèïà îáúåêòû—îòíîøåíèÿ ïðèâåëè ê øèðîêîìó èñïîëüçîâàíèþ
ãðàôîâ â ðàçëè÷íûõ îáëàñòÿõ íàóêè è òåõíè÷åñêèõ ïðèëîæåíèÿõ, òàêèõ
êàê ñèñòåìû ðàñïîçíàâàíèÿ îáðàçîâ, ñèñòåìû ìîäåëèðîâàíèÿ, ïðîãíîçèðîâà-
íèÿ è ïëàíèðîâàíèÿ, ñðàâíåíèÿ ìîëåêóëÿðíûõ ñòðóêòóð, òåñòèðîâàíèå èíòå-
ãðàëüíûõ ñõåì, îïòèìèçàöèÿ ìèêðîêîíòðîëëåðîâ, àíàëèç êèòàéñêîé ïèñü-
ìåííîñòè, ïëàíèðîâàíèå äâèæåíèé ðîáîòîâ, ñåìàíòè÷åñêèé ñåòåâîé ïîèñê è
ðàñïîçíàâàíèå ìíîãîãðàííûõ îáúåêòîâ [2].
Ïðîâåðêà íà èçîìîðôíîñòü äâóõ ãðàôîâ èãðàåò â àëãåáðå ãðàôîâ ïðè-
ìåðíî òàêóþ æå ðîëü, êàê ïðîâåðêà ìàòåìàòè÷åñêîãî îòíîøåíèÿ ðàâåíñò-
âà. Çàäà÷ó óñòàíîâëåíèÿ èçîìîðôíîé ýêâèâàëåíòíîñòè äâóõ ãðàôîâ ïðè-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 19
íÿòî îòíîñèòü ê ðàçðÿäó NP-òðóäíûõ [3], õîòÿ ñòðîãîãî äîêàçàòåëüñòâà
ýòîãî íå ñóùåñòâóåò. Ðàññìîòðèì àëãîðèòìû îïðåäåëåíèÿ èçîìîðôèçìà è
ãðàô-ïîäãðàô èçîìîðôèçìà äâóõ ãðàôîâ, êîòîðûå ïî ñëîæíîñòè âû÷èñëå-
íèé ìàêñèìàëüíî ïðèáëèæåíû ê ïîëèíîìèàëüíûì.
Îáçîð ñîâðåìåííûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ èçîìîðôèçìà íà
ãðàôàõ. Â íàñòîÿùåå âðåìÿ ñóùåñòâóåò øèðîêèé ñïåêòð àëãîðèòìîâ ðåøå-
íèÿ çàäà÷è ïðîâåðêè èçîìîðôèçìà è ãðàô-ïîäãðàô èçîìîðôèçìà [4—8].
Ñòàíäàðòîì äå-ôàêòî â ïðàêòè÷åñêèõ ïðèëîæåíèÿõ ÿâëÿåòñÿ àëãîðèòì,
ïðåäëîæåííûé Äæ. Ð. Óëìàíîì [9]. Àëãîðèòì îñíîâàí íà ïðîöåäóðå ïîèñ-
êà ñ âîçâðàòîì íà îñíîâå ýôôåêòèâíîé ôóíêöèè «çàãëÿäûâàíèÿ âïåðåä»,
óìåíüøàþùåé ïðîñòðàíñòâî ïîèñêà. Ýòîò àëãîðèòì ïðèãîäåí äëÿ äâóõ
âèäîâ ìîðôèçìîâ (èçîìîðôèçìà è ãðàô-ïîäãðàô èçîìîðôèçìà) è ÿâëÿåòñÿ
îäíèì èç íàèáîëåå øèðîêî ïðèìåíÿåìûõ àëãîðèòìîâ äëÿ òî÷íîãî ñðàâíå-
íèÿ ãðàôîâ [4].
Ñðåäè íàèáîëåå ýôôåêòèâíûõ àëãîðèòìîâ äëÿ ðåøåíèÿ çàäà÷ èçî-
ìîðôèçìà è ãðàô-ïîäãðàô èçîìîðôèçìà âûäåëÿþòñÿ àëãîðèòìû VF è
VF2, ðàçðàáîòàííûå Ï. Ôîãèÿ [10, 11]. Ýòî òî÷íûå àëãîðèòìû, îñíîâàí-
íûå, êàê è àëãîðèòì Óëìàíà, íà ïîèñêå â ïðîñòðàíñòâå ñîñòîÿíèé, íî â
êà÷åñòâå îãðàíè÷èâàþùåãî óñëîâèÿ â íèõ èñïîëüçóåòñÿ ÷èñëî âõîäÿùèõ è
èñõîäÿùèõ äóã, èíöèäåíòíûõ ñîâìåùåííûì âåðøèíàì ãðàôîâ. Ýòîò àëãî-
ðèòì âõîäèò â ñîñòàâ áèáëèîòåêè äëÿ ðàáîòû ñ ãðàôàìè LEDA [12, 13].
Àëãîðèòì VF2 îòëè÷àåòñÿ îò ïðåäøåñòâóþùåãî, â îñíîâíîì, èçìåíåí-
íûìè ñòðóêòóðàìè äëÿ õðàíåíèÿ äàííûõ è ïðîìåæóòî÷íûõ ðåçóëüòàòîâ. Â
îáîèõ àëãîðèòìàõ èñïîëüçóåòñÿ ôóíêöèÿ îãðàíè÷åíèÿ ãëóáèíû ïîèñêà íà
îñíîâå ñîâïàäåíèÿ ñóììàðíîãî ÷èñëà èíöèäåíòíûõ ðåáåð óæå ñîâìå-
ùåííîé ÷àñòè âåðøèí îáîèõ ãðàôîâ. Ïî ðåçóëüòàòàì èññëåäîâàíèé [14]
ýòî îäèí èç ñàìûõ áûñòðûõ àëãîðèòìîâ ïðîâåðêè íà èçîìîðôíîñòü ñðåäè
ñîâðåìåííûõ ïåðåáîðíûõ àëãîðèòìîâ.
Àëãîðèòì SD (Øìèäòà—Äðþôåëÿ) íàçâàí ïî èìåíàì àâòîðîâ [15]. Ýòî
äîñòàòî÷íî èçâåñòíûé è õîðîøî çàðåêîìåíäîâàâøèé ñåáÿ àëãîðèòì ïåðå-
áîðíîãî õàðàêòåðà. Îñíîâó åãî ñîñòàâëÿåò ôóíêöèÿ îãðàíè÷åíèÿ ãëóáèíû
ïîèñêà íà îñíîâå ìàòðèöû ðàññòîÿíèé ìåæäó âåðøèíàìè. Ê íåäîñòàòêàì
äàííîãî àëãîðèòìà ñëåäóåò îòíåñòè òî, ÷òî åãî ôóíêöèÿ îãðàíè÷åíèÿ ãëóáèíû
ïîèñêà ïðàêòè÷åñêè íå ðàáîòàåò íà ñèëüíîðåãóëÿðíûõ ãðàôàõ.
Ê íàèáîëåå ýôôåêòèâíûì àëãîðèòìàì îòíîñèòñÿ òàêæå àëãîðèòì
Â.Ï. Ïèí÷óêà, îñíîâàííûé íà ìåòîäå ïîñëåäîâàòåëüíîãî íàëîæåíèÿ ñ âîç-
âðàòîì [16, 17]. Ôóíêöèÿ îãðàíè÷åíèÿ ãëóáèíû ïîèñêà ñòðîèòñÿ òîëüêî íà
ïðîâåðêå ñîâïàäåíèÿ ðåáåð ìåæäó íàëîæåííûìè âåðøèíàìè ãðàôîâ.
Îòñóòñòâóåò ôóíêöèÿ çàãëÿäûâàíèÿ âïåðåä. Äëÿ óñêîðåíèÿ ðàáîòû àëãî-
ðèòìà â ñëó÷àÿõ, êîãäà ãðàôû èçîìîðôíû, ïðèìåíÿåòñÿ ðÿä ïðåäâàðè-
Ì. Á. Èëüÿøåíêî
20 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
òåëüíûõ ïðåîáðàçîâàíèé, ïðåäíàçíà÷åííûõ äëÿ ñîðòèðîâê âåðøèí â ïî-
ðÿäêå, íàèáîëåå ïðåäïî÷òèòåëüíîì äëÿ ñîâìåùåíèÿ. Íåñìîòðÿ íà ïðîñòî-
òó, àëãîðèòì ïîçâîëèë âûïîëíèòü ðàñ÷åò ïîëíîãî íàáîðà íåèçîìîðôíûõ
ãðàôîâ äî 11 âåðøèí âêëþ÷èòåëüíî.
Àëãîðèòì óñòàíîâëåíèÿ èçîìîðôíîñòè. Ïîñòàíîâêà çàäà÷è óñòà-
íîâëåíèÿ èçîìîðôíîñòè ãðàôîâ. Ïóñòü äàíû ãðàôû G V E
1 1 1
� ( , ) è G
2
�
� ( , )V E
2 2
. Ãðàô G
1
èçîìîðôåí ãðàôó G
2
(îáîçíà÷àåòñÿ êàê G G
1 2
� ), åñëè
ñóùåñòâóåò ïîäñòàíîâêà � :V V
2 1
� òàêàÿ, ÷òî äëÿ êàæäîé ïàðû âåðøèí
v v Vi j, �
2
, ( , )v v Ei j �
2
, òîãäà è òîëüêî òîãäà, êîãäà ( ( ), ( ))� �v v Ei j �
1
.
Ðàçðàáîòàííûé àëãîðèòì îñíîâàí íà èäåå ïîèñêà ñ âîçâðàòîì. Íàè-
áîëåå ðàñïðîñòðàíåííûì ìåòîäîì óñêîðåíèÿ ðàáîòû àëãîðèòìîâ, îñíî-
âàííûõ íà ïîèñêå ñ âîçâðàòîì, ÿâëÿåòñÿ ìåòîä âåòâåé è ãðàíèö, ñóòü
êîòîðîãî ñâîäèòñÿ ê òîìó, ÷òî ïîñëå ïðîñìîòðà êàæäîãî óçëà àíàëèçè-
ðóåòñÿ ïåðñïåêòèâíîñòü äàëüíåéøåãî àíàëèçà òåêóùåé âåòâè äåðåâà âîç-
ìîæíûõ ðåøåíèé. Åñëè, ñîãëàñíî âûáðàííûì êðèòåðèÿì, ìîæíî ñäåëàòü
âûâîä î òîì, ÷òî â äàííîé âåòâè äåðåâà ðåøåíèå íàéäåíî íå áóäåò (èëè îíî
áóäåò ñëàáåå îäíîãî èç óæå íàéäåííûõ, íàïðèìåð, ïðè âû÷èñëåíèè ñòåïå-
íè èçîìîðôíîñòè ãðàôîâ), òî äàííàÿ âåòâü ðåøåíèÿ ïðèçíàåòñÿ áåñïåðñ-
ïåêòèâíîé è åå äàëüíåéøèé àíàëèç ïðåêðàùàåòñÿ.
Íàèáîëåå âàæíûì â ìåòîäå âåòâåé è ãðàíèö ÿâëÿåòñÿ âûáîð ôóíêöèè
àíàëèçà ïåðñïåêòèâíîñòè òåêóùåé âåòâè ðåøåíèÿ. Àëãîðèòìû, îñíîâàí-
íûå íà ýòîì ìåòîäå, êàê ïðàâèëî, èìåþò íåïîëèíîìèàëüíóþ âû÷èñëè-
òåëüíóþ ñëîæíîñòü è îñíîâàíû íà ðåêóðñèâíîé ïðîöåäóðå ïåðåáîðà âñåõ
âîçìîæíûõ ðåøåíèé. Ïîýòîìó ÷åì ðàíüøå (ò.å. ïðè íàèìåíüøåì ÷èñëå
èñõîäíûõ äàííûõ) ìîæíî ðàñïîçíàòü áåñïåðñïåêòèâíîñòü òåêóùåé âåòâè
ðåøåíèÿ, òåì áîëüøå âðåìåíè óäàåòñÿ ñýêîíîìèòü.
Ïðè îïðåäåëåíèè ôóíêöèè àíàëèçà ïåðñïåêòèâíîñòè òåêóùåé âåòâè
ðåøåíèÿ ðàçðàáîò÷èê ñòîèò ïåðåä âûáîðîì ìåæäó óñëîæíåíèåì ñàìîé
ôóíêöèè, ÷òî âëå÷åò çà ñîáîé óìåíüøåíèå îáúåìà èñõîäíûõ äàííûõ, íà
îñíîâàíèè êîòîðûõ ìîæíî ñäåëàòü îäíîçíà÷íûé âûâîä î âîçìîæíîñòè
ïðåêðàùåíèÿ ïðîñìîòðà, è âîçìîæíûì óïðîùåíèåì ýòîé ôóíêöèè, ÷òî
ïîçâîëèò ñýêîíîìëåííîå íà àíàëèçå âðåìÿ èñïîëüçîâàòü äëÿ ñáîðà áîëü-
øåãî ÷èñëà èñõîäíûõ äàííûõ, ò. å. íà ïåðåáîð äîïîëíèòåëüíûõ âàðèàíòîâ
äåðåâà âîçìîæíûõ ðåøåíèé. Êàê ïðàâèëî, ïðè óâåëè÷åíèè ðàçìåðíîñòè
äàííûõ áîëåå ýôôåêòèâíûì ÿâëÿåòñÿ óñëîæíåíèå ôóíêöèè àíàëèçà.
Îñíîâíîé íåäîñòàòîê ìåòîäà âåòâåé è ãðàíèö çàêëþ÷àåòñÿ â òîì, ÷òî
îïåðàöèÿ àíàëèçà ïåðñïåêòèâíîñòè äàííîé âåòâè ðåøåíèÿ ïðîâîäèòñÿ íà
êàæäîì øàãå àëãîðèòìà. Âî ìíîãèõ ñëó÷àÿõ ýòî ïðèâîäèò ê ìíîãîêðàò-
íîìó âûïîëíåíèþ îäíîé è òîé æå îïåðàöèè. Äëÿ óñòðàíåíèÿ ýòîãî íåäîñ-
òàòêà èñïîëüçóåì ìàòðèöó âîçìîæíûõ ñîâìåùåíèé.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 21
Ìàòðèöà âîçìîæíûõ ñîâìåùåíèé. M — ýòî ìàòðèöà ðàçìåðîì N � N,
ãäå N — ÷èñëî âåðøèí â ñðàâíèâàåìûõ ãðàôàõ. Êàæäûé ýëåìåíò M i j,
ýòîé
ìàòðèöû ìîæåò ïðèíèìàòü çíà÷åíèÿ 0 èëè 1 â çàâèñèìîñòè îò òîãî, ìîãóò
ëè áûòü ñîâìåùåíû âåðøèíû i ãðàôà A è âåðøèíû j ãðàôà B.
Èñïîëüçîâàíèå ìàòðèöû ïîçâîëÿåò âûïîëíÿòü çíà÷èòåëüíûé îáúåì
ïðåäâàðèòåëüíûõ ïðîâåðîê è ôîðìèðîâàòü íà èõ îñíîâå ïðîñòîå óñëîâèå,
èñïîëüçóåìîå â ïåðåáîðíîé ÷àñòè àëãîðèòìà äëÿ îãðàíè÷åíèÿ ãëóáèíû
ïîèñêà.  ðàìêàõ ìàòðèöû ðåàëèçóåòñÿ ïðîâåðêà âñåõ îãðàíè÷åíèé, íå
îñíîâàííûõ íà èíôîðìàöèè, ïîëó÷åííîé â ïðîöåññå íàëîæåíèÿ âåðøèí.
Ïðîñòåéøèì óñëîâèåì, èñïîëüçóåìûì â êà÷åñòâå îãðàíè÷åíèÿ â ìàò-
ðèöå âîçìîæíûõ ñîâìåùåíèé, ÿâëÿåòñÿ ñðàâíåíèå ñòåïåíåé âåðøèí ãðà-
ôîâ. Î÷åâèäíî, ÷òî âåðøèíû ãðàôîâ ìîãóò áûòü ñîâìåùåíû òîëüêî â
ñëó÷àå, åñëè ñòåïåíè âåðøèí ñîâïàäàþò. Ýòî óñëîâèå âûãëÿäèò òàê:
M i j,
� 0, åñëè V Vi j1 2, ,
� , i V�1
1
.. , j V�1
2
.. ,
ãäå V — ÷èñëî âåðøèí ãðàôà; Vi — ñòåïåíü i-é âåðøèíû ãðàôà. Ê
ïðîñòåéøèì ïðîâåðêàì äëÿ îðèåíòèðîâàííûõ ãðàôîâ ìîæíî îòíåñòè
ñðàâíåíèå ÷èñëà âõîäÿùèõ è èñõîäÿùèõ äóã:
M i j,
� 0, åñëè V Vi j1 2, ,
èñ èñ
� , i V�1
1
..
èñ
, j V�1
2
..
èñ
;
M i j,
� 0, åñëè V Vi j1 2, ,
âõ âõ
� , i V�1
1
..
âõ
, j V�1
2
..
âõ
.
Ïîäõîä, ñîñòîÿùèé â âûíåñåíèè âñåõ ïðåäâàðèòåëüíûõ ïðîâåðîê â
îòäåëüíûé áëîê è ôîðìèðîâàíèè íà èõ îñíîâå ìàòðèöû âîçìîæíûõ ñîâ-
ìåùåíèé, èñïîëüçóåì äëÿ ïåðåáîðíûõ àëãîðèòìîâ ïðè ðåøåíèè çàäà÷è
óñòàíîâëåíèÿ èçîìîðôèçìà íà ãðàôàõ.
Èñïîëüçîâàíèå èíâàðèàíòîâ ïðè ôîðìèðîâàíèè ìàòðèöû âîç-
ìîæíûõ ñîâìåùåíèé. Ïðè ðåøåíèè çàäà÷è îá èçîìîðôíîñòè äâóõ ãðàôîâ
òî÷íîãî è îäíîâðåìåííî ýôôåêòèâíîãî àëãîðèòìà óñòàíîâëåíèÿ èçîìîðô-
íîñòè ãðàôîâ íà äàííûé ìîìåíò íå íàéäåíî, íî âî ìíîãèõ ñëó÷àÿõ çà
ïîëèíîìèàëüíîå âðåìÿ ìîæíî ïîäòâåðäèòü ãèïîòåçó î òîì, ÷òî äâà çàäàí-
íûõ ãðàôà íå èçîìîðôíû. Äëÿ ýòîãî èñïîëüçóþòñÿ èíâàðèàíòû. Íî äëÿ
óñòàíîâëåíèÿ èçîìîðôíîñòè ãðàôîâ èíâàðèàíòû íå áûëè èñïîëüçîâàíû,
õîòÿ îíè íåñóò äîñòàòî÷íî ìíîãî ïîëåçíîé èíôîðìàöèè.
Îáû÷íî èíâàðèàíòû âû÷èñëÿþòñÿ äëÿ âñåãî ãðàôà è äàþò îòâåò íà
âîïðîñ, ìîãóò ëè áûòü äâà ãðàôà èçîìîðôíû. Îäíàêî èíîãäà óæå íà
îñíîâàíèè äàííûõ èíâàðèàíòà ìîæíî ñêàçàòü, ÷òî ãðàôû íå èçîìîðôíû.
Íî ïîñêîëüêó èíâàðèàíòû âû÷èñëÿþòñÿ äëÿ ãðàôà â öåëîì, íèêàêîé äî-
ïîëíèòåëüíîé èíôîðìàöèè èñïîëüçóåìûì â äàëüíåéøåì ñòðîãèì àëãî-
ðèòìàì ïðîâåðêè íà èçîìîðôíîñòü îíè ïðåäîñòàâèòü íå ìîãóò, òàê êàê íå
ñîäåðæàò èíôîðìàöèè îá èçîìîðôíîñòè ÷àñòåé ãðàôîâ (ïîäãðàôîâ).
Ì. Á. Èëüÿøåíêî
22 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
Ðàññìîòðèì ìåòîäèêó, ïîçâîëÿþùóþ, ñ îäíîé ñòîðîíû, äëÿ ïðîèç-
âîëüíîãî èíâàðèàíòà ôîðìèðîâàòü èíôîðìàöèþ î âîçìîæíîé èçîìîðô-
íîñòè ïîäãðàôîâ, ñ äðóãîé — ñóùåñòâåííî óñèëèòü ïðàêòè÷åñêè ëþáîé
èíâàðèàíò. Áóäåì ïðèìåíÿòü èíâàðèàíò íå êî âñåìó ãðàôó, à ê ïîäãðàôàì
îêðóæåíèÿ âåðøèí (ïðè ýòîì ïîä ïîäãðàôîì îêðóæåíèÿ âåðøèíû ïîíè-
ìàåì íå òîëüêî âåðøèíû, íåïîñðåäñòâåííî ñâÿçàííûå ñ äàííîé, íî è
íàõîäÿùèåñÿ íà ðàññòîÿíèè K ðåáåð îò íåå). Âåëè÷èíà K — ïàðàìåòð,
ïîçâîëÿþùèé ãèáêî ðåãóëèðîâàòü ðàçìåðû ïîäãðàôîâ, äëÿ êîòîðûõ âû-
÷èñëÿþòñÿ èíâàðèàíòû.
Èíâàðèàíòû âû÷èñëÿåì äëÿ ïîäãðàôîâ îêðóæåíèÿ âñåõ âåðøèí îáîèõ
ãðàôîâ. Ïðè ýòîì ôîðìèðóåòñÿ èíôîðìàöèÿ î òîì, êàêèå âåðøèíû ìîãóò
áûòü ñîâìåùåíû, òàê êàê ïðè ñîâìåùåíèè âåðøèí äîëæíû ñîâìåñòèòüñÿ è
ïîäãðàôû èõ îêðóæåíèÿ. Êðîìå òîãî, ïîñêîëüêó ðàññìàòðèâàþòñÿ íå òîëü-
êî âåðøèíû, íî è ïîäãðàôû èõ îêðóæåíèÿ, ìû êàê áû çàãëÿäûâàÿ âïåðåä,
ïðîâåðÿåì, ìîãóò ëè ïðè ýòîì áûòü ñîâìåùåíû âåðøèíû èõ ïîäãðàôîâ
îêðóæåíèÿ.
Ðåçóëüòàòû âû÷èñëåíèÿ èíâàðèàíòîâ äëÿ ïîäãðàôîâ îêðóæåíèÿ âåð-
øèí èìåþò ñëåäóþùèé âèä:
ïóñòü P Ai ( ) — èíâàðèàíò ïîäãðàôà îêðóæåíèÿ âåðøèíû i ãðàôà A;
ïóñòü P Bj ( ) — èíâàðèàíò ïîäãðàôà îêðóæåíèÿ âåðøèíû j ãðàôà B;
åñëè P Ai ( )� P Bj ( ), òî M i j,
�0, òàê êàê âåðøèíà i ãðàôà A íå ìîæåò áûòü
ñîâìåùåíà ñ âåðøèíîé j ãðàôà B, ïîñêîëüêó ó íèõ íå ñîâïàäàþò èíâà-
ðèàíòû ïîäãðàôîâ îêðóæåíèÿ âåðøèí;
åñëè P Ai ( ) = P Bj ( ), òî íèêàêèõ èçìåíåíèé â ìàòðèöó âîçìîæíûõ èçìå-
íåíèé íå âíîñèòñÿ, òàê êàê ðàññìàòðèâàåòñÿ òîëüêî òà ÷àñòü âåðøèí ãðàôîâ,
íà êîòîðûõ âû÷èñëÿåòñÿ èíâàðèàíò, à ïî èíâàðèàíòàì ìîæíî îäíîçíà÷íî
ñäåëàòü âûâîä òîëüêî î íåèçîìîðôíîñòè ïîäãðàôîâ, â òî âðåìÿ êàê ñòðîãî
óñòàíîâèòü èçîìîðôíîñòü ìîæíî òîëüêî ñ ïîìîùüþ òî÷íîãî àëãîðèòìà.
Òàêèì îáðàçîì, èñïîëüçóÿ èíâàðèàíòû, ìîæíî ïîëó÷èòü äîïîëíèòåëüíóþ
èíôîðìàöèþ, îãðàíè÷èâàþùóþ äåðåâî âîçìîæíûõ ðåøåíèé.
Ðàññìîòðèì èíâàðèàíòû, ïðèìåíÿåìûå äëÿ ïðåäâàðèòåëüíîé ÷àñòè
àëãîðèòìà.
Èíâàðèàíò Zero2 ïðåäñòàâëÿåò ñîáîé óïîðÿäî÷åííûé âåêòîð ñòå-
ïåíåé âåðøèí, ñìåæíûõ äàííîé, è ÿâëÿåòñÿ ðàçâèòèåì èíâàðèàíòà Zero,
ïîäðîáíî îïèñàííîãî â [18].
Ïóñòü Z P R2
( , ) — èíâàðèàíò Zero2 ãðàôà G V E( , ), òîãäà P Vi i� ,
i V�1.. — âåêòîð, êîòîðûé õðàíèò ñòåïåíè âåðøèí ãðàôà G. Ìàòðèöà Ri j,
äëÿ êàæäîé âåðøèíû, èìåþùåé îáùåå ðåáðî ñ i-é, ñîäåðæèò ñòåïåíü ýòîé
ñìåæíîé âåðøèíû. Ýëåìåíòû êàæäîé ñòðîêè ìàòðèöû R óïîðÿäî÷èâàþòñÿ
ïî óáûâàíèþ. Ýëåìåíòû âåêòîðà P è ñòðîêè ìàòðèöû R ëåêñèêîãðàôè-
÷åñêè óïîðÿäî÷èâàþòñÿ ïî óáûâàíèþ.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 23
Ïîëó÷åííûé â ðåçóëüòàòå óïîðÿäî÷åííûé âåêòîð P è ìàòðèöà R ïðåä-
ñòàâëÿþò ñîáîé èíâàðèàíò. Ïðè íåñîâïàäåíèè õîòÿ áû îäíîãî èç ýëåìåí-
òîâ èíâàðèàíòû ðàçëè÷íû è ñîîòâåòñòâóþùèå èì ãðàôû íå ìîãóò áûòü
èçîìîðôíû.
Èíâàðèàíò íà îñíîâàíèè ìàòðèöû ðàññòîÿíèé ìåæäó âåðøèíàìè
ãðàôà ôîðìèðóåòñÿ ñëåäóþùèì îáðàçîì. Äëÿ êàæäîé âåðøèíû îïðåäå-
ëÿåì âåêòîð ðàññòîÿíèé äî âñåõ îñòàëüíûõ âåðøèí ãðàôà, èñïîëüçóÿ àëãî-
ðèòì Ôëîéäà. Äëÿ îðèåíòèðîâàííûõ ãðàôîâ ìîãóò áûòü äâå ìîäèôèêàöèè
äàííîãî èíâàðèàíòà (ïðè îäíîé ó÷èòûâàåòñÿ íàïðàâëåíèå äóã, à ïðè äðó-
ãîé íå ó÷èòûâàåòñÿ), ïðè÷åì îáå ìîäèôèêàöèè ìîãóò ïðèìåíÿòüñÿ ïîñëå-
äîâàòåëüíî, ïîñêîëüêó, â îáùåì ñëó÷àå, äîïîëíÿþò îäíà äðóãóþ.  ðå-
çóëüòàòå ïîëó÷àåì ìàòðèöó Di j,
.
Ïîëó÷åííûå âåêòîðû ðàññòîÿíèé äî îñòàëüíûõ âåðøèí ãðàôà, à òàêæå
ñòðîêè ìàòðèöû ñîðòèðóþòñÿ â ëåêñèãîãðàôè÷åñêîì ïîðÿäêå. Ïîëó÷åííûé â
ðåçóëüòàòå âåêòîð D ïðåäñòàâëÿåò ñîáîé èíâàðèàíò. Åñëè ïàðà ñîîòâåòñò-
âóþùèõ ýëåìåíòîâ ìàòðèöû D íå ñîâïàäàåò, òî èíâàðèàíòû ÿâëÿþòñÿ ðàç-
ëè÷íûìè, à ñîîòâåòñòâóþùèå èì ãðàôû íå ìîãóò áûòü èçîìîðôíû.
Èíâàðèàíò First [19] ÿâëÿåòñÿ �-èíâàðèàíòîì ïåðâîãî ïîðÿäêà. Ïðè
îòíîñèòåëüíî íåáîëüøèõ âû÷èñëèòåëüíûõ çàòðàòàõ ýòî äîñòàòî÷íî ñèëü-
íûé èíâàðèàíò.  îáùåì ñëó÷àå ìîãóò áûòü ñîçäàíû �-èíâàðèàíòû è
áîëåå âûñîêèõ ïîðÿäêîâ (â ÷àñòíîñòè, �-èíâàðèàíò âòîðîãî ïîðÿäêà Sec-
ond), íî äëÿ ïîñòàâëåííîé çàäà÷è, êîãäà â áîëüøèíñòâå ñëó÷àåâ ðàññìàò-
ðèâàþòñÿ îòíîñèòåëüíî íåáîëüøèå ãðàôû, èñïîëüçîâàíèå �-èíâàðèàíòîâ
áîëåå âûñîêèõ ïîðÿäêîâ íå îïðàâäàíî, ïîñêîëüêó óâåëè÷èâàåòñÿ ñëîæ-
íîñòü àëãîðèòìà âû÷èñëåíèÿ èíâàðèàíòà, à äîïîëíèòåëüíîãî âûèãðûøà
íà ñòîëü íåáîëüøèõ ãðàôàõ ïîëó÷èòü íå óäàåòñÿ.
Ïðåäâàðèòåëüíàÿ ÷àñòü àëãîðèòìà. Âñå îïåðàöèè, âûïîëíÿåìûå
îäíîêðàòíî â ïðîöåññå ðàáîòû àëãîðèòìà, âûíîñèì â ïðåäâàðèòåëüíóþ
÷àñòü. Îñíîâíîé ÿâëÿåòñÿ îïåðàöèÿ ôîðìèðîâàíèÿ ìàòðèöû âîçìîæíûõ
ñîâìåùåíèé, îïèñàííîé âûøå, ñ èñïîëüçîâàíèåì èíâàðèàíòîâ äëÿ ïîä-
ãðàôîâ îêðóæåíèÿ âåðøèí.
 ïðîãðàììå ðåàëèçîâàíû ñëåäóþùèå ïðåäâàðèòåëüíûå ïðîâåðêè,
ôîðìèðóþùèå ìàòðèöó âîçìîæíûõ ñîâìåùåíèé:
1. M i j,
�0, åñëè V Vi j1 2, ,
� , ãäå V X Y, — ñòåïåíü âåðøèíû Y ãðàôà X;
2. M i j,
�0, åñëè V Vi j1 2, ,
âõ âõ
� , ãäå V X Y,
âõ
— ÷èñëî âõîäÿùèõ ðåáåð
âåðøèíû Y ãðàôà X;
3. M i j,
�0, åñëè V Vi j1 2, ,
èñ èñ
� , ãäå V X Y,
èñ
— ÷èñëî èñõîäÿùèõ ðåáåð
âåðøèíû Y ãðàôà X;
Ì. Á. Èëüÿøåíêî
24 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
4. M i j,
�0, åñëè Z Zi j i j1 2, , , ,
� , j V i�1
1
..
,
, ãäå ZX i,
— ñòðîêà èíâàðèàí-
òà Zero2 ãðàôà X, ñîîòâåòñòâóþùàÿ âåðøèíå i;
5. M i j,
�0, åñëè W Wi j1 2, ,
â â
� , ãäå WX Y,
â
— ÷èñëî âåðøèí â âîëíîâîì
ðàçëîæåíèè ãðàôà X, íà÷èíàÿ ñ âåðøèíû Y;
6. M i j,
�0, åñëè W Wi l
l
k
j l
l
k
1
1
2
1
, , , ,
â â
� �
� , k WX Y�1..
,
â
, ãäå WX Y l, ,
â
— ÷èñëî
âåðøèí â l-é âîëíå âîëíîâîãî ðàçëîæåíèÿ ãðàôà X íà÷èíàÿ ñ âåðøèíû Y;
7. M i j,
�0, åñëè W Wi j1 2, ,
p p
� , ãäå WX Y,
p
— ÷èñëî ðåáåð â âîëíîâîì
ðàçëîæåíèè ãðàôà X, íà÷èíàÿ ñ âåðøèíû Y;
8. M i j,
�0, åñëè W Wi l
l
k
j l
l
k
1
1
2
1
, , , ,
p p
� �
� , k W j�1
2
..
,
p
, ãäå WX Y l, ,
p
— ÷èñëî
ðåáåð â l-é âîëíå âîëíîâîãî ðàçëîæåíèÿ ãðàôà X, íà÷èíàÿ ñ âåðøèíû Y.
Ïåðåä íà÷àëîì íåïîëèíîìèàëüíîé ÷àñòè àëãîðèòìà (íàëîæåíèÿ âåð-
øèí ñ âîçâðàòîì) ïðîâîäèòñÿ ñîðòèðîâêà âåðøèí îáîèõ ãðàôîâ. Ýòî
äåéñòâèå çàíèìàåò äîïîëíèòåëüíîå ìàøèííîå âðåìÿ, íî äëÿ åãî âûïîë-
íåíèÿ èìååòñÿ ðÿä îñíîâàíèé.
Ñîðòèðîâêà âåðøèí ãðàôîâ ïðîâîäèòñÿ äëÿ óñêîðåíèÿ íàõîæäåíèÿ èçî-
ìîðôíîé ïîäñòàíîâêè â ñëó÷àå, åñëè òàêàÿ ïîäñòàíîâêà ñóùåñòâóåò.  ïåðå-
áîðíîé ÷àñòè àëãîðèòìà ïåðåñòàâëÿþòñÿ òîëüêî âåðøèíû ïåðâîãî ãðàôà, à
ïîðÿäîê âåðøèí âòîðîãî ãðàôà íå ìåíÿåòñÿ. Ïîðÿäîê ñëåäîâàíèÿ âåðøèí
ìåíüøåãî ãðàôà îïðåäåëÿåòñÿ â ïðåäâàðèòåëüíîé ÷àñòè àëãîðèòìà.
Ïóñòü T i2,
— ÷èñëî ðåáåð èíöèäåíòíûõ âåðøèíàì ñ ìåíüøèìè íîìå-
ðàìè è P Mi j i
j
V
2
1
1
, ,
�
�
— ñóììàðíîå ÷èñëî âàðèàíòîâ ñîâìåùåíèÿ âåðøèíû
i ãðàôàG
2
ñ âåðøèíàìè ãðàôàG
1
. Òîãäà ïîðÿäîê ñîðòèðîâêè âåðøèí ãðàôà
G
2
ñëåäóþùèé: V Vi k2 2, ,
� ïðè T Tk
j i
V
j2
1
2
2
, ,
min( )�
�
. Åñëè T Ti j2 2, ,
� , òîV Vi k2 2, ,
� ,
ïðè P P Pk i j2 2 2, , ,
min( , )� . Ñëåäîâàòåëüíî, âåðøèíû ãðàôà G
2
ñîðòèðóþòñÿ â
ïîðÿäêå óáûâàíèÿ ÷èñëà ñâÿçåé ñ âåðøèíàìè, èìåþùèìè ìåíüøèå íî-
ìåðà, èëè â ïîðÿäêå óáûâàíèÿ ÷èñëà âàðèàíòîâ ñîâìåùåíèÿ âåðøèí, åñëè
÷èñëo ñâÿçåé îäèíàêîâî. Òàêîé ïîðÿäîê ñëåäîâàíèÿ âåðøèí îáóñëîâëåí
òåì, ÷òî ÷åì áîëüøå ñâÿçåé ñ ñîâìåùåííûìè èìååò âåðøèíà, òåì áîëåå
ñòðîãèì áóäåò îãðàíè÷èâàþùåå óñëîâèå, âêëþ÷àþùåå ýòó âåðøèíó, è
ìåíüøå îáùåå ÷èñëî ñîâìåùåíèé, êîòîðûå íåîáõîäèìî ïåðåáðàòü.
Îñíîâíàÿ (ïåðåáîðíàÿ) ÷àñòü àëãîðèòìà ïðåäñòàâëÿåò ñîáîé ïîñëå-
äîâàòåëüíîå íàëîæåíèå âåðøèí ñ âîçâðàòîì, îïèñûâàòü êîòîðîå óäîáíî â
òåðìèíàõ ìåòîäà ïîèñêà â ïðîñòðàíñòâå ñîñòîÿíèé.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 25
Âåðøèíû ãðàôà G
2
îñòàþòñÿ íåòðîíóòûìè è êàæäîé èç íèõ ñòàâèòñÿ â
ñîîòâåòñòâèå îäíà èç âåðøèí ãðàôà G
1
. Ïðè ýòîì ïðîâåðÿåòñÿ äîïóñ-
òèìîñòü òàêîãî ñîâìåùåíèÿ. Åñëè óäàåòñÿ íàéòè ñîîòâåòñòâèå âñåì âåð-
øèíàì ãðàôàG
2
è ïðè ýòîì âûïîëíÿåòñÿ óñëîâèå èçîìîðôèçìà, òî íàéäåí-
íîå ñîñòîÿíèå âîçâðàùàåòñÿ êàê èñêîìàÿ ïîäñòàíîâêà.
Ïóñòü T i1,
— ÷èñëî ñâÿçåé âåðøèíû i ãðàôà G
1
ñ âåðøèíàìè V sj1 1,
( )�� ,
à T i2,
— ÷èñëî ñâÿçåé âåðøèíû i ãðàôà G
2
ñ âåðøèíàìè V sj2 2,
( )�� .
Íà÷àëüíîìó ñîñòîÿíèþ � ( )s
0
0� ñîîòâåòñòâóåò ñîñòîÿíèå, ïðè êîòîðîì
åùå íå ñîâìåùåíî íè îäíîé ïàðû âåðøèí.
Äëÿ ïîëó÷åíèÿ i-ãî ñîñòîÿíèÿ âåðøèíû V i2,
èùåì ñîîòâåòñòâèå ñðåäè
âåðøèíV j1,
òàêèõ, ÷òî:
1. M i j,
�1, ò.å. âåðøèíû ñîâìåñòèìû íà îñíîâàíèè ïðåäâàðèòåëüíûõ
ïðîâåðîê;
2. T i1,
= T j2,
;
3. Äëÿ k i�1... , åñëè ( , )v v Ei k �
1
, òî ( ( ), ( ))� �v v Ei k �
2
.
Åñëè âûïîëíåíû âñå òðè óñëîâèÿ, èç êîòîðûõ òðåòüå ÿâëÿåòñÿ ïðÿìûì
ñëåäñòâèåì îïðåäåëåíèÿ èçîìîðôèçìà, òî ñîîòâåòñòâóþùàÿ ïàðà âåðøèí
âõîäèò â ÷àñòè÷íóþ ïîäñòàíîâêó è ôîðìèðóåòñÿ íîâîå ñîñòîÿíèå � ( )s i .
Ïåðåáîð ñîñòîÿíèé ïðîâîäèòñÿ ìåòîäîì ïîèñêà â ãëóáèíó.
×èñëåííàÿ îöåíêà âû÷èñëèòåëüíîé ñëîæíîñòè àëãîðèòìà. Äëÿ
îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè àëãîðèòìà ìîæíî ïðèìåíÿòü êàê àíà-
ëèòè÷åñêèå ìåòîäû, òàê è ÷èñëåííûé ýêñïåðèìåíò. Ðàçðàáîòàííûé àëãî-
ðèòì ÷åòêî äåëèòñÿ íà äâå ÷àñòè:
1. Ïðåäâàðèòåëüíûå ïðîâåðêè è ïðåîáðàçîâàíèÿ (ôîðìèðîâàíèå ìàò-
ðèöû âîçìîæíûõ ñîâìåùåíèé);
2. Ðåêóðñèâíûé îáõîä äåðåâà âîçìîæíûõ ðåøåíèé (ïîñëåäîâàòåëüíîå
íàëîæåíèå âåðøèí ñ âîçâðàòîì).
 ïðåäâàðèòåëüíîé ÷àñòè àëãîðèòìà ïðèìåíÿþòñÿ èíâàðèàíòû è äðó-
ãèå àëãîðèòìû, âû÷èñëèòåëüíàÿ ñëîæíîñòü êîòîðûõ èçâåñòíà, è äîêàçàíî,
÷òî âû÷èñëèòåëüíàÿ ñëîæíîñòü êàæäîãî èç ýòèõ àëãîðèòìîâ ïîëèíîìèàëü-
íàÿ. Ñëåäîâàòåëüíî, è âû÷èñëèòåëüíàÿ ñëîæíîñòü âñåõ àëãîðèòìîâ, èñïîëü-
çóåìûõ â ïðåäâàðèòåëüíîé ÷àñòè, áóäåò ïîëèíîìèàëüíàÿ.
Îñíîâíîé èíòåðåñ ïðè ýòîì ïðåäñòàâëÿåò âû÷èñëèòåëüíàÿ ñëîæíîñòü
âòîðîé (ðåêóðñèâíîé) ÷àñòè àëãîðèòìà.  îáùåì ñëó÷àå îíà ÿâëÿåòñÿ íå-
ïîëèíîìèàëüíîé, íî äëÿ ìíîãèõ êëàññîâ ãðàôîâ ýòà îöåíêà ìîæåò áûòü
çíà÷èòåëüíî íèæå.
Äëÿ îïðåäåëåíèÿ âû÷èñëèòåëüíîé ñëîæíîñòè àëãîðèòìà áûëè ïðîâå-
äåíû èññëåäîâàíèÿ.  êà÷åñòâå èñõîäíûõ äàííûõ áûëè âçÿòû ñëó÷àéíî
ñãåíåðèðîâàííûå ãðàôû ñ ïëîòíîñòüþ ðåáåðíîãî çàïîëíåíèÿ îò 0,1 äî 0,5
è ÷èñëîì âåðøèí îò 20 äî 1000.  êà÷åñòâå ðåçóëüòàòà íà ãðàôèêàõ èñïîëü-
çîâàëîñü óñðåäíåííîå âðåìÿ ïðîâåðêè 100 ïàð ãðàôîâ. Âñå ïàðû ïðîâåðÿåìûõ
Ì. Á. Èëüÿøåíêî
26 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
ãðàôîâ áûëè èçîìîðôíû, ïîñêîëüêó îíè áîëåå ñëîæíû äëÿ ïðîâåðêè, ÷åì
íåèçîìîðôíûå ãðàôû, ïîäòâåðæäåíèå íåèçîìîðôíîñòè êîòîðûõ ìîæíî ïî-
ëó÷èòü â áîëüøèíñòâå ñëó÷àåâ íà ýòàïå ïðåäâàðèòåëüíûõ ïðîâåðîê è
ïðåîáðàçîâàíèé.
Áûëà èññëåäîâàíà ìîäèôèêàöèÿ àëãîðèòìà, èñïîëüçóþùàÿ èíâàðèàíò
ZERO2. Ýòî äîñòàòî÷íî ïðîñòîé, íî äîñòàòî÷íî ñèëüíûé èíâàðèàíò äëÿ
êëàññà ïðîèçâîëüíûõ ãðàôîâ (áåç ñïåöèàëüíûõ ñâîéñòâ, òàêèõ êàê ðåãó-
ëÿðíîñòü èëè ñèëüíîðåãóëÿðíîñòü). Ýòà ìîäèôèêàöèÿ ïîçâîëÿåò îöåíèòü
âêëàä ïðåäâàðèòåëüíîé ÷àñòè àëãîðèòìà â îáùóþ âû÷èñëèòåëüíóþ ñëîæ-
íîñòü, ïîñêîëüêó ñóùåñòâóåò âîçìîæíîñòü ñðàâíèòü ïîëó÷åííûå ðåçóëü-
òàòû ñ îöåíêîé ïðîèçâîäèòåëüíîñòè òîëüêî ðåêóðñèâíîé ÷àñòè àëãîðèòìà.
Ðåçóëüòàòû èññëåäîâàíèé ïðèâåäåíû íà ðèñ. 1.
Êàê âèäíî èç ðèñ. 1, à, ÷åì âûøå ïëîòíîñòü ðåáåðíîãî çàïîëíåíèÿ
ãðàôîâ, òåì íèæå ïðîèçâîäèòåëüíîñòü àëãîðèòìà. Â ýêñïîíåíöèàëüíîé
ñèñòåìå êîîðäèíàò (ñì. ðèñ. 1, á) óäîáíî ñðàâíèâàòü âû÷èñëèòåëüíóþ
ñëîæíîñòü àëãîðèòìà ñ ýêñïîíåíöèàëüíîé ôóíêöèåé, êîòîðàÿ â äàííîé
ñèñòåìå êîîðäèíàò ïðåäñòàâëÿåò ñîáîé ïðÿìóþ ëèíèþ. Êàê âèäèì, â äàí-
íîì ñëó÷àå êðèâûå ïðîèçâîäèòåëüíîñòè èìåþò ôîðìó äóãè, ÷òî ñâèäå-
òåëüñòâóåò î ñóáýêñïîíåíöèàëüíîì õàðàêòåðå âû÷èñëèòåëüíîé ñëîæíîñòè
àëãîðèòìà.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 27
t
2
1
0
Y
Y
Y
Y
Y
0
1
2
3
4
= 10 %
= 20 %
= 30 %
= 40 %
= 50 %
Y
0
Y
0
Y
1
Y
1
Y
2
Y
2Y
3
Y
3Y
4
Y
4
200 400 600 800 1000 N 200 400 600 800 1000 N
lg ( )
1
0,1
0,01
1 10
t
�
�
Y
0
Y
1
Y
2
Y
3
Y
4
10 100 1 10�
lg ( )N
lg ( )
1
0,1
0,01
1 10
t
�
�
à á
â
Ðèñ. 1. Çàâèñèìîñòü âðåìåíè t ïðîâåðêè
íà èçîìîðôíîñòü îò ÷èñëà âåðøèí N
äëÿ ðàçëè÷íûõ çíà÷åíèé ïëîòíîñòè ðå-
áåðíîãî çàïîëíåíèÿ Y â ñèñòåìå êîîð-
äèíàò: à — ëèíåéíîé; á — ýêñïîíåí-
öèàëüíîé; â — ëîãàðèôìè÷åñêîé
 ëîãàðèôìè÷åñêîé ñèñòåìå êîîðäèíàò ïîëèíîìèàëüíûé àëãîðèòì
îáðàçóåò ïðÿìóþ ëèíèþ. Êàê âèäíî èç ðèñ. 1, â, ñ óâåëè÷åíèåì ÷èñëà
âåðøèí êðèâûå â òî÷íîñòè ñîâïàäàþò ñ ïðÿìîé ëèíèåé, ÷òî ïîäòâåðæäàåò
ãèïîòåçó î ïðèáëèæåííîñòè âû÷èñëèòåëüíîé ñëîæíîñòè àëãîðèòìà ê ïî-
ëèíîìèàëüíîé ïðè âîçðàñòàíèè ÷èñëà âåðøèí â ñðàâíèâàåìûõ ãðàôàõ.
Îäíàêî â îáùåì ñëó÷àå àëãîðèòì îñòàåòñÿ ãèïåðïîëèíîìèàëüíûì.
Áàçà ãðàôîâ äëÿ ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðî-
âåðêè ãðàôîâ íà èçîìîðôíîñòü. Îòñóòñòâèå ñòàíäàðòíîé áàçû ãðàôîâ
äëÿ îïðåäåëåíèÿ ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðîâåðêè ãðàôîâ íà èçî-
ìîðôíîñòü ïðèâîäèò ê íåîäíîçíà÷íîñòè ïðè îöåíêå ïîëó÷åííûõ êàæäûì
èññëåäîâàòåëåì ýêñïåðèìåíòàëüíûõ ðåçóëüòàòîâ è èõ ñðàâíåíèè ñ ðåçóëü-
òàòàìè, ïîëó÷åííûìè ïðè èñïîëüçîâàíèè äðóãèõ àëãîðèòìîâ.
 ðàáîòàõ [14, 20] ïðåäëîæåíà áàçà ãðàôîâ äëÿ ïðîâåäåíèÿ ñðàâíåíèé
ðàçëè÷íûõ àëãîðèòìîâ, îïðåäåëåíèÿ èõ õàðàêòåðèñòèê è ïðîèçâîäèòåëü-
íîñòè íà îäíîì, ñòàíäàðòíîì íàáîðå ãðàôîâ. Ïðåäëàãàåìàÿ áàçà ãðàôîâ
îòâå÷àåò ñëåäóþùèì òðåáîâàíèÿì:
1. Ïðåäîñòàâëÿåò øèðîêèé ñïåêòð ãðàôîâ, ïîêðûâàþùèõ áîëüøóþ
îáëàñòü èõ âîçìîæíûõ ïðèìåíåíèé.
2. Ñîäåðæèò ïàðû ãðàôîâ, ïîçâîëÿþùèõ ñðàâíèâàòü àëãîðèòìû ðåøå-
íèÿ ðàçëè÷íûõ êëàññîâ çàäà÷, áëèçêèõ ê èçîìîðôèçìó (ãðàô-ïîäãðàô èçî-
ìîðôèçì, íàõîæäåíèå íàèáîëüøåãî îáùåãî ïîäãðàôà è äð.).
3. Ñîäåðæèò ãðàôû ðàçëè÷íîãî ðàçìåðà ñ ðàçëè÷íûì ÷èñëîì ðåáåð è
ïàðàìåòðàìè èõ ðàñïðåäåëåíèÿ.
Òèïû ãðàôîâ, âõîäÿùèõ â ñîñòàâ áàçû ãðàôîâ. 1. Ñëó÷àéíî ñãåíåðè-
ðîâàííûå ãðàôû — ãðàôû, â êîòîðûõ ñâÿçè ìåæäó âåðøèíàìè íå îáðàçóþò
íèêàêèõ ðåãóëÿðíûõ ñòðóêòóð (ðèñ. 2). Îñíîâíîé õàðàêòåðèñòèêîé òàêèõ
ãðàôîâ ÿâëÿåòñÿ ïëîòíîñòü ðåáåðíîãî çàïîëíåíèÿ �. ×èñëî ðåáåð ñîñ-
òàâëÿåò E
N N
�
�
�
( )1
2
.
2. Ðåãóëÿðíûå è íåðåãóëÿðíûå ñåòè — ãðàôû, ñîäåðæàùèå ðåãóëÿðíûå
ñòðóêòóðû òèïà ñåòè (2D, 3D è 4D). Èçâåñòíî, ÷òî ãðàôû, ñîäåðæàùèå
Ì. Á. Èëüÿøåíêî
28 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
Ðèñ. 2. Ñëó÷àéíî ñãåíåðèðîâàííûé ãðàô ñ ïàðàìåòðàìè N = 5 è � = 0,2, Å = 4
ðåãóëÿðíûå ñòðóêòóðû, ãîðàçäî ñëîæíåå ñðàâíèâàòü íà èçîìîðôíîñòü, ÷åì
ãðàôû, íå ñîäåðæàùèå ðåãóëÿðíûõ ñòðóêòóð. Â áàçå ñîäåðæàòñÿ ðåãóëÿð-
íûå è íåðåãóëÿðíûå ñåòè (òàáë. 1). Íåðåãóëÿðíûå ñåòè ïîëó÷àþòñÿ èç
ðåãóëÿðíûõ äîáàâëåíèåì íåêîòîðîãî ÷èñëà ñëó÷àéíîðàñïîëîæåííûõ ðå-
áåð. Äëÿ îïèñàíèÿ íåðåãóëÿðíûõ ñåòåé èñïîëüçóåòñÿ ïàðàìåòð �. ×èñëî
äîáàâëÿåìûõ ðåáåð N�. Ðåãóëÿðíûå ñåòè 2D — ýòî ãðàôû, ó êîòîðûõ âñå
âåðøèíû, êðîìå ëåæàùèõ íà ãðàíèöå, èìåþò ñâÿçè ñ ÷åòûðüìÿ ñîñåäíèìè.
Àíàëîãè÷íî 3D ñåòè — ýòî ãðàôû, ó êîòîðûõ êàæäàÿ âåðøèíà ñîåäèíåíà ñ
øåñòüþ ñîñåäíèìè, à 4D ñåòè — ñ âîñåìüþ. Âñå ñåòè îòêðûòû, ò.å. âåð-
øèíû íà âíåøíåé ãðàíèöå ñåòè èìåþò ñâÿçè òîëüêî ñ âíóòðåííèìè âåðøè-
íàìè ýòîé ñåòè (ðèñ. 3).
3. Ðåãóëÿðíûå ãðàôû ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí V — ãðàôû,
êàæäàÿ âåðøèíà êîòîðûõ èìååò íåêîòîðîå îãðàíè÷åííîå ÷èñëî èíöèäåíòíûõ
ðåáåð (êàê âõîäÿùèõ, òàê è èñõîäÿùèõ). Ýòî ðåãóëÿðíûå ãðàôû (ðèñ. 4, à),
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 29
à á
Ðèñ. 3. Ðåãóëÿðíàÿ (à) è íåðåãóëÿðíàÿ (b) ñåòè ñ ïàðàìåòðàìè N = 5, � = 0,2 äëÿ íåðå-
ãóëÿðíîé ñåòè, â êîòîðóþ äîáàâëåíî ïÿòü ðåáåð
à á
Ðèñ. 4. Ðåãóëÿðíûé (a) è íåðåãóëÿðíûé (b) ãðàôû ñ ôèêñèðîâàííîé ñòåïåíüþ âåðøèí ñ
ïàðàìåòðàìè N = 8 è V = 5, � = 0,1 (â íåðåãóëÿðíîì ãðàôå ïåðåìåùåíî 10 % ðåáåð)
ïîëó÷àåìûå ïîñëåäîâàòåëüíûì äîáàâëåíèåì ñëó÷àéíî ðàñïîëîæåííûõ ðå-
áåð äî òåõ ïîð, ïîêà ñòåïåíü êàæäîé âåðøèíû íå äîñòèãíåò çàäàííîé âåëè÷è-
íû. Íåâîçìîæíî ïîëó÷èòü ãðàôû ñ íå÷åòíûì ÷èñëîì âåðøèí è íå÷åòíîé ñòå-
ïåíüþ êàæäîé âåðøèíû, ïîýòîìó â áàçå ãðàôîâ òàêèå ãðàôû îòñóòñòâóþò.
4. Íåðåãóëÿðíûå ãðàôû ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí — ýòî ãðà-
ôû, â êîòîðûõ ñðåäíÿÿ ñòåïåíü âåðøèí ÿâëÿåòñÿ íåêîòîðîé, çàðàíåå îïðå-
äåëåííîé âåëè÷èíîé, íî ïðè ýòîì ñòåïåíè íåêîòîðûõ îòäåëüíûõ âåðøèí
ìîãóò çíà÷èòåëüíî îòëè÷àòüñÿ îò ýòîãî ïðåäîïðåäåëåííîãî çíà÷åíèÿ. Òà-
êèå ãðàôû (ðèñ. 4, á) ïîëó÷àþòñÿ èç ðåãóëÿðíûõ ãðàôîâ ñ îãðàíè÷åííîé
ñòåïåíüþ âåðøèí ñëó÷àéíûì ïåðåìåùåíèåì íåêîòîðîãî ÷èñëà ðåáåð â
ãðàôå. Äëÿ íåðåãóëÿðíûõ ãðàôîâ ââîäèòñÿ äîïîëíèòåëüíûé ïàðàìåòð � —
ïðîöåíò ñëó÷àéíî ïåðåìåùàåìûõ ðåáåð â ðåãóëÿðíîì ãðàôå.
Ì. Á. Èëüÿøåíêî
30 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
Òèï ãðàôîâ ×èñëî ïàð Ïàðàìåòðû
Ðàçìåð ãðàôà
(÷èñëî âåðøèí)
Ñëó÷àéíî ñãåíåðèðîâàííûå
ãðàôû
1000 � = 0,01 20—1000
1000 � = 0,005 20—1000
1000 � = 0,001 20—1000
Ðåãóëÿðíûå ñåòè 1000 2D ñåòü 16—1024
800 3D ñåòü 27—1000
500 4D ñåòü 16—1296
Íåðåãóëÿðíûå ñåòè 3000 Íåðåãóëÿðíûå 2D ñåòè
� = {0,2; 0,4; 0,6}
16—1024
2400 Íåðåãóëÿðíûå 3D ñåòè
� = {0,2; 0,4; 0,6}
27—1000
1500 Íåðåãóëÿðíûå 4D ñåòè
� = {0,2; 0,4; 0,6}
16—1296
Ðåãóëÿðíûå ãðàôû ñ îãðàíè-
÷åííîé ñòåïåíüþ âåðøè
1000 V = 3 20—1000
1000 V = 6 20—1000
1000 V = 9 20—1000
Íåðåãóëÿðíûå ãðàôû ñ îãðà-
íè÷åííîé ñòåïåíüþ âåðøèí
1000
1000
1000
V = 3, � = 0,1
V = 6, � = 0,1
V = 9, � = 0,1
20—1000
20—1000
20—1000
 ñ å ã î 18200
Ï ð è ì å ÷ à í è å: Íàáîð ãðàôîâ, èñïîëüçîâàííûé äëÿ ñðàâíèòåëüíîãî àíàëèçà àëãîðèòìîâ,
âçÿò íà ñàéòå SIVALab (http://amalfi.dis.unina.it/graph/db/graphs/).
Òàáëèöà 1. Áàçà ãðàôîâ äëÿ ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè
àëãîðèòìîâ ïðîâåðêè íà èçîìîðôíîñòü
Èñïîëüçîâàííûå àëãîðèòìû è îðãàíèçàöèÿ ñðàâíåíèÿ èõ ïðîèç-
âîäèòåëüíîñòè. Äëÿ ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðîâåð-
êè ãðàôîâ íà èçîìîðôíîñòü èñïîëüçîâàíû àëãîðèòìû òîãî æå êëàññà (ò. å.
òî÷íûå àëãîðèòìû, îñíîâàííûå íà ìåòîäå âåòâåé è ãðàíèö è åãî ìîäèôè-
êàöèÿõ). Èç èìåþùèõñÿ àëãîðèòìîâ âûáðàíû íàèáîëåå áûñòðûå (VF è
VF2) è íàèáîëåå ðàñïðîñòðàíåííûå ïðè ðåàëèçàöèè ñèñòåì, èñïîëüçóþ-
ùèõ îïåðàöèþ óñòàíîâëåíèÿ èçîìîðôíîñòè, äàâíî è õîðîøî èññëåäî-
âàííûå (SD è ULL). Èñïîëüçîâàí òàê æå àëãîðèòì, îïèñàííûé â [16, 17], ïî
êîòîðîìó áûë ïðîñ÷èòàí ïîëíûé íàáîð íåèçîìîðôíûõ ãðàôîâ ñ ÷èñëîì
âåðøèí äî 11 âêëþ÷èòåëüíî (öåëü ðàçðàáîòêè àëãîðèòìà óñòàíîâëåíèÿ
èçîìîðôíîñòè, â ÷àñòíîñòè, âêëþ÷àåò ïîëó÷åíèå ïîëíûõ íàáîðîâ ãðàôîâ,
îáëàäàþùèõ ñïåöèàëüíûìè ñâîéñòâàìè, â òîì ÷èñëå è íåèçîìîðôíûõ).
Äëÿ ïðîâåäåíèÿ èññëåäîâàíèé áûë èñïîëüçîâàí Linux Mandrake 9.2, êîì-
ïèëÿòîð gcc 3.3.1. Ðàñ÷åòû ïðîâåäåíû íà êîìïüþòåðå AMD Athlon XP 1700+,
512 Mb RAM. Àëãîðèòìû VF, VF2, SD è ULL ïîëó÷åíû â ðåàëèçàöèè
áèáëèîòåêè VFLib (http://amalfi.dis.unina.it/graph/db/vflib-2.0/vflib2.tgz).
Äëÿ îïðåäåëåíèÿ âðåìåíè âûïîëíåíèÿ àëãîðèòìà èñïîëüçîâàíî âðåìÿ
ðàáîòû ïðîãðàììû, ïîëó÷àåìîå ôóíêöèåé clock() áèáëèîòåêè glibñ. Âðåìÿ
îïðåäåëÿëîñü äëÿ 100 ïàð ãðàôîâ.  ïðîöåññå âû÷èñëåíèé ðàáîòà ïðîãðàì-
ìû ïðåðûâàëàñü, åñëè î÷åðåäíàÿ ïàðà ñðàâíèâàåìûõ ãðàôîâ ïðîâåðÿëàñü
àëãîðèòìîì áîëåå 200 ñ ìàøèííîãî âðåìåíè. Åñëè õîòÿ áû îäíà ïàðà
ãðàôîâ ñ çàäàííûì ÷èñëîì âåðøèí ïðîâåðÿëàñü áîëüøå 200 ñ, òî ðåçóëüòà-
òû èçìåðåíèé äëÿ âñåõ ãðàôîâ ñ òàêèì ÷èñëîì âåðøèí íå ó÷èòûâàëèñü.
Àíàëèç ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðîâåðêè ãðàôîâ íà
èçîìîðôíîñòü. Ïî ðåçóëüòàòàì èññëåäîâàíèÿ øåñòè àëãîðèòìîâ ïîñòðîå-
íû ãðàôèêè ñðàâíåíèÿ ãðàôîâ íà èçîìîðôíîñòü (ðèñ. 5) â ýêñïîíåíöèàëü-
íîé ñèñòåìå êîîðäèíàò, íà êîòîðûõ èñïîëüçîâàíû ñëåäóþùèå îáîçíà-
÷åíèÿ: VF è VF2 — àëãîðèòìû Ôîãèÿ (êðèâûå 1, 2); SD — àëãîðèòì
Øìèäòà — Äðþôåëÿ (êðèâàÿ 3); ULL — àëãîðèòì Óëìàíà (êðèâàÿ 4);
ISOMORF — àëãîðèòì Ïèí÷óêà (êðèâàÿ 5); ISOMORPH — àëãîðèòì
àâòîðà (êðèâàÿ 6).
Ïî ôîðìå êðèâûõ ìîæíî ñóäèòü î õàðàêòåðå èçìåíåíèÿ âðåìåíè ðàáî-
òû àëãîðèòìîâ â çàâèñèìîñòè îò ÷èñëà âåðøèí â èññëåäóåìûõ ãðàôàõ.
Ýêñïîíåíöèàëüíûé õàðàêòåð èçìåíåíèÿ âðåìåíè âû÷èñëåíèé ïðåäñòàâ-
ëÿåò ñîáîé ïðÿìóþ ëèíèþ â òàêîé ñèñòåìå êîîðäèíàò. Ñðàâíåíèå êðèâîé
ïðîèçâîäèòåëüíîñòè àëãîðèòìà èìåííî ñ ýêñïîíåíòîé ïðåäñòàâëÿåò îñî-
áûé èíòåðåñ ïîòîìó, ÷òî â îáùåì ñëó÷àå íå äîêàçàíà âîçìîæíîñòü ïîñò-
ðîåíèÿ ïîëèíîìèàëüíîãî àëãîðèòìà äëÿ ïðîèçâîëüíîãî êëàññà ãðàôîâ, à
íàèëó÷øàÿ òåêóùàÿ îöåíêà ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðîâåðêè íà
èçîìîðôíîñòü âûðàæàåòñÿ ýêñïîíåíöèàëüíîé ôóíêöèåé.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 31
Ì. Á. Èëüÿøåíêî
32 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
200 400 600 800 1000
lg( )
1 10
100
10
1
0,1
0,01
1 10
t
�
�
3
�
à á
1 2
5
3
6
4
200 400 600 800 1000 N
lg( )
1 10
100
10
1
0,1
0,01
1 10
t
�
�
3
�
1
2
5
3
6 4
200 400 600 800 1000 1200
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
â ã
1
2
5
3
6
4
æ ç
200 400 600 800 1000 1200 N
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
1
2
5
3
64
200 400 600 800 1000
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
1
2
5
3
6
4
200 400 600 800 1000 1200 1400 N
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
12
5
3
64
ä å
200 400 600 800 1000
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
12
5
3
6
4
200 400 600 800 1000 N
1 10
100
10
1
0,1
0,01
1 10
�
�
3
�
1, 2
5
3
6
4
Ðèñ. 5. Ãðàôèêè ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ ïðîâåðêè íà èçîìîôíîñòü: à — ðåãó-
ëÿðíûå ãðàôû ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí (N = 20..1000, V = 3); á — íåðåãóëÿðíûå
ãðàôû ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí (N = 20..1000, V = 3, � = 0,1); â — ðåãóëÿðíûå 2D
ñåòè (N = 16..1024, � = 0); ã — íåðåãóëÿðíûå 2D ñåòè (N = 16..1024, � = 0,2); ä — ðåãóëÿðíûå
3D ñåòè (N = 27..1000, � = 0); e — ðåãóëÿðíûå 4D ñåòè (N = 16..1296, � = 0); æ — ñëó÷àéíî
ñãåíåðèðîâàííûå ãðàôû (N = 20..1000, � = 0,001); ç — ñëó÷àéíî ñãåíåðèðîâàííûå ãðàôû (N=
= 20..1000, � = 0,01)
Ïî ðåçóëüòàòàì èññëåäîâàíèé (òàáë. 2) â áîëüøèíñòâå ñëó÷àåâ íàèáî-
ëåå áûñòðûì áûë àëãîðèòì VF2, íà âòîðîì ìåñòå â çàâèñèìîñòè îò òèïîâ
ãðàôîâ ÷àùå âñåãî îêàçûâàëèñü àëãîðèòìû ISOMORPH è VF. Ê áåçóñëîâ-
íûì äîñòîèíñòâàì àëãîðèòìîâ VF2 è SD ìîæíî îòíåñòè òî, ÷òî îáà
ïîçâîëèëè ïîëó÷èòü ðåçóëüòàò, âíå çàâèñèìîñòè îò òèïà èññëåäóåìûõ
ãðàôîâ, â ïðåäåëàõ ëèìèòà âðåìåíè 200 ñ. Ýòîò ïîêàçàòåëü õàðàêòåðèçóåò
íàäåæíîñòü ðàáîòû ñèñòåì, ïîñòðîåííûõ íà îñíîâå óêàçàííûõ àëãîðèòìîâ,
íåñìîòðÿ íà òî ÷òî ïðîèçâîäèòåëüíîñòü àëãîðèòìà SD â ñðåäíåì ïîñòîÿííàÿ
è óñòóïàåò ïðîèçâîäèòåëüíîñòè àëãîðèòìà VF2 â 100—200 ðàç. Î÷åíü áëèçêè
ïî ïîêàçàòåëþ íàäåæíîñòè ðàáîòû àëãîðèòìû ISMORPH è VF, êîòîðûå íå
ïîëó÷èëè ðåçóëüòàòà â ïðåäåëàõ ëèìèòà âðåìåíè òîëüêî äëÿ îäíîãî òèïà
ãðàôîâ — íåðåãóëÿðíûõ ãðàôîâ ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí ñ ïàðà-
ìåòðàìè V = 3, � = 0,1.
Íàèìåíåå ïðîèçâîäèòåëüíûì îêàçàëñÿ àëãîðèòì ULL, êîòîðûé äëÿ
áîëüøèíñòâà òèïîâ ãðàôîâ áûë èñêëþ÷åí ïî ïðè÷èíå ïðåâûøåíèÿ îòâå-
äåííîãî ëèìèòà âðåìåíè íà îäíó ïðîâåðêó.
Àëãîðèòì ISOMORF íå ïîëó÷èë ðåçóëüòàòîâ äëÿ ðåãóëÿðíûõ ãðàôîâ,
íî äëÿ ñëó÷àéíûõ ãðàôîâ èìåë òåì áîëüøóþ ïðîèçâîäèòåëüíîñòü, ÷åì
ìåíüøå ðåãóëÿðíûõ ñòðóêòóð íàáëþäàëîñü â ãðàôàõ.
Àëãîðèòì VF2 â áîëüøèíñòâå ñëó÷àåâ áûë íàèáîëåå ïðîèçâîäèòåëü-
íûì, âñåãäà ïîëó÷àë ðåçóëüòàò â ïðåäåëàõ ëèìèòà âðåìåíè. Äëÿ áîëü-
øèíñòâà òèïîâ ãðàôîâ, ïðèíèìàâøèõ ó÷àñòèå â èññëåäîâàíèè, îí îêàçàëñÿ
íàèëó÷øèì ïî ïîêàçàòåëþ ïðîèçâîäèòåëüíîñòè. Ýòîò àëãîðèòì ïðîÿâèë
ñåáÿ ëó÷øå àëãîðèòìîâ VF è ISOMORPH äëÿ ãðàôîâ ñ ðåãóëÿðíûìè
ñòðóêòóðàìè, íî óñòóïèë àëãîðèòìó ISOMORPH äëÿ ñëó÷àéíî ñãåíåðè-
ðîâàííûõ ãðàôîâ ñ ïîâûøåíèåì ïëîòíîñòè ðåáåðíîãî çàïîëíåíèÿ.
Àëãîðèòì VF âî ìíîãèõ ñëó÷àÿõ (ðåãóëÿðíûå è íåðåãóëÿðíûå ñåòè)
ïîêàçàë âòîðîé ðåçóëüòàò ïî ïðîèçâîäèòåëüíîñòè.  ñëó÷àå ðåãóëÿðíûõ è
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 33
Õàðàêòåðèñòèêà VF VF2 SD ULL ISOMORF ISOMORPH
Âñåãäà ïîëó÷åí ðåçóëüòàò â ïðåäåëàõ
ëèìèòà âðåìåíè (200ñ) – + + – – –
Íà íåêîòîðûõ êëàññàõ ãðàôîâ ïîêàçàë
ïðîèçâîäèòåëüíîñòü
íàèáîëüøóþ � + – – – +
íàèìåíüøóþ – – + + + –
Íàáëþäàëèñü ñêà÷êè (ïèêè) íà íåêî-
òîðûõ êëàññàõ ãðàôîâ + – – + + –
Òàáëèöà 2. Ðåçóëüòàòû àíàëèçà ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ
ïðîâåðêè íà èçîìîðôíîñòü
íåðåãóëÿðíûõ ãðàôîâ ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí óñòóïàë àëãîðèò-
ìó ISOMORPH ïðè ìàëîì ÷èñëå âåðøèí.
Îñíîâíîå äîñòîèíñòâî àëãîðèòìà SD — ïîñòîÿíñòâî âðåìåíè âû÷èñ-
ëåíèé è ñòàáèëüíîñòü ðàáîòû. Âðåìÿ ðàáîòû ïðàêòè÷åñêè íå èçìåíÿëîñü â
çàâèñèìîñòè îò òèïà èññëåäóåìûõ ãðàôîâ, îñòàâàÿñü íà óðîâíå 170—190 ñ
äëÿ ãðàôîâ ñ íàèáîëüøèì ÷èñëîì âåðøèí. Äëÿ ãðàôîâ ñ îãðàíè÷åííîé
ñòåïåíüþ âåðøèí ïðè âîçðàñòàíèè ñòåïåíè âåðøèí ýòîò àëãîðèòì ñòàíî-
âèëñÿ íàèìåíåå ïðîèçâîäèòåëüíûì.Îí ïîêàçàë íàèõóäøèé ðåçóëüòàò è
äëÿ âñåõ ñëó÷àéíî ñãåíåðèðîâàííûõ ãðàôîâ, à òàêæå ïðè ìàëîì ÷èñëå
âåðøèí â ðåãóëÿðíûõ è íåðåãóëÿðíûõ ñåòÿõ. Îí ðàáîòàë ñòàáèëüíî, íà-
äåæíî, íî ìåäëåííî.
Àëãîðèòì ULL — äîñòàòî÷íî ìåäëåííûé. Âî ìíîãèõ ñëó÷àÿõ îí íå
ïîëó÷èë ðåçóëüòàòà â ïðåäåëàõ ëèìèòà âðåìåíè (âñå ñëó÷àè ðåãóëÿðíûõ
ãðàôîâ è âñå ñëó÷àè ñåòåé, êàê ðåãóëÿðíûõ, òàê è íåðåãóëÿðíûõ), ðàáîòàÿ
ñòàáèëüíî òîëüêî íà ñëó÷àéíûõ ãðàôàõ, ïîêàçàâ ïðè ýòîì âòîðîé íàèõóä-
øèé ïî ïðîèçâîäèòåëüíîñòè ðåçóëüòàò.
Àëãîðèòì ISOMORPH â áîëüøèíñòâå ñëó÷àåâ îêàçûâàëñÿ íà òðåòüåì
ìåñòå, õîòÿ íà íåêîòîðûõ òèïàõ ãðàôîâ (ðåãóëÿðíûå 2D ñåòè è ñëó÷àéíûå
ãðàôû) ïîêàçàë íàèëó÷øèå ðåçóëüòàòû. Äëÿ ñëó÷àéíûõ ãðàôîâ ïðè óâåëè-
÷åíèè ïëîòíîñòè ðåáåðíîãî çàïîëíåíèÿ îí îïåðåæàë âñåõ êîíêóðåíòîâ.
Êðîìå òîãî, âî âñåõ ñëó÷àÿõ, êðîìå îäíîãî, àëãîðèòì âûäàë ðåçóëüòàò â
ïðåäåëàõ ëèìèòà âðåìåíè.
Àëãîðèòì ISOMORF ñòàáèëüíî çàíèìàë ÷åòâåðòîå ìåñòî äëÿ ñåðèè
ñëó÷àéíûõ ãðàôîâ.  îñòàëüíûõ ñëó÷àÿõ ðàáîòàë òåì áûñòðåå, ÷åì ìåíüøå
ðåãóëÿðíûõ ýëåìåíòîâ ñîäåðæàëè ãðàôû. Äëÿ áîëüøèíñòâà ðåãóëÿðíûõ
ãðàôîâ íå ïîëó÷èë ðåçóëüòàòîâ â ïðåäåëàõ ëèìèòà âðåìåíè (êðîìå ãðàôîâ
ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí è ïàðàìåòðîì V=9).
Òàêèì îáðàçîì, àëãîðèòìû ISOMORPH è VF2 îêàçàëèñü íàèáîëåå ïðîèç-
âîäèòåëüíûìè, â áîëüøèíñòâå ñëó÷àåâ ïîêàçàâ ïðàêòè÷åñêè ðàâíîöåííûå
ðåçóëüòàòû. Àëãîðèòì VF2 ëó÷øå èñïîëüçîâàòü äëÿ ãðàôîâ, ñîäåðæàùèõ
ðåãóëÿðíûå ñòðóêòóðû. Àëãîðèòì ISOMORPH ñëåäóåò èñïîëüçîâàòü äëÿ
êëàññà ãðàôîâ, áëèçêèõ ïî ñâîèì õàðàêòåðèñòèêàì ê ñëó÷àéíûì, õîòÿ äëÿ
ðåãóëÿðíûõ ãðàôîâ ýòîò àëãîðèòì òàêæå ïîêàçûâàåò õîðîøèå ðåçóëüòàòû.
Àëãîðèòì óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà. Ïîñòàíîâêà
çàäà÷è. Ïóñòü äàíû ãðàôû G V E
1 1 1
� ( , ) è G V E
2 2 2
� ( , ). Ãðàô G
1
èçîìîðôåí
ïîäãðàôó ãðàôà G
2
(G S G
1 2 2
� � ), åñëè ñóùåñòâóåò ïîäñòàíîâêà � :V V
2 1
�
òàêàÿ, ÷òî äëÿ êàæäîé ïàðû âåðøèí v v Vi j, �
2
; åñëè ( , )v v Ei j �
2
, òî
( ( ), ( ))� �v v Ei j �
1
.
Àëãîðèòì óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà ÿâëÿåòñÿ ðàçâè-
òèåì è ïðîäîëæåíèåì àëãîðèòìà óñòàíîâëåíèÿ èçîìîðôíîñòè [21]. Îí
Ì. Á. Èëüÿøåíêî
34 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
îñíîâàí íà ìåòîäå âåòâåé è ãðàíèö, à òàêæå íà îñíîâíûõ ïðèíöèïàõ, ðàçðà-
áîòàííûõ äëÿ àëãîðèòìà óñòàíîâëåíèÿ èçîìîðôíîñòè.
Ïðåäâàðèòåëüíàÿ ÷àñòü àëãîðèòìà. Îñíîâó ïðåäâàðèòåëüíîé ÷àñòè
àëãîðèòìà ñîñòàâëÿåò ìàòðèöà âîçìîæíûõ ñîâìåùåíèé M i j,
êîòîðàÿ
ïðåäñòàâëÿåò ñîáîé áèíàðíóþ òàáëèöó ðàçìåðîì V V
1 2
� . Êàæäîìó ýëå-
ìåíòó òàáëèöû ñîîòâåòñòâóåò ïàðà âåðøèí èñõîäíûõ ãðàôîâ V i1,
è V j2,
.
Çíà÷åíèÿ ìàòðèöû ôîðìèðóþòñÿ òàê: M i j,
�0, åñëè íà îñíîâàíèè ïðåä-
âàðèòåëüíûõ ïðîâåðîê âåðøèíû V i1,
è V j2,
ñîâìåñòèòü íåëüçÿ; M i j,
�1 â
ïðîòèâíîì ñëó÷àå.
Îñíîâíûå ðàçëè÷èÿ ïðè çàïîëíåíèè ìàòðèöû âîçìîæíûõ ñîâìåùåíèé
ÿâëÿþòñÿ ïðÿìûì ñëåäñòâèåì èçìåíåíèé â ïîñòàíîâêå çàäà÷è. Èõ ëåãêî
ïðîäåìîíñòðèðîâàòü íà ïðèìåðå ïðîñòåéøèõ ïðîâåðîê, ïðèìåíÿåìûõ ïðè
åå ôîðìèðîâàíèè. Äàëåå ïðåäïîëàãàåì, ÷òî ãðàô G
1
ÿâëÿåòñÿ áîëüøèì, à
ãðàô G
2
ìåíüøèì è âåðøèíû åãî íàêëàäûâàþòñÿ íà âåðøèíû ãðàôà G
1
.
Î÷åâèäíî, ÷òî âåðøèíû ãðàôîâ ìîãóò áûòü ñîâìåùåíû òîëüêî â ñëó-
÷àå, åñëè ñòåïåíè ñîîòâåòñòâóþùèõ âåðøèí ãðàôà G
1
íå ìåíüøå, ÷åì
ñòåïåíè íàêëàäûâàåìûõ âåðøèí ãðàôà G
2
. Ýòî óñëîâèå çàïèøåì â ñëå-
äóþùåì âèäå:
M i j,
� 0, åñëè V Vi j1 2, ,
� , i V�1
1
.. , j V�1
2
.. .
Ê ïðîñòåéøèì ïðîâåðêàì äëÿ îðèåíòèðîâàííûõ ãðàôîâ ìîæíî îòíåñòè
òàêæå ñðàâíåíèå ÷èñëà âõîäÿùèé è èñõîäÿùèõ äóã:
M i j,
� 0, åñëè V Vi j1 2, ,
èñ èñ
� , i V�1
1
..
èñ
, j V�1
2
..
èñ
;
M i j,
� 0, åñëè V Vi j1 2, ,
âõ âõ
� , i V�1
1
..
âõ
, j V�1
2
..
âõ
;
Íåñêîëüêî èíà÷å âûãëÿäèò ïðèìåíåíèå èíâàðèàíòîâ ïðè ôîðìèðî-
âàíèè ìàòðèöû âîçìîæíûõ ñîâìåùåíèé. Êðîìå çàìåíû óñëîâèÿ ðàâåíñòâà
óñëîâèåì íåðàâåíñòâà, íåêîòîðûå èíâàðèàíòû ìîæíî ïðèìåíÿòü èñêëþ-
÷èòåëüíî ê ïîäãðàôàì îêðóæåíèÿ âåðøèí, â îòëè÷èå îò àëãîðèòìà óñòà-
íîâëåíèÿ èçîìîðôíîñòè, ãäå òàêèå èíâàðèàíòû êàê Zero2 ìîæíî èñïîëü-
çîâàòü «íàïðÿìóþ», ñðàâíèâàÿ ñòðîêè, ñîîòâåòñòâóþùèå ïîòåíöèàëüíî
ñîâìåùàåìûì âåðøèíàì.
Ïðîãðàììíàÿ ðåàëèçàöèÿ âêëþ÷àåò ñëåäóþùèå ïðåäâàðèòåëüíûå
ïðîâåðêè:
1. M i j,
� 0, åñëè V Vi j1 2, ,
� , ãäå V X Y, — ñòåïåíü âåðøèíû Y ãðàôà X.
2. M i j,
� 0, åñëè V Vi j1 2, ,
âõ âõ
� , ãäå V X Y,
âõ
— ÷èñëî âõîäÿùèõ ðåáåð
âåðøèíû Y ãðàôà X.
3. M i j,
� 0, åñëè V Vi j1 2, ,
èñ èñ
� , ãäå V X Y,
èñ
— ÷èñëî èñõîäÿùèõ ðåáåð
âåðøèíû Y ãðàôà X.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 35
4. M i j,
� 0, åñëè W Wi j1 2, ,
â â
� , ãäå WX Y,
â
— ÷èñëî âåðøèí â âîëíîâîì
ðàçëîæåíèè ïîäãðàôà îêðóæåíèÿ âåðøèíû Y ãðàôà X.
5. M i j,
� 0, åñëè W Wi l
l
k
j l
l
k
1
1
2
1
, , , ,
â â
� �
� , k W j�1
2
..
,
â
, l �1 4.. , ãäå WX Y l, ,
â
—
÷èñëî âåðøèí â ïåðâîé âîëíå âîëíîâîãî ðàçëîæåíèÿ ãðàôà X, íà÷èíàÿ ñ
âåðøèíû Y.
6. M i j,
� 0, åñëè W Wi j1 2, ,
p p
� , ãäå WX Y,
p
— ÷èñëî ðåáåð â âîëíîâîì ðàç-
ëîæåíèè ïîäãðàôà îêðóæåíèÿ âåðøèíû Y ãðàôà X.
7. M i j,
� 0, åñëè W Wi l
l
k
j l
l
k
1
1
2
1
, , , ,
p p
� �
� , k W j�1
2
..
,
p
, l �1 4.. , ãäå WX Y l, ,
p
—
÷èñëî ðåáåð â ïåðâîé âîëíå âîëíîâîãî ðàçëîæåíèÿ ãðàôà X, íà÷èíàÿ ñ
âåðøèíû Y.
Êàê è â àëãîðèòìå óñòàíîâëåíèÿ èçîìîðôíîñòè ïðîâîäèòñÿ ñîðòèðîâ-
êà âåðøèí ãðàôîâ. Ïîñêîëüêó äàííàÿ ÷àñòü àëãîðèòìà ïîëíîñòüþ ñîâïà-
äàåò ñ ñîîòâåòñòâóþùåé ÷àñòüþ àëãîðèòìà óñòàíîâëåíèÿ èçîìîðôíîñòè, ñ
òîé ëèøü ðàçíèöåé, ÷òî ãðàôû ìîãóò èìåòü â îáùåì ñëó÷àå ðàçëè÷íîå
÷èñëî âåðøèí, à ìàòðèöà âîçìîæíûõ ñîâìåùåíèé ìîæåò áûòü ñîîòâåòñò-
âåííî ïðÿìîóãîëüíîé, à íå êâàäðàòíîé, äåòàëüíîå îïèñàíèå àëãîðèòìà
ñîðòèðîâêè íå ïðèâîäèòñÿ.
Îñíîâíàÿ ÷àñòü àëãîðèòìà ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîå
íàëîæåíèå âåðøèí ñ âîçâðàòîì, îïèñûâàòü êîòîðîå óäîáíî â òåðìèíàõ
ìåòîäà ïîèñêà â ïðîñòðàíñòâå ñîñòîÿíèé.
Âåðøèíû ãðàôà G
2
îñòàþòñÿ íåòðîíóòûìè è êàæäîé èç íèõ ñòàâèòñÿ â
ñîîòâåòñòâèå îäíà èç âåðøèí ãðàôà G
1
. Ïðè ýòîì ïðîâåðÿåòñÿ äîïóñòè-
ìîñòü òàêîãî ñîâìåùåíèÿ. Åñëè óäàåòñÿ íàéòè ñîîòâåòñòâèå âñåì âåðøè-
íàì ãðàôàG
2
è âûïîëíåíî óñëîâèå ãðàô-ïîäãðàô èçîìîðôèçìà, òî íàéäåí-
íîå ñîñòîÿíèå âîçâðàùàåòñÿ êàê èñêîìàÿ ïîäñòàíîâêà.
ÏóñòüT i1,
— ÷èñëî ñâÿçåé âåðøèíû i ãðàôàG
1
ñ âåðøèíàìèV sj1 1,
( )�� , à
T i2,
— ÷èñëî ñâÿçåé âåðøèíû i ãðàôà G
2
ñ âåðøèíàìèV sj2 2,
( )�� . Íà÷àëü-
íîìó ñîñòîÿíèþ � ( )s
0
0� ñîîòâåòñòâóåò ñîñòîÿíèå, ïðè êîòîðîì åùå íå
ñîâìåùåíî íè îäíîé ïàðû âåðøèí. Äëÿ ïîëó÷åíèÿ i-ãî ñîñòîÿíèÿ äëÿ
âåðøèíûV i2,
íàõîäèì ñîîòâåòñòâèå ñðåäè âåðøèí V j1,
, òàêèõ ÷òî
1) M i j,
� 1, ò. å. âåðøèíû ñîâìåñòèìû íà îñíîâàíèè ïðåäâàðèòåëüíûõ
ïðîâåðîê;
2) T i1,
� T j2,
;
3) äëÿ k i�1.. , åñëè ( , )v v Ei k �
1
, òî ( ( ), ( ))� �v v Ei k �
2
.
Åñëè âûïîëíåíû ýòè òðè óñëîâèÿ, èç êîòîðûõ òðåòüå ÿâëÿåòñÿ ïðÿìûì
ñëåäñòâèåì îïðåäåëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà, òî ñîîòâåòñòâóþùàÿ
Ì. Á. Èëüÿøåíêî
36 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
ïàðà âåðøèí âõîäèò â ÷àñòè÷íóþ ïîäñòàíîâêó è ôîðìèðóåòñÿ íîâîå ñîñ-
òîÿíèå � ( )s i . Ïåðåáîð ñîñòîÿíèé ïðîâîäèòñÿ ìåòîäîì ïîèñêà â ãëóáèíó.
Áàçà ãðàôîâ è àíàëèç ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ óñòàíîâëå-
íèÿ ãðàô-ïîäãðàô èçîìîðôèçìà. Äëÿ ñðàâíåíèÿ ïðîèçâîäèòåëüíîñòè
àëãîðèòìîâ óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà, áûëà èñïîëüçîâàíà
ïðåäëîæåííàÿ â [20], ýòàëîííàÿ áàçà ãðàôîâ (òàáë. 3).
Íàáîðû ãðàôîâ äëÿ ðàçëè÷íûõ ðàçìåðîâ ïîäãðàôîâ (20, 40 è 60 % îò
áîëüøåãî ãðàôà) îäèíàêîâû. Äëÿ íàáîðà, ïðèâåäåííîãî â òàáë. 3, îáùåå
÷èñëî ïàð äëÿ ñðàâíåíèÿ ñîñòàâèëî 54600.
Äëÿ ñðàâíåíèÿ áûëè èñïîëüçîâàíû àëãîðèòìû: VF è VF2, ULL,
SGISOMORPH. Àëãîðèòìû SD è ISOMORF íå èñïîëüçîâàíû, òàê êàê íå èç-
âåñòíû èõ ìîäèôèêàöèè äëÿ çàäà÷è óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçî-
ìîðôèçìà.
 ðåçóëüòàòå ñðàâíåíèÿ ïîëó÷åíû äàííûå î õàðàêòåðå ïîâåäåíèÿ ïðî-
èçâîäèòåëüíîñòè âñåõ àëãîðèòìîâ íà áîëåå ÷åì 45 íàáîðàõ ãðàôîâ. Ïî-
ñêîëüêó ïðèâåñòè ðåçóëüòàòû òàêîãî äåòàëüíîãî àíàëèçà àëãîðèòìîâ íå
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 37
Òèï ãðàôîâ ×èñëî ïàð Ïàðàìåòðû
Ðàçìåð ãðàôà
(÷èñëî âåðøèí)
Ñëó÷àéíî ñãåíåðèðîâàííûå ãðàôû 1000 � = 0,01 20—1000
1000 � = 0,005 20—1000
1000 � = 0,001 20—1000
Ðåãóëÿðíûå ñåòè 1000 2D ñåòü 16—1024
800 3D ñåòü 27—1000
500 4D ñåòü 16—1296
Íåðåãóëÿðíûå ñåòè 3000 2D ñåòè
� ={0,2; 0,4; 0,6}
16—1024
2400 3D ñåòè
� ={0,2; 0,4; 0,6}
27—1000
1500 4D ñåòè
� ={0,2; 0,4; 0,6}
16—1296
Ðåãóëÿðíûå ãðàôû ñ îãðàíè÷åííîé
ñòåïåíüþ âåðøèí
1000 V = 3 20—1000
1000 V = 6 20—1000
1000 V = 9 20—1000
Íåðåãóëÿðíûå ãðàôû ñ îãðàíè÷åí-
íîé ñòåïåíüþ âåðøèí
1000 V = 3, � = 0,1 20—1000
1000 V = 6, � = 0,1 20—1000
1000 V = 9, � = 0,1 20—1000
 ñ å ã î 18200
Òàáëèöà 3. Ñîñòàâ ýòàëîííîé áàçû ãðàôîâ
ïðåäñòàâëÿåòñÿ âîçìîæíûì, ïðèâåäåì õàðàêòåðíûå ðåçóëüòàòû äëÿ êàæ-
äîãî êëàññà ãðàôîâ ýòàëîííîé áàçû.
Êàê âèäíî èç ðèñ. 6 è òàáë. 4, àëãîðèòì VF2 ïîêàçàë ñòàáèëüíî âûñîêóþ
ïðîèçâîäèòåëüíîñòü äëÿ áîëüøèíñòâà íàáîðîâ ãðàôîâ, êðîìå ñëó÷àéíûõ è
íåêîòîðûõ íåðåãóëÿðíûõ ãðàôîâ ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí. Ê äî-
ñòîèíñòâàì àëãîðèòìà ìîæíî îòíåñòè è ñòàáèëüíîñòü ðàáîòû, ïîñêîëüêó äëÿ
âñåõ òåñòîâûõ íàáîðîâ áûë ïîëó÷åí ðåçóëüòàò â ïðåäåëàõ ëèìèòà âðåìåíè.
Àëãîðèòì VF äëÿ ðåãóëÿðíûõ è íåðåãóëÿðíûõ ñåòåé ÷àñòî ïîêàçûâàë
âòîðîé ïî ïðîèçâîäèòåëüíîñòè ðåçóëüòàò, íî ïëîõî ðàáîòàë ñî ñëó÷àéíûìè
ãðàôàìè, ÷àñòî ïðåâûøàÿ ëèìèò âðåìåíè ïðè ñðàâíåíèè ïàðû ãðàôîâ. Â
Ì. Á. Èëüÿøåíêî
38 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
0 50 100 150 200 250 300 350 400 N
lg( )
1 10
100
10
1
0,1
0,01
1 10
1 10
1 10
t
�
�
�
�
3
�
��
��
à
1
2
3
4
0 50 100 150 200 250 300 350 400 N
1
0,1
0,01
1 10
1 10
1 10
�
�
�
�
��
��
â
1
2
3
4
0 50 100 150 200 250 300 350 400 N
lg( )
100
10
1
0,1
0,01
1 10
1 10
1 10
t
�
�
�
�
��
��
á
1
2
3
4
0 50 100 150 200 250 300 350 400 N
ã
1
2
3
4
lg( )
1
0,1
0,01
1 10
1 10
1 10
t
�
�
�
�
��
��
0 50 100 150 200 250 300 350 400 N
1 10
100
10
1
0,1
0,01
1 10
1 10
1 10
�
�
�
�
3
�
��
��
ä
1 3 2
4
lg( )t
lg( )t
Ðèñ 6. Ãðàôèêè ïðîèçâîäèòåëüíîñòè àëãî-
ðèòìîâ óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîð-
ôèçìà: à — ðåãóëÿðíûå 2D ñåòè; á — íå-
ðåãóëÿðíûå 2D ñåòè; â è ã — ñîîòâåòñòâåííî
ðåãóëÿðíûå è íåðåãóëÿðíûå ãðàôû ñ îãðàíè-
÷åííîé ñòåïåíüþ âåðøèí; ä — ñëó÷àéíî ñãå-
íåðèðîâàííûå ãðàôû; 1 — VF; 2 — VF2; 3 —
ULL; 4 — ISOMORPH
ðàáîòå àëãîðèòìà ÷àñòî íàáëþäàëèñü ñêà÷êè ïðîèçâîäèòåëüíîñòè. Îäíàêî â
íåêîòîðûõ ñëó÷àÿõ àëãîðèòì VF ïîêàçàë íàèáîëüøóþ ïðîèçâîäèòåëüíîñòü
íà ãðàôàõ ñ ìàêñèìàëüíûì ÷èñëîì âåðøèí â íàáîðå, õîòÿ äëÿ ìåíüøåãî ÷èñëà
âåðøèí óñòóïàë â ïðîèçâîäèòåëüíîñòè àëãîðèòìàì VF2 è SGISOMORPH
(íåêîòîðûå ñëó÷àè íåðåãóëÿðíûõ ãðàôîâ ñ îãðàíè÷åííîé ñòåïåíüþ âåðøèí).
Àëãîðèòì ULL â áîëüøèíñòâå ñëó÷àåâ ïîêàçûâàë íàèõóäøèå ðåçóëü-
òàòû, õîòÿ äëÿ âñåõ íàáîðîâ, êðîìå ñëó÷àéíûõ ãðàôîâ, ðåçóëüòàò âû÷èñ-
ëåíèé áûë ïîëó÷åí â ïðåäåëàõ óñòàíîâëåííîãî ëèìèòà âðåìåíè. Ñðåäè
èññëåäóåìûõ àëãîðèòìîâ ULL èìåë íàèìåíüøåå ïëàâíîå è ïðåäñêàçóåìîå
èçìåíåíèå âðåìåíè âû÷èñëåíèé è ìèíèìàëüíîå ÷èñëî ïèêîâ. Ïîýòîìó,
ÿâëÿÿñü ñàìûì ìåäëåííûì, îí îêàçàëñÿ íàèáîëåå ïðåäñêàçóåìûì ïî ñâîèì
õàðàêòåðèñòèêàì.
Àëãîðèòì SGISOMORPH ïî ðåçóëüòàòàì èññëåäîâàíèé ïîêàçàë íàè-
áîëüøóþ ïðîèçâîäèòåëüíîñòü äëÿ ãðàôîâ, íå îáëàäàþùèõ ñïåöèàëüíûìè
ñâîéñòâàìè è íåðåãóëÿðíûõ 2D ñåòåé. Íà íàáîðàõ ñïåöèàëüíûõ ãðàôîâ àëãî-
ðèòì SGISOMORPH èìåë ïðîèçâîäèòåëüíîñòü ëèáî íàèáîëüøóþ, ëèáî ñðàâ-
íèìóþ ñ íàèáîëåå áûñòðûì èç àíàëîãîâ. Ïîñêîëüêó èñïîëüçîâàííûé äëÿ
ñðàâíåíèÿ àëãîðèòì VF2 ÿâëÿåòñÿ íàèáîëåå áûñòðûì èç òî÷íûõ ïåðåáîðíûõ
àëãîðèòìîâ óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà äëÿ ãðàôîâ îáùåãî
âèäà, äëÿ íåðåãóëÿðíûõ 2D ñåòåé, à òàêæå ãðàôîâ, íå îáëàäàþùèõ ñïåöèàëü-
íûìè ñâîéñòâàìè, àëãîðèòì SGISOMORPH íàèáîëåå áûñòðûé ñðåäè òî÷íûõ
ïåðåáîðíûõ àëãîðèòìîâ.
Âûâîäû. Ðàçðàáîòàííûå íîâûå àëãîðèòìû ïðîâåðêè ãðàôîâ íà èçî-
ìîðôíîñòü è óñòàíîâëåíèÿ ãðàô-ïîäãðàô èçîìîðôèçìà, îñíîâàíû íà
èñïîëüçîâàíèè ìàòðèöû âîçìîæíûõ ñîâìåùåíèé è áîëåå ñòðîãîãî îãðà-
íè÷èâàþùåãî óñëîâèÿ ïåðåáîðíîé ÷àñòè. Âïåðâûå ïðåäëîæåí ïîäõîä ê
ôîðìèðîâàíèþ äîïîëíèòåëüíûõ ïðîâåðîê äëÿ ìàòðèöû âîçìîæíûõ ñîâ-
ìåùåíèé, îñíîâàííûé íà âîëíîâîì ðàçëîæåíèè ãðàôîâ è ïðèìåíåíèè
èíâàðèàíòîâ äëÿ ïîäãðàôîâ îêðóæåíèÿ âåðøèí.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 39
Õàðàêòåðèñòèêà VF VF2 ULL SGISOMORPH
Âñåãäà ïîëó÷åí ðåçóëüòàò â ïðåäåëàõ
ëèìèòà âðåìåíè (200ñ) – + – +
Ïîêàçàë íàèáîëüøóþ ïðîèçâîäèòåëü-
íîñòü íà íåêîòîðûõ êëàññàõ ãðàôîâ + + – +
Ïîêàçàë íàèìåíüøóþ ïðîèçâîäèòåëü-
íîñòü íà íåêîòîðûõ êëàññàõ ãðàôîâ + – + –
Íàáëþäàëèñü ñêà÷êè (ïèêè) íà íåêîòî-
ðûõ êëàññàõ ãðàôîâ + + + +
Òàáëèöà 4. Ðåçóëüòàòû àíàëèçà ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ
Ðåçóëüòàòû ñðàâíåíèÿ àëãîðèòìîâ íà ãðàôàõ ýòàëîííîé áàçû äëÿ îöåí-
êè ïðîèçâîäèòåëüíîñòè àëãîðèòìîâ óñòàíîâëåíèÿ èçîìîðôíîñòè è ïðî-
âåðêè ãðàô-ïîäãðàô èçîìîðôèçìà ñ àíàëîãàìè ïîêàçàëè, ÷òî íàèáîëåå
áûñòðûìè ñðåäè òî÷íûõ ïåðåáîðíûõ àëãîðèòìîâ äëÿ ãðàôîâ áåç ñïåöèàëü-
íûõ õàðàêòåðèñòèê è íåðåãóëÿðíûõ 2D ñåòåé ÿâëÿþòñÿ àëãîðèòìû, ïðåäëî-
æåííûå àâòîðîì. Äàëüíåéøèå óñèëèÿ áóäóò íàïðàâëåíû íà ðàçðàáîòêó
íîâûõ îãðàíè÷èâàþùèõ óñëîâèé, êàê äëÿ ìàòðèöû âîçìîæíûõ ñîâìå-
ùåíèé, òàê è äëÿ ïåðåáîðíîé ÷àñòè àëãîðèòìà, ôîðìèðîâàíèå êðèòåðèÿ
ýôôåêòèâíîñòè ñîâìåñòíîãî èñïîëüçîâàíèÿ èíâàðèàíòîâ, ïîñòðîåíèå íà
îñíîâå ïðåäñòàâëåííûõ àëãîðèòìîâ àëãîðèòìà íàõîæäåíèÿ íàèáîëüøåãî
îáùåãî ïîäãðàôà.
Ïðåäëîæåííûå àëãîðèòìû è èõ ìîäèôèêàöèè äëÿ ñðàâíåíèÿ âçâå-
øåííûõ ãðàôîâ èñïîëüçóþòñÿ ïðè ïîñòðîåíèè ñèñòåì óïðàâëåíèÿ ðåçåð-
âèðîâàíèåì ðàñïðåäåëåííûõ ðåñóðñîâ â êîìïüþòåðíûõ ñåòÿõ, äëÿ îïòè-
ìèçàöèè àïïàðàòíûõ çàòðàò íà ýòàïå ïðîåêòèðîâàíèè êîíå÷íûõ àâòîìàòîâ
ñ ïðîãðàììèðóåìîé ïðîöåäóðîé.
Algorithms are presented for isomorphism and graph-subgraph isomorphism determination.
They are based on the use of possible coincidence matrix and invariants application to subgraphs
for vertexes surrounding. Comparative analysis results are offered for speed of algorithms
executing. High performance of algorithms developed is shown for those graphs class which are
not possessed special properties.
1. Bunke H., Dickinson P., Kraetzl M. Matching Sequences of Graphs with Applications in Com-
puter Network Analysis https://iamwww.unibe.ch/~fki/publications/public/BuDiKr04-001.pdf.
2. Bunke H. Graph matching: Theoretical foundations, algorithms, and applications// Proc. Vi-
sion Interface 2000. — Montreal, 2000. — Ð. 82 — 88
3. Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-com-
pleteness. — W. H. Freeman, 1979. — 251 p.
4. Messmer T. Efficient Graph Matching Algorithms for Preprocessed Model Graphs. Ph.D.
Thesis. Inst. of Comp. Sci. and Applied Mathematics. — University of Bern, 1996. — 272 p.
5. Messmer, B. T., Bunke H. Subgraph Isomorphism in Polynomial Time. http://www.iam.
unibe.ch/publikationen/techreports/1995/iam-95-003.
6. Chao-Wen Kevin Chen, Yun D. Y. Y. Unifying Graph Matching Problems with a Practical
Solution. http://citeseer.ist.psu.edu/chen98unifying.html.
7. Luks E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time// J.
Comput. Syst. Sci. — 1982. — Ð. 42—65.
8. Messmer, B. T., Bunke H. A decision tree approach to graph and subgraph isomorphism de-
tection.// Pattern Recogn. — 1999. — 32. — Ð. 1979—1998.
9. Ullmann J.R. An Algorithm for Subgraph Isomorphism // Journal of the Association for
Computing Machinery. — 1976. — ¹ 23. — P. 31—42.
10. Cordella L. P., Foggia P., Sansone C., Vento M. Performance evaluation of the VF graph
matching algorithm // Proc. of the 10th ICIAP. IEEE Computer SocietyPress. — 1999. —
Ð. 1172—1177.
Ì. Á. Èëüÿøåíêî
40 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
11. Cordella L. P., Foggia P., Sansone C., Vento M. An improved algorithm for matching large
graphs//Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representa-
tions. — Italy. — 2001. — Ð. 149—159.
12. Mehlhorn K., Naher S. LEDA: À platform for combinatorial and geometric computing //
Comm. of the ACM 38. — 1995. —N 1. — P.96—102.
13. Singler J. Graph Isomorphism Implementation in LEDA 5.1 http://www.algorithmic-solu-
tions.com/bilder/graph_iso.pdf .
14. Foggia P., Sansone C., Vento M. A performance comparison of five algorithms for graph
isomorphism// Proc. of the 3rd IAPR-TC15 Workshop on Graph based Representation
(GbR2001). — Italy, 2001. — P.188—189.
15. Schmidt D.C., Druffel L.E. A Fast Backtracking Algorithm to Test Directed Graphs for
Isomorphism Using Distance Matrices//J. of the Association for Computing Machinery. —
1976. — 23.— Ð. 433—445.
16. Ïèí÷óê Â. Ï. Ìåòîäû è àëãîðèòìû ñòðóêòóðíîé èäåíòèôèêàöèè //Èñêóññòâåííûé
èíòåëëåêò-2002: Ìàòåðèàëû ìåæäóíàð. íàó÷.-òåõíè÷åñêîé êîíô. Òîì 2.— Òàãàíðîã,
2002. — Ñ. 221—225.
17. Ïèí÷óê Â.Ï. Ðîñïîçíà÷àíèå èçîìîðôíîñòè ãðàôîâ: ÏÍÂ-àëãîðèòì //Ñêëàäí³ ñèñòåìè ³
ïðîöåñè. — 2002. — ¹ 1. — Ñ. 4—11.
18. Èëüÿøåíêî Ì. Á. Ïðîáëåìíî-îðèåíòèðîâàííàÿ áèáëèîòåêà è èíòåãðèðîâàííàÿ ñðåäà
äëÿ ðåøåíèÿ çàäà÷ íà ãðàôàõ// Òåç. 9-ãî Ìåæäóíàðîäíîãî ìîëîäåæíîãî ôîðóìà
«Ðàä³îåëåêòðîí³êà òà ìîëîäü ó ÕÕ² ñò.» Ñá. ìàòåðèàëîâ. — Õàðüêîâ : ÕÍÓÐÅ, 2005.—
Ñ.482—487.
19. Ïèí÷óê Â. Ï. Îñíîâàííàÿ íà âîëíîâîì ðàçëîæåíèè ñèñòåìà èíâàðèàíòîâ äëÿ ïðîñòûõ
ãðàôîâ è àëãîðèòì ðàñïîçíàâàíèÿ èçîìîðôíîñòè. — Êèåâ, 1995. — 30 ñ. Äåï. â ÃÍÒÁ
Óêðàèíû 10.05.95, ¹ 1002 — Óê95.
20. Foggia P., Sansone C., Vento M. A Database of Graphs for Isomorphism and Sub-Graph
Isomorphism Benchmarking http://amalfi.dis.unina.it/graph/db/papers/database.pdf.
21. Èëüÿøåíêî Ì. Á. Ðàçðàáîòêà è èññëåäîâàíèå ïàðàëëåëüíîãî àëãîðèòìà ïðîâåðêè
ãðàô-ïîäãðàô èçîìîðôèçìà //Ðàäèîýëåêòðîíèêà. Èíôîðìàòèêà. Óïðàâëåíèå. — 2006. —
¹ 1. — Ñ. 63—69.
Ïîñòóïèëà 28.12.06
ÈËÜßØÅÍÊÎ Ìàòâåé Áîðèñîâè÷, àñïèðàíò Çàïîðîæñêîãî Íàöèîíàëüíîãî òåõíè÷åñêîãî
óíèâåðñèòåòà, êîòîðûé îêîí÷èë â 2005 ãîäó. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — òðóäíî-
âû÷èñëèìûå àëãîðèòìû íà ãðàôàõ; ïàðàëëåëüíîå è ðàñïðåäåëåííîå ïðîãðàììèðîâàíèå â ðàçíî-
ðîäíûõ ñåòÿõ; ðàñïðåäåëåíèå íàãðóçêè è ðåçåðâèðîâàíèå ñèñòåìíûõ ðåñóðñîâ â ðàçíîðîäíûõ
êîìïüþòåðíûõ ñåòÿõ.
Óíèôèöèðîâàííûé ïîäõîä ê ðåøåíèþ çàäà÷ ìîðôèçìà íà ãðàôàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 41
|
| id | nasplib_isofts_kiev_ua-123456789-101550 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T16:08:47Z |
| publishDate | 2008 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Ильяшенко, М.Б. 2016-06-04T19:12:34Z 2016-06-04T19:12:34Z 2008 Унифицированный подход к решению задач морфизма на графах / М.Б. Ильяшенко // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 19-41. — Бібліогр.: 21 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101550 004.021; 004.75 Описаны алгоритмы определения изоморфизма и граф-подграф изоморфизма, основанные на использовании матрицы возможных совмещений и применении инвариантов к подграфам окружения вершин. Приведены результаты сравнительного анализа скорости работы алгоритмов. Показана высокая производительность разработанных алгоритмов для класса графов, не обладающих специальными свойствами. Наведено алгоритми визначення ізоморфізму та граф-підграф ізоморфізму на базі використання матриці можливих суміщень та застосування інваріантів до підграфів оточення вершин. Наведено результати порівнювального аналізу швидкості роботи алгоритмів. Показано високу продуктивність розроблених алгоритмів для класу графів, що не мають спеціальних властивостей. Algorithms are presented for isomorphism and graph-subgraph isomorphism determination. They are based on the use of possible coincidence matrix and invariants application to subgraphs for vertexes surrounding. Comparative analysis results are offered for speed of algorithms executing. High performance of algorithms developed is shown for those graphs class which are not possessed special properties. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Унифицированный подход к решению задач морфизма на графах Generalized Approach to Morphism Problem Solution on Graphs Article published earlier |
| spellingShingle | Унифицированный подход к решению задач морфизма на графах Ильяшенко, М.Б. Математические методы и модели |
| title | Унифицированный подход к решению задач морфизма на графах |
| title_alt | Generalized Approach to Morphism Problem Solution on Graphs |
| title_full | Унифицированный подход к решению задач морфизма на графах |
| title_fullStr | Унифицированный подход к решению задач морфизма на графах |
| title_full_unstemmed | Унифицированный подход к решению задач морфизма на графах |
| title_short | Унифицированный подход к решению задач морфизма на графах |
| title_sort | унифицированный подход к решению задач морфизма на графах |
| topic | Математические методы и модели |
| topic_facet | Математические методы и модели |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101550 |
| work_keys_str_mv | AT ilʹâšenkomb unificirovannyipodhodkrešeniûzadačmorfizmanagrafah AT ilʹâšenkomb generalizedapproachtomorphismproblemsolutionongraphs |