1 UVOD
Veliki grafi igrajo v današnjem svetu čedalje pomemb-
nejšo vlogo. Socialna omrežja z milijoni ali celo milijar-
dami vozlišč (uporabnikov) in še precej več povezavami
(»prijateljstvi«) so nemara najbolj razvpit primer velikih
grafov, seveda pa še zdaleč niso edini. Pomislimo na
transportna in energetska omrežja, omrežja e-poštnih
sporočil, omrežja citiranja znanstvenih objav, lingvi-
stična omrežja itd. [1], [2], [3]
Zaradi obsega in pomembnosti velikih omrežij je
nujno, da jih znamo učinkovito preiskovati. Pogosto
nas zanima prisotnost določenih podgrafov v podanem
omrežju. Na primer, štetje trojic vzajemnih prijateljstev
v socialnem omrežju lahko prevedemo na štetje pojavi-
tev 3-ciklov v grafu omrežja. Žal pa je problem pod-
Prejet 12. junij, 2018
Odobren 23. avgust, 2018
grafnega izomorfizma (»ugotovi, ali podani gostiteljski
graf H vsebuje pojavitev podanega vzorčnega grafa G«)
NP -poln [4], pripadajoči preštevalni problem (»poišči
vse pojavitve grafa G v grafu H«) pa #P -poln [5].
To pomeni, da najverjetneje ne obstaja algoritem, ki bi
tovrstne probleme reševal v polinomskem času. Tudi
najučinkovitejši znani algoritmi v najslabšem primeru
potrebujejo eksponentno veliko časa v odvisnosti od ve-
likosti vhoda, četudi se lahko v tipičnih realnih primerih
kar dobro obnesejo [6], [7], [8].
Problem podgrafnega izomorfizma je mogoče reševati
na različne načine [9]. Med bolj znanimi je Ullman-
nov pristop [10], ki s pomočjo sestopanja gradi in
popravlja dvojiško matriko, ki predstavlja vse mogoče
monomorfizme* med vzorčnim in gostiteljskim grafom.
V našem članku pa bomo primerke vzorčnih grafov
iskali s pomočjo iskalnega načrta [11]. Iskalni načrt
je zaporedje navodil za sistematični prebor vozlišč in
povezav vzorčnega grafa, zato ga lahko uporabimo za
iskanje njegovih pojavitev v poljubnem gostiteljskem
grafu. Prvo navodilo v zaporedju obišče eno od vozlišč
vzorčnega grafa, vsako od nadaljnjih pa obišče bodisi še
ne obiskanega soseda že obiskanega vozlišča (in obenem
tudi povezavo med vozliščema) bodisi še ne obiskano
povezavo med že obiskanima vozliščema. Algoritma
za iskanje pojavitev grafov s pomočjo iskalnega načrta
ni težko zasnovati, saj moramo zgolj po vrsti slediti
iskalnemu načrtu in sestopiti, ko ne moremo več naprej
ali pa ko želimo poiskati naslednjo pojavitev vzorčnega
grafa.
Poseben izziv pri reševanju problema podgrafnega
∗Monomorfizem je injektivna preslikava med množico elementov
vzorčnega grafa in množico elementov gostiteljskega grafa, ki določa
eno od pojavitev vzorčnega grafa v gostiteljskem.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV 163
izomorfizma so simetrije v obliki avtomorfizmov vzorč-
nega grafa. Če ima vzorčni graf k avtomorfizmov, bo
iskalni postopek brez dodatnih ukrepov vsako njegovo
pojavitev v gostiteljskem grafu odkril po k-krat. Tudi če
gostiteljski graf ne vsebuje nobene pojavitve, bo iskalni
algoritem zaradi avtomorfizmov odkril več kandidatnih
delnih monomorfizmov, kot bi jih dejansko moral. Ob-
staja več pristopov za rokovanje s simetrijami [12], [13],
[14], v tem članku pa si bomo pomagali s preisko-
valno ekvivalenco vozlišč vzorčnega grafa [15], [16].
Če ima vzorčni graf simetrije, potem lahko na podlagi
preiskovalne ekvivalence postopek iskanja izboljšamo
tako, da ta tvori manj odvečnih delnih in popolnih
monomorfizmov med vzorčnim in gostiteljskim grafom
in s tem porabi manj časa. Kot bomo videli, je na podlagi
particije množice vozlišč grafa, ki jo določa preiskovalna
ekvivalenca, mogoče neposredno definirati nabor omeji-
tev, ki zmanjša redundanco iskalnega postopka.
V pričujočem članku bomo pokazali, kako lahko
algoritem za reševanje problema podgrafnega izomor-
fizma, ki temelji na iskalnem načrtu, izboljšamo tako,
da upošteva preiskovalno ekvivalenco vzorčnega grafa.
Poleg tega bomo predstavili rezultate eksperimentov, ki
smo jih izvedli na umetnih in realnih grafih. Oboje lahko
obravnavamo kot izvirni prispevek k znanosti.
V razdelku 2 bomo definirali pojme, ki jih bomo
uporabili pri opisu problema in iskalnega algoritma.
V razdelku 3 bomo natančno formulirali problem. V
razdelku 4 bomo predstavili naivni in izboljšani algo-
ritem za reševanje problema podgrafnega izomorfizma s
pomočjo iskalnega načrta. V razdelku 5 bomo rezultate
eksperimentov prikazali in o njih razpravljali, z razdel-
kom 6 pa bomo članek zaključili.
2 OZADJE
Graf G je dvojica (VG, EG), kjer je VG množica vozlišč,
EG ⊆ VG × VG pa množica povezav. Kadar bo jasno
(ali pa nepomembno), kateremu grafu pripada množica
vozlišč oziroma povezav, bomo namesto VG in EG pisali
kar V in E. V članku se bomo brez pretirane izgube
splošnosti omejili na neusmerjene grafe brez zank: E ⊆
{uv | u < v}.* Prav tako bomo predpostavili, da velja
V = {1, 2, . . . , |V |}.
Graf H je podgraf grafa G (H v G), če velja
VH ⊆ VG in EH ⊆ EG. Homomorfizem med gra-
foma G in H je funkcija h : G → H , ki ohranja
sosednosti: ∀(u, v) ∈ EG : h(u)h(v) ∈ EH . Injektivni
homomorfizem se imenuje monomorfizem ali podgrafni
izomorfizem. Če je h : G → H monomorfizem, potem
je graf h(G) v H pojavitev grafa G v grafu H .
Pojavitvi grafa G v grafu H , določeni z monomorfiz-
moma h1 : G → H in h2 : G → H , obravnavamo
kot istovetni (kot eno in isto pojavitev), če pokrivata
∗Vrstni red krajišč povezave ni pomemben: zapisa uv in vu oba
pomenita povezavo med vozliščema u in v.
isto množico vozlišč in povezav grafa H , torej če
velja {h1(v) | v ∈ VG} = {h2(v) | v ∈ VG} in
{h1(e) | e ∈ EG} = {h2(e) | e ∈ EG}.
Bijektivni homomorfizem se imenuje izomorfizem.
Grafa G in H sta izomorfna, če obstaja izomorfizem
h : G → H . Izomorfizem v istem grafu (h : G → G)
se imenuje avtomorfizem. Množico vseh avtomorfizmov
grafa G označimo z Aut(G).
Monomorfizem {1 7→ v1, 2 7→ v2, . . . , |V | 7→ v|V |}
bomo zapisali kar kot v1v2 . . . v|V |. Graf C4 (4-cikel),
prikazan na sliki 2, ima 8 avtomorfizmov: Aut(C4) =
{1234, 2341, 3412, 4123, 4321, 3214, 2143, 1432}.
Eden od številnih monomorfizmov med grafom C4 in
grafom na sliki 3 je {1 7→ 7, 2 7→ 11, 3 7→ 10, 4 7→ 6}
oziroma 7 11 10 6.
Iskalni načrt [11], [17] je zaporedje navodil za prebor
celotnega vzorčnega grafa G, ki nam omogoča iskanje
pojavitev grafa v poljubnem gostiteljskem grafu H . Prvo
navodilo je vedno oblike [u]; razumemo ga kot »obišči
poljubno vozlišče w v grafu H in ga priredi vozlišču u v
grafu G (tj. vzpostavi h(u) = w)«. Vsako od nadaljnjih
navodil pa ima bodisi obliko [u→ v] (»prični v vozlišču,
prirejenem vozlišču u, obišči enega od njegovih še ne
obiskanih sosedov in izbranega soseda priredi vozlišču
v) bodisi obliko [u?v] (»preveri, ali sta vozlišči grafa H ,
prirejeni vozliščema u in v, povezani«). Navodilo oblike
[u → v] obišče novo vozlišče in povezavo, navodilo
oblike [u ? v] pa samo novo povezavo. Na primer, eden
od iskalnih načrtov za graf C4 se glasi 〈[1], [1 → 2],
[2→ 3], [3→ 4], [1 ? 4]〉.
Če v gostiteljskem grafu izpolnimo iskalni načrt za
podani vzorčni graf na vse mogoče načine (tj. v vsa-
kem koraku preizkusimo vse veljavne možnosti), bomo
zanesljivo našli vse pojavitve vzorčnega grafa v gosti-
teljskem. V tem smislu so vsi iskalni načrti za podani
graf med seboj enakovredni. Kot bomo videli, pa niso
nujno enakovredni po učinkovitosti iskanja.
Množica A ⊆ Aut(G) pokriva množico P = {v1,
v2, . . . , vk} ⊆ V (oznaka: cover(A,P )), če za vsako
permutacijo σ : P → P obstaja avtomorfizem a ∈ A,
tako da velja a(v1) = σ(v1), a(v2) = σ(v2), . . . ,
a(vk) = σ(vk). Na primer, množica Aut(C4) pokriva
množico {1, 3}, saj avtomorfizem 1234 zajema per-
mutacijo {1 7→ 1, 3 7→ 3}, avtomorfizem 3214 pa
permutacijo {1 7→ 3, 3 7→ 1}. Stabilizator množice
A ⊆ Aut(G) glede na množico P ⊆ V je množica vseh
avtomorfizmov v A, ki fiksirajo vse elemente množice
P : Stab(A,P ) = {a ∈ A | ∀v ∈ P : a(v) = v}. Na
primer, Stab(Aut(C4), {1, 3}) = {1234, 1432}.
Zaporedje P = 〈P1, P2, . . . , Ps〉 je urejena particija
množice V , če velja
⋃s
i=1 Pi = V in Pi ∩ Pj = ∅
za vse i 6= j. Urejena particija 〈P1, P2, . . . , Ps〉 je
preiskovalno ekvivalentna, če za vse i ∈ {1, . . . , s} velja
cover(Ai−1, Pi) in Ai = Stab(Ai−1, Pi), pri čemer je
A0 = Aut(G). Na primer, pri grafu C4 je urejena parti-
cija 〈{1, 3}, {2, 4}〉 preiskovalno ekvivalentna. To velja
tudi za particijo 〈{1, 2}, {3}, {4}〉, ne pa za particijo
164 FÜRST, ČIBEJ, MIHELIČ
〈{1, 2}, {3, 4}〉, saj množica Stab(Aut(G), {1, 2}) =
{1234} ne pokriva množice {3, 4}.
Množica P = {P1, P2, . . . , Ps} je particija množice
V , če velja
⋃s
i=1 Pi = V in Pi ∩ Pj = ∅ za vse i 6= j.
Particija {P1, P2, . . . , Ps} je preiskovalno ekvivalentna,
če obstaja permutacija σ : {1, . . . , s} → {1, . . . , s}, tako
da je urejena particija 〈Pσ(1), Pσ(2), . . . , Pσ(s)〉 preisko-
valno ekvivalentna.
Kot bomo pokazali v razdelku 4, lahko pri reševanju
problema podgrafnega izomorfizma na podlagi preisko-
valno ekvivalentne particije {P1, P2, . . . , Ps} vpeljemo
omejitve, ki število odkritih monomorfizmov med vzorč-
nim in gostiteljskim grafom zmanjšajo za faktor F =
|P1|! |P2|! . . . |Ps|!, zato med različnimi kandidatnimi
preiskovalno ekvivalentnimi particijami izberemo opti-
malno — tisto, pri kateri je faktor (ocena) F največji.
Pri grafu C4 je optimalna particija {{1, 3}, {2, 4}},
pri grafu C6 (slika 2) pa particija {{1, 3, 5}, {2}, {4},
{6}} z oceno 3! 1! 1! 1! = 6; alternativa {{1, 3}, {2, 5},
{4}, {6}} je z oceno 2! 2! 1! 1! = 4 slabša. Oceno
optimalne preiskovalno ekvivalentne particije grafa G
bomo označili s F ∗(G).
3 OPREDELITEV PROBLEMA
Vhod v problem, ki ga rešujemo v članku, sestavljajo
• vzorčni graf G,
• gostiteljski graf H ,
• iskalni načrt za graf G in
• preiskovalno ekvivalentna particija grafa G,
pričakovani izhod pa je seznam vseh pojavitev grafa G v
grafu H , pri čemer ne zahtevamo, da se vsaka pojavitev
izpiše samo po enkrat.
4 NAŠ PRISTOP
Najprej pokažimo naslednjo trditev in njeno posledico:
Trditev 1. Naj bo 〈P1, P2, . . . , Ps〉 preiskovalno ek-
vivalentna urejena particija množice V , pri čemer je
Pi = {vi,1, vi,2, . . . , vi,ki} in vi,1 < vi,2 < . . . < vi,ki
za vse i ∈ {1, . . . , s}. Naj bo HG pojavitev grafa G
v grafu H . Potem obstaja izomorfizem h : G → HG,
za katerega pri vseh i ∈ {1, . . . , s} velja h(vi,1) <
h(vi,2) < . . . < h(vi,ki).
Dokaz: Naj bo h0 : G → HG poljuben izomor-
fizem in naj bodo σ∗1 : P1 → P1, . . . , σ∗s : Ps → Ps
takšne permutacije, da za vse i ∈ {1, . . . , s} velja
h0(σ
∗
i (vi,1)) < h0(σ
∗
i (vi,2)) < . . . < h0(σ
∗
i (vi,ki)). Naj
bo permutacija σ∗ : V → V definirana kot σ∗(vi,j) =
σ∗i (vi,j) za vse i ∈ {1, . . . , s} in j ∈ {1, . . . , ki}.
Naj bo σ1 permutacija množice P1, σ2 permutacija
množice P2 itd. in naj A(σ1, σ2, . . . , σr) označuje mno-
žico avtomorfizmov a ∈ Aut(G) z lastnostjo a(vi,j) =
σi(vi,j) za vse i ∈ {1, . . . , r} in j ∈ {1, . . . , ki}. Ker
po definiciji preiskovalne ekvivalence množica Aut(G)
pokriva množico P1, je množica A(σ1) neprazna za
pojubno permutacijo σ1 množice P1. Ker množica
Stab(Aut(G), P1) pokriva množico P2, je neprazna
tudi množica A(σ1, σ2), in to za poljubni par permu-
tacij σ1 in σ2. Če razmislek nadaljujemo, ugotovimo,
da za poljubno množico permutacij σ1 : P1 → P1,
. . . , σs : Ps → Ps množica A(σ1, σ2, . . . , σs) vsebuje
vsaj en avtomorfizem. Vsak avtomorfizem iz množice
A(σ∗1 , σ
∗
2 , . . . , σ
∗
s ) premeša vozlišča v vsaki posamezni
množici P1, . . . , Ps tako, da h = h0◦σ∗ postane izomor-
fizem z iskano lastnostjo: po definiciji iz prejšnjega od-
stavka velja namreč h(vi,1) < h(vi,2) < . . . < h(vi,ki)
za vsak i ∈ {1, . . . , s}.
Posledica 2. Pri uporabi preiskovalno ekvivalen-
tne particije {P1, P2, . . . , Ps} je število izomorfizmov
h : G → HG, ki izpolnjujejo pogoje iz trditve 1, enako
|Aut(G)| / F ∗(G).
Dokaz: Število vseh izomorfizmov G → HG je
enako številu avtomorfizmov na grafu G. Vendar pa
v vsaki množici |Pi|! izomorfizmov, ki v grafu HG
zajamejo vseh |Pi|! permutacij slike množice Pi, le eden
izpolnjuje pogoj h(vi,1) < h(vi,2) < . . . < h(vi,ki). Ker
to velja za vse i ∈ {1, . . . , s}, se število izomorfizmov
zmanjša za faktor F ∗(G) = |P1|! |P2|! . . . |Ps|!.
Iz trditve 1 neposredno sledi, da se lahko pri iskanju
pojavitev vzorčnega grafa G v gostiteljskem grafu H
omejimo samo na tiste (delne in popolne) monomor-
fizme G → H , za katere veljajo navedene omejitve. Z
drugimi besedami: če vozlišči u in v z lastnostjo u < v
pripadata istemu ekvivalenčnemu razredu v preiskovalno
ekvivalentni particiji grafa G, potem ohranimo (in raz-
vijamo) zgolj tiste delne in popolne monomorfizme
h : G → H , za katere velja h(u) < h(v), vse druge
pa zavržemo.
Algoritem za iskanje pojavitev s pomočjo iskalnega
načrta je prikazan kot algoritem 1. Postopek se sproži
s klicem procedure IZVRSI, ki sprejme vzorčni graf G,
iskalni načrt zanj (zaporedje navodil 〈D1, D2, . . . , Dr〉,
pri čemer je navodilo D1 vedno oblike [v0]), preisko-
valno ekvivalentno particijo (P) grafa G in gostiteljski
graf H . Algoritem po korakih — z zaporednim izvrševa-
njem navodil iskalnega načrta — gradi monomorfizem
h : G → H . Navodilo [v0] seveda izpolnjujejo vsa voz-
lišča grafa H . Navodilo [v1 → v2] pa algoritem izpolni
tako, da izbere enega od sosedov w2 vozlišča h(v1) v
grafu H , ki v trenutnem poskusu iskanja pojavitve grafa
G še ni bil obiskan in ki izpolnjuje pogoj
∀v ∈ h−1(VH) : (∃P ∈ P : {v, v2} ⊆ P ) =⇒
(v < v2 ⇐⇒ h(v) < w2), (1)
pri čemer h−1(VH) označuje množico vseh vozlišč
v ∈ VG, za katera po trenutnem delnem monomorfizmu
h že obstaja slika h(v) ∈ VH . Ko algoritem izpolni vsa
navodila iskalnega načrta in tako zgradi popoln mono-
morfizem, izpiše pojavitev, ki jo določa monomorfizem,
nato pa sestopi, da poišče še druge monomorfizme.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV 165
Sestopimo tudi tedaj, ko nobeno vozlišče grafa H ne
izpolnjuje trenutnega navodila oziroma pogoja (1).
Postopek poleg delnega monomorfizma h : G → H
vzdržuje tudi množico Visited , ki vsebuje vsa vozlišča
grafa H , ki smo jih pri gradnji tekočega monomorfizma
že obiskali. Preslikava h : G → H je, kot vemo, mo-
nomorfizem samo tedaj, ko se različna vozlišča grafa G
preslikajo v različna vozlišča grafa H .
Množica Neighbors(u) = {v ∈ V | uv ∈ E} vsebuje
vse sosede vozlišča u. Spremenljivka i v pomožni proce-
duri IZVRSIPOM podaja zaporedno številko trenutnega
navodila iskalnega načrta.
V razdelku 5 bomo Algoritem 1 primerjali z njegovo
naivno različico. Ta se od Algoritma 1 razlikuje le po
funkciji PREVERIPE:
function PREVERIPE(G, P , h, v2, w2)
return true
end function
Naivni algoritem preiskovalne ekvivalence sploh ne
upošteva in zgolj premočrtno na vse mogoče načine
izpolnjuje navodila iskalnega načrta.
Oglejmo si razliko med delovanjem naivnega in iz-
boljšanega algoritma na primeru iskanja pojavitev grafa
C4 v grafu K4 (slika 2). Vse tri pojavitve so prikazane
na sliki 1. Graf C4 ima 8 avtomorfizmov (|Aut(C4)|),
ocena njegove optimalne preiskovalno ekvivalentne par-
ticije (F ∗(C4)) pa znaša 4. Zato naivni algoritem vsako
pojavitev grafa C4 odkrije po 8-krat, izboljšani pa le po
dvakrat (= |Aut(C4)|/F ∗(C4)). Na primer, za pojavitev,
določeno z monomorfizmom 1324, bi naivni algoritem
tvoril monomorfizme 1324, 3241, 2413, 4132, 4231,
2314, 3142 in 1423, izboljšani pa le monomorfizma
1324 in 3142, saj sta edina, ki izpolnjujeta zahtevi
h(1) < h(3) in h(2) < h(4).
1 2
34
h = 1234
1 2
34
h = 1243
1 2
34
h = 1324
Slika 1: Vse pojavitve grafa C4 v grafu K4
5 EKSPERIMENTALNI REZULTATI IN
RAZPRAVA
S pomočjo eksperimentov smo poskušali empirično od-
govoriti na naslednja raziskovalna vprašanja:
• Kako se po učinkovitosti razlikujeta algoritem, ki
upošteva preiskovalno ekvivalenco vzorčnega grafa,
in algoritem, ki zgolj premočrtno na vse mogoče
načine izpolnjuje navodila iskalnega načrta?
• Kako na delovanje algoritma vpliva ocena pre-
iskovalno ekvivalentne particije in kako velikost
vzorčnega grafa?
• Ali izbira drugačnega iskalnega načrta za isti
vzorčni graf vpliva na učinkovitost algoritma?
Večino poskusov smo izvedli z vzorčnimi grafi, prika-
zanimi na sliki 2. Barve vozlišč označujejo posamezne
ekvivalenčne razrede v optimalni preiskovalno ekviva-
lentni particiji. Vozlišča iste barve pripadajo istemu
ekvivalenčnemu razredu, neobarvana vozlišča pa vsak
svojemu. Na primer, optimalna preiskovalno ekvivalen-
tna particija grafa C6 je {{1, 3, 5}, {2}, {4}, {6}}.
Števili ob oznaki grafa (npr. (8 / 4) pri grafu C4)
podajata število avtomorfizmov (|Aut(G)|) in oceno
optimalne preiskovalno ekvivalentne particije (F ∗(G)).
Kot smo že povedali, bo naivni algoritem vsako poja-
vitev grafa odkril po |Aut(G)|-krat, izboljšani pa po
(|Aut(G)| / F ∗(G))-krat.
V nadaljevanju bomo z N označevali število pojavitev
podanega vzorčnega grafa G v podanem gostiteljskem
grafu H , s t0 oziroma t+ pa čas v milisekundah, ki ga
za podani par grafov G in H potrebuje naivni oziroma
izboljšani algoritem. Algoritma smo implementirali v
programskem jeziku C, poganjali pa na računalniku s
3,40-gigaherčnim 8-jedrnim procesorjem Intel Core i7-
3770.
V prvem nizu poskusov smo Algoritem 1 in njegovo
naivno različico preizkušali na umetnih gostiteljskih
grafih, in sicer na grafih Mn z (n + 1)2 vozlišči in
2n(n + 1) povezavami (E = {v, v + 1 | v 6≡ 0
(mod (n + 1))} ∪ {(v, v + n + 1) | v ≤ n(n + 1)})
in na grafih Kn z n vozlišči in n(n−1)/2 povezavami
(E = {uv | u < v}). Graf M3 je prikazan na sliki 3.
Tabela 1 prikazuje rezultate izvajanja obeh algoritmov
na vseh parih vzorčnih grafov in gostiteljskih grafov
M100 in K15. Kot bi lahko pričakovali, razmerje med
časom delovanja naivnega in izboljšanega algoritma
narašča z naraščajočo oceno optimalne preiskovalno
ekvivalentne particije. Razlika je še posebej izrazita pri
vzorčnih grafih Kn. Na primer, pri grafu K9 se število
odkritih pojavitev z uporabo preiskovalne ekvivalence
zmanjša za faktor F ∗(K9) = 9! = 362 880, poraba časa
pa za faktor, večji od 50 000. Tudi v primerih, ko graf
H ne vsebuje nobene pojavitve grafa G, je izboljšani
algoritem hitrejši od naivnega, saj uporaba preiskovalne
ekvivalence omeji tudi število vzpostavljenih delnih, ne
samo popolnih monomorfizmov.
Iz tabele 1 razberemo tudi to, da se razmerje med
izvajalnim časom naivnega in izboljšanega algoritma
pri večjih vzorčnih grafih približuje oceni optimalne
preiskovalno ekvivalentne particije za vzorčni graf. S
povečevanjem vzorčnega grafa se namreč zmanjšuje
časovni delež programske kode, ki je neodvisna od veli-
kosti vzorčnega grafa in je skupna obema algoritmoma.
Postopno približevanje ciljnemu razmerju pride še bolj
do izraza, če algoritma poženemo na družini grafov z
različno velikostjo, a enako oceno optimalne preisko-
valno ekvivalentne particije. Tabela 2 prikazuje rezultate
iskanja grafa Ln v grafu M100 za n ∈ {2, . . . , 14}.
Vidimo, da se razmerje v porabi časa približuje vrednosti
166 FÜRST, ČIBEJ, MIHELIČ
Algoritem 1 Iskanje pojavitev grafa s pomočjo iskalnega načrta in preiskovalne ekvivalence
1: function IZVRSI(G, 〈[v0], D2, . . . , Dr〉, P , H)
2: for all v ∈ VG do
3: h(v) := ⊥ . to pomeni, da v (še) nima svoje slike v grafu H
4: end for
5: for all w0 ∈ VH do
6: h(v0) := w0 . izpolnimo prvo navodilo iskalnega načrta
7: Visited := {w0}
8: IZVRSIPOM(G, 〈D2, . . . , Dr〉, 2, P , H , h, Visited )
9: end for
10: end function
11:
12: function IZVRSIPOM(G, 〈D2, . . . , Dr〉, i, P , H , h, Visited )
13: if i = r then
14: izpiši h(G) . izpolnili smo vsa navodila iskalnega načrta
15: else
16: if Di = [v1 → v2] then
17: for all w2 ∈ Neighbors(h(v1)) do . navodilo izpolnimo na vse mogoče načine
18: if w2 6∈ Visited ∧ PREVERIPE(G, P , h, v2, w2) then
19: h(v2) := w2
20: Visited := Visited ∪ {w2}
21: IZVRSIPOM(G, 〈D2, . . . , Dr〉, i+ 1, P , H , h, Visited )
22: Visited := Visited \ {w2}
23: h(v2) := ⊥
24: end if
25: end for
26: else if Di = [v1 ? v2] then
27: if h(v1)h(v2) ∈ EH then . preverimo obstoj povezave med že obiskanima vozliščema
28: IZVRSIPOM(G, 〈D2, . . . , Dr〉, i+ 1, P , H , h, Visited )
29: end if
30: end if
31: end if
32: end function
33:
34: function PREVERIPE(G, P , h, v2, w2)
35: for all v ∈ VG do . preverimo, ali lahko v monomorfizem h dodamo preslikavo v2 7→ w2
36: if h(v) 6= ⊥ ∧ ∃P ∈ P : {v, v2} ⊆ P then
37: if (v < v2 ∧ h(v) > w2) ∨ (v > v2 ∧ h(v) < w2) then
38: return false
39: end if
40: end if
41: end for
42: return true
43: end function
F ∗(Ln) = 2.
Poskusi so pokazali, da iskalni načrt praviloma nima
skoraj nikakršnega vpliva na delovanje algoritma, kljub
temu pa neugodni primeri obstajajo. Vsi dosedanji po-
skusi so bili izvedeni z iskalnimi načrti, ki vozlišča
vzorčnih grafov obiskujejo po vrsti od vozlišča 1 do
vozlišča |V |. Pojavitve grafa C11, denimo, odkrivamo
z iskalnim načrtom N1 = 〈[1], [1 → 2], [2 → 3],
. . . , [9 → 10], [10 → 11], [11 ? 1]〉. V kombinaciji z
optimalno preiskovalno ekvivalentno particijo {{1, 2},
{3}, {4}, . . . , {11}} je iskalni načrt N1 ugoden, saj
moramo že pri izpolnjevanju drugega navodila upošte-
vati omejitev h(1) < h(2). To pomeni, da že zgodaj
v postopku iskanja pojavitve zatremo nekatere odvečne
delne monomorfizme. Iskalni načrt N2 = 〈[2], [2→ 3],
[3→ 4], . . . , [9→ 10], [10→ 11], [11→ 1], [1 ? 2]〉 pa
je v obravnavem primeru izrazito neugoden, saj omejitev
h(1) < h(2) učinkuje šele pri izpolnjevanju predza-
dnjega navodila. Preden bo algoritem neperspektivni
monomorfizem zavrgel, ga bo zgradil skoraj v celoti.
ISKANJE VZORČNIH GRAFOV S POMOČJO ISKALNEGA NAČRTA OB PRISOTNOSTI AVTOMORFIZMOV 167
Tabela 1: Rezultati na umetnih gostiteljskih grafih
H G N t0 t+
M100 L4 178 596 31,0 19,5
C4 10 000 20,3 14,0
K4 0 7,1 6,1
L6 1 387 104 244 136
C6 19 800 127 58
K6 0 7,0 6,4
L9 28 273 662 5430 2920
C9 0 2380 977
K9 0 7,1 6,9
K15 L4 16 380 5,4 2,9
C4 4095 7,2 3,0
K4 1365 10,1 0,75
L6 1 801 800 274 143
C6 300 300 361 61
K6 5005 660 2,54
L9 908 107 200 159 000 84 100
C9 100 900 800 202 000 34 200
K9 5005 527 000 10,3
Tabela 2: Iskanje pojavitev grafa Ln v grafu M100 za različne
vrednosti n
G N t0 t+ t0 / t+
L2 20 200 5,78 4,98 1,16
L3 59 998 12,1 9,84 1,23
L4 178 596 31,5 20,0 1,58
L5 492 006 86,9 53,2 1,63
L6 1 387 104 249 139 1,79
L7 3 780 626 700 395 1,77
L8 10 455 084 1970 1080 1,82
L9 28 273 662 5430 2980 1,82
L10 77 233 024 15 400 8230 1,87
L11 207 943 998 42 400 22 700 1,87
L12 563 572 700 118 000 63 000 1,87
L13 1 512 373 042 334 000 176 000 1,90
L14 4 077 286 312 919 000 483 000 1,90
Kot prikazujejo rezultati za iskanje pojavitev grafa C11 v
grafu K11 (tabela 3), je razlika med iskalnima načrtoma
N1 in N2 očitna. (Graf K11 vsebuje 1 814 400 pojavitev
grafa C11.)
Tabela 3: Iskanje pojavitev grafa C11 v grafu K11 s pomočjo
ugodnega in neugodnega iskalnega načrta
Iskalni načrt t0 t+
N1 8340 4210
N2 8460 6960
Nazadnje predstavljamo še rezultate izvajanja obeh
algoritmov na gostiteljskih grafih, ki izvirajo iz realnega
sveta. Algoritma smo preizkusili na šestih grafih iz baz
KONECT* (grafi Les Misérables, US Power Grid, David
Copperfield in Jazz Musicians) [1] in SNAP† (grafa
ca-HepTh in ca-CondMat) [2]. Grafom smo odstranili
morebitne oznake, zanke in večkratne povezave med
istim parom vozlišč, morebitne usmerjene povezave pa
smo spremenili v neusmerjene. Nato smo v vsakem od
grafov z naivnim in izboljšanim algoritmom našteli vse
pojavitve grafov L4, C4 in K4 in dobili rezultate, zbrane
v tabeli 4. Tudi tukaj vidimo, da izboljšani algoritem
v vseh primerih prekaša naivnega, razmerje v porabi
časa pa je marsikje blizu |F ∗(G)|. Ni presenetljivo, da
na porabo časa bolj kot sama velikost gostiteljskega
grafa vpliva razmerje med številom povezav in vozlišč.
Večje povprečno število povezav na vozlišče na splošno
pomeni tudi več pojavitev vzorčnega grafa.
Tabela 4: Rezultati na realnih gostiteljskih grafih
H G N t0 t+
Les Misérables L4 26 784 5,9 2,0
|V | = 77 C4 2672 8,9 3,7
|E| = 254 K4 639 7,6 0,8
US Power Grid L4 52 556 13 8,5
|V | = 4941 C4 979 12 4,5
|E| = 6594 K4 90 6,6 2,4
David Copperfield L4 61 254 15 4,5
|V | = 112 C4 2579 9,4 2,9
|E| = 425 K4 58 5,8 0,9
Jazz Musicians L4 3 850 915 480 260
|V | = 198 C4 406 441 870 250
|E| = 2742 K4 78 442 670 43
ca-HepTh L4 4 207 311 550 300
|V | = 9877 C4 239 081 630 200
|E| = 25 973 K4 65 592 360 36
ca-CondMat L4 50 543 325 6300 3500
|V | = 23 133 C4 1 505 383 9900 2600
|E| = 93 439 K4 294 008 3700 270
6 SKLEP
Predstavili smo algoritem za reševanje problema pod-
grafnega izomorfizma s pomočjo iskalnega načrta, ki
upošteva avtomorfizme vzorčnega grafa in zato deluje
učinkoviteje kot premočrtni iskalni algoritem. Algori-
tem s pomočjo poznavanja preiskovalno ekvivalentne
particije vzorčnega grafa omeji množico obravnavanih
monomorfizmov med vzorčnim in gostiteljskim grafom.
Algoritem smo preizkusili na umetnih in realnih go-
stiteljskih grafih. Proučili smo vpliv ocene optimalne
∗http://konect.uni-koblenz.de/
†http://snap.stanford.edu/data/
168 FÜRST, ČIBEJ, MIHELIČ
1 2 3 4
L4 (2 / 2)
1 2 3 4 5 6
L6 (2 / 2)
1 2 3 4 5 6 7 8 9
L9 (2 / 2)
1
2
3
4
C4 (8 / 4)
1 2
3
45
6
C6 (12 / 6)
1
2 3
4
5
67
8
9
C9 (18 / 6)
1
2
3
4
K4 (24 / 24)
1 2
3
45
6
K6 (720/720)
1
2 3
4
5
67
8
9
K9 (362 880/362 880)
Slika 2: Grafi, ki smo jih uporabljali v večini poskusov
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Slika 3: Graf M3
preiskovalne ekvivalence, velikosti vzorčnega grafa in
zaporedja navodil v iskalnem načrtu.
Preiskovalna ekvivalenca ne vodi nujno do optimal-
nega nabora omejitev. Na primer, pri 4-ciklu dobimo
na podlagi optimalne preiskovalno ekvivalentne particije
nabor omejitev {h(1) < h(3), h(2) < h(4)}, toda še
večje prihranke nam ponuja nabor {h(1) < h(2) <
h(4)}. Tega nabora ne moremo izpeljati iz preiskovalne
ekvivalence, kljub temu pa se lahko prepričamo, da z
njegovo uporabo ne izpustimo nobene pojavitve 4-cikla,
ne glede na oštevilčenje vozlišč v gostiteljskem grafu.
Ena od zamisli za nadaljnje delo je torej iskanje tovrstnih
omejitev, zanimiva pa bi bila tudi študija vpliva omejitev
na različne iskalne algoritme.