Részgráf mintázatok

Ebben a szakaszban az asszociációs elemzés olyan módszereivel foglalkozunk, melyek az elemhalmazokon és sorozatokon túlmutató, bonyolultabb konstrukciókra alkalmazhatóak. Ilyenek például a kémiai vegyületek, a háromdimenziós fehérjeszerkezetek, a hálózati topológiák és a faszerkezetű XML dokumentumok. Ezeket a konstrukciókat (a továbbiakban: egyedeket) gráfreprezentációval modellezhetjük, ahogy az a 7.7. táblázatban is látható.

7.7. táblázat - Különböző alkalmazási területek egyedeinek gráfreprezentációja

Alkalmazás

Gráfok

Csúcsok

Élek

Web bányászat

Webböngészési

Weboldalak

Oldalak közötti

mintázatok

hiperlinkek

Számítógépes

Kémiai vegyületek

Atomok vagy

Atomok vagy ionok

kémia

szerkezete

ionok

közötti kötések

Hálózati

Számítógéphálózatok

Számítógépek és

Gépek közötti

számítások

szerverek

összeköttetések

Szemantikus

XML dokumentumok

XML elemek

Elemek szülő-gyermek

web

kapcsolatai

Bioinformatika

Fehérjeszerkezetek

Aminosavak

Kapcsoló gyökök


Az ilyen típusú adatok esetén hasznos egy olyan adatbányászati tevékenység végrehajtása, amely gráfok halmazából nyer ki gyakori részstruktúrákat. Ezt a feladatot gyakori részgráfok bányászatának nevezik. A gyakori részgráfok bányászatának egy lehetséges alkalmazási területe a számítógépes kémia. Minden évben új kémiai vegyületeket terveznek gyógyszerekhez, rovarirtószerekhez, műtrágyákhoz, stb. Bár közismert, hogy a kémiai vegyületek felépítése nagyban befolyásolja kémiai tulajdonságaikat, nehéz a közöttük lévő pontos kapcsolatot kimutatni. Ezt a feladatot segíthet megoldani a gyakori részgráfok bányászata azon részstruktúrák azonosításával, amelyeket általában ismert vegyületek bizonyos tulajdonságaihoz társítanak. Ilyen információk segítségével a tudósok bizonyos, kívánt tulajdonságokkal rendelkező új vegyületeket fejleszthetnek ki.

Ebben a szakaszban egy módszertant mutatunk be, amellyel asszociációs elemzést alkalmazhatunk gráf-alapú adatokra. Először áttekintünk néhány alapvető gráfelméleti fogalmat és definíciót. Ezután bevezetjük a gyakori részgráfok bányászatának feladatát, majd leírjuk, hogyan lehet a hagyományos Apriori algoritmust kiterjeszteni úgy, hogy alkalmas legyen ilyen mintázatok feltárására.

Gráfok és részgráfok

A gráf egy olyan adatszerkezet, amellyel egyedek közötti kapcsolatokat ábrázolhatunk. Matematikai értelemben egy gráf csúcsok egy V halmazából és a csúcsokat páronként összekötő élek egy E halmazából áll. Minden élt egy ( v i , v j ) csúcspárral jelölünk, ahol v i , v j V . Minden v i csúcshoz hozzárendelhetünk egy l( v i ) címkét, amely az egyed nevét ábrázolja. Hasonlóképpen, minden ( v i , v j ) élhez is hozzárendelhetünk egy, a két egyed közötti kapcsolatot leíró l( v i , v j ) címkét. tab4:graph_examples. táblázatban különböző típusú gráfok csúcsait és éleit láthatjuk. Egy webgráfban például a csúcsok weboldalakhoz tartoznak, az élek pedig a weboldalak közötti hiperlinkeket reprezentálják.

7.4. Definíció

(Részgráf) Egy G'= (V',E') gráf a G=(V,E) gráf részgráfja, ha csúcsainak V' halmaza a V részhalmaza, éleinek E' halmaza pedig E részhalmaza. A részhalmaz kapcsolatot G' S G módon jelöljük.

A 7.9. ábrán egy olyan gráf látható, amelynek 6 csúcsa és 11 éle van, továbbá a lehetséges részgráfjai közül egy. A 7.9. (b) ábrán látható részgráfba az eredeti gráf 6 csúcsa közül csak 4, és 11 éle közül is csak 4 tartozik bele.

7.9. ábra - Példa részgráfra

Példa részgráfra

7.5. Definíció

(Támogatottság) Ha adott gráfok egy G halmaza, akkor egy g részgráf támogatottságát az összes g -t részgráfként tartalmazó gráf hányadaként definiáljuk, azaz

s(g)= |{ G i |g S G i ,   G i G}| |G| . (7.2)

7.2. Példa.

Tekintsük a 7.10. ábrán látható G 1 , , G 5 gráfokat. Az ábra jobb felső sarkában ábrázolt g 1 gráf G 1 , G 3 , G 4 és G 5 részgráfja, így s( g 1 )=4/5=80% . Hasonlóképpen kiszámítható, hogy s( g 2 )=60% , mivel g 2 a G 1 , G 2 és G 3 gráfok részgráfja, míg s( g 3 )=40% , mert g 3 a G 1 és G 3 gráfok részgráfja.

7.10. ábra - Egy részgráf támogatottságának kiszámítása gráfok egy halmazára

Egy részgráf támogatottságának kiszámítása gráfok egy halmazára

Gyakori részgráfok bányászata

Ebben a szakaszban a gyakori részgráf bányászat problémájának egy formális definícióját mutatjuk be, és ezen feladat összetettségét érzékeltetjük .

7.6. Definíció

(Gyakori részgráfok bányászata) Ha adott gráfok egy G halmaza és egy minsup támogatottsági küszöb, akkor a gyakori részgráfok bányászatának célja minden olyan g részgráf feltárása, melyre s(g)minsup . Bár ez a megfogalmazás általánosságban bármilyen gráftípusra alkalmazható, ebben a fejezetben az irányítatlan és összefüggő gráfokra helyezzük a hangsúlyt. A következőkben ezen gráfok definícióit adjuk meg:

  1. Egy gráf összefüggő, ha a gráf bármely két csúcsa között létezik út, ahol út alatt csúcsok egy olyan v 1 v 2 v k sorozatát értjük, melyben minden egymást követő ( v i , v i+1 ) csúcs között létezik él.

  2. Egy gráf irányítatlan, ha csak irányítatlan éleket tartalmaz. Egy ( v i , v j ) él irányítatlan, ha nem megkülönböztethető ( v j , v i ) -től.

A más típusú részgráfok (irányított vagy nem összefüggő) kezeléséhez szükséges módszerek kidolgozásának feladatát meghagyjuk az Olvasónak (lásd a 15. feladatot a 497. oldalon).

A gyakori részgráfok bányászata nagy számításigényű feladat, mert a keresési tér exponenciális. Hogy a feladat összetettségét érzékeltessük, tekintsünk egy d számú egyedet tartalmazó adatállományt. A gyakori elemhalmazok bányászatánál minden egyed egy elem, a feltárásra váró keresési tér mérete pedig 2 d , amely a generálható elemhalmaz jelöltek száma. Gyakori részgráfok bányászatánál minden egyed egy csúcs, amelyből legfeljebb d1 él vezethet más csúcsokba. Ha feltételezzük, hogy a csúcsok címkéi egyediek, az összes lehetséges részgráf száma

i=1 d ( d i )× 2 i(i1)/2 ,

ahol d i azon lehetőségek száma, ahányféleképpen i számú csúcsot választhatunk ki egy részgráf kialakításához, 2 i(i1)/2 pedig a csúcsok közötti élek maximális száma. A 7.8. táblázatban az elemhalmazok és részgráfok számát hasonlítjuk össze különböző d értékekre.

7.8. táblázat - Elemhalmazok és részgráfok számának összehasonlítása különböző d dimenziószámok esetén

Egyedek száma ( d )

1

2

3

4

5

6

7

8

Elemhalmazok száma

2

4

8

16

32

64

128

256

Részgráfok száma

2

5

18

113

1 450

40 069

2 350 602

28 619 2513


A részgráf jelöltek száma valójában sokkal kisebb, mert a 7.8. táblázatban megadott értékek tartalmazzák a nem összefüggő részgráfokat is. A nem összefüggő részgráfokat általában figyelmen kívül hagyjuk, mert kevésbé érdekesek, mint az összefüggő részgráfok.

7.11. ábra - Nyers erőn alapuló módszer gyakori részgráfok bányászatára

Nyers erőn alapuló módszer gyakori részgráfok bányászatára

Nyers erőn alapuló megközelítéssel ezt úgy tehetjük meg, hogy jelöltként generáljuk az összes összefüggő részgráfot, és kiszámítjuk azok támogatottságát. Tekintsük például a 7.11. (a) ábrán látható gráfokat. Feltéve, hogy a csúcsok címkéit az {a,b} halmazból, az élek címkéit pedig a {p,q} halmazból választjuk, az összefüggő, egy és három közötti számú csúcsból álló részgráfok listája a 7.11. (b) ábrának megfelelő lesz. A következő okokból sokkal nagyobb a részgráf jelöltek száma, mint az elemhalmaz jelöltek száma a hagyományos asszociációs szabály bányászatban:

  1. Egy elem legfeljebb egyszer jelenhet meg egy elemhalmazban, míg egy csúcscímke többször is megjelenhet egy gráfban.

  2. Ugyanahhoz a csúcscímke párhoz több élcímke is választható.

Mivel a részgráf jelöltek száma igen nagy, egy nyers erőn alapuló algoritmus akár közepes méretű gráfon alkalmazva is összeomolhat.

Apriori-szerű módszer

Ebben a szakaszban azt vizsgáljuk, hogy hogyan fejleszthetünk ki egy Apriori-szerű algoritmust, amellyel gyakori részgráfokat tárhatunk fel.

Az adatok transzformálása

Egy lehetséges megközelítés minden gráf egy tranzakciószerű formátumba alakítása, hogy alkalmazhatóak legyenek az olyan meglévő algoritmusok, mint például az Apriori. A 7.12. ábra azt szemlélteti, hogy hogyan alakíthatjuk át gráfok egy halmazát a vele ekvivalens bevásárlókosár reprezentációba. Ebben az l(e) élcímkék és a hozzájuk tartozó (l( v i ) és l( v j )) csúcscímkék minden kombinációját egy ``termékre'' képezzük le. A ``tranzakció'' szélességét a gráfban lévő élek száma adja meg. Egyszerűsége ellenére ez a megközelítés csak akkor működik, ha egy gráfban minden élhez a csúcs- és élcímkék egy egyedi kombinációja tartozik. Más esetben a gráfok nem modellezhetőek teljes pontossággal ebben a reprezentációban.

7.12. ábra - Gráfszerkezetek egy halmazának leképezése bevásárlókosár tranzakciókra

Gráfszerkezetek egy halmazának leképezése bevásárlókosár tranzakciókra

A gyakori részgráf bányászati algoritmus általános felépítése

A következő lépésekből áll egy gyakori részgráfok bányászatára szolgáló Apriori-szerű algoritmus:

  1. Jelöltgenerálás, amely során gyakori (k1) -részgráfok párjait egyesítjük, hogy így k -részgráf jelölteket kapjunk.

  2. A jelöltek nyesése, amely során elvetjük az összes olyan k -részgráf jelöltet, amelyek nem gyakori (k1) -részgráfokat tartalmaznak.

  3. A támogatottságok kiszámítása, amely során minden jelöltre megszámoljuk az olyan G -beli gráfokat, amelyek tartalmazzák azt.

  4. A jelöltek eltávolítása, amely során elvetjük az összes olyan részgráf jelölet, melyek támogatottsága nem éri el minsup értékét.

A szakasz további részében ezen lépések jellegzetes részleteit fejtjük ki.

Jelöltgenerálás

A jelöltek generálása során két gyakori (k1) -részgráfot egyesítünk, egy k -részgráf jelöltet létrehozva így. Az első kérdés azzal kapcsolatban merül fel, hogy hogyan definiáljuk k -t, a részgráfok méretét. A 7.11. ábrán látható példában k a gráf csúcsainak számát jelenti. Csúcsnövelésnek (vertex growing) nevezik azt a módszert, amelynél egy további csúcs hozzáadásával iteratív módon bővítjük a részgráfokat. Jelentheti azonban k a gráf éleinek számát is. Élnövelésnek (edge growing) nevezik azt a megközelítést, amelynél egy további élt adunk hozzá a meglévő részgráfokhoz.

Jelöltek többszöri generálásának elkerülése érdekében megadhatjuk továbbá azt a feltételt is az egyesítéshez, hogy a két (k1) -részgráfnak rendelkeznie kell egy közös (k2) -részgráffal. Ezt a közös (k2) -részgráfot a gráfok magjának nevezzük. A továbbiakban röviden ismertetjük a jelöltek generálásának folyamatát a csúcsnöveléses és élnöveléses stratégiák esetére is.

Jelöltgenerálás csúcsnöveléssel

A csúcsnövelés az a folyamat, amely során úgy generálunk egy új jelöltet, hogy egy új csúcsot adunk hozzá egy meglévő gyakori részgráfhoz. A megközelítés leírása előtt tekintsük először a gráfok szomszédsági mátrix reprezentációját. A mátrix egy M(i,j) eleme vagy a v i és v j csúcsok közötti él címkéjét tartalmazza, vagy pedig a nullát, ha nincs közöttük él. A csúcsnöveléses megközelítést tekinthetjük úgy, mint egy k×k méretű szomszédsági mátrix létrehozását két (k1)×(k1) méretű szomszédsági mátrix kombinálásával, ahogy az a 7.13. ábrán látható. A G1 és G2 két olyan gráf, melyek szomszédsági mátrixai M(G1) és M(G2) . A gráfok magját az ábrán szaggatott vonal jelöli.

7.13. ábra - Csúcsnöveléses stratégia

Csúcsnöveléses stratégia

A következőekben a csúcsnöveléses jelöltgeneráló eljárást mutatjuk be.

Csúcsnöveléses részgráf egyesítő eljárás

Egy M (1) szomszédsági mátrixot akkor egyesítünk egy másik, M (2) mátrixszal, ha az utolsó soruk és utolsó oszlopuk eltávolításával kapott almátrixaik megegyeznek Az eredmény az M (1) mátrix, amelyhez hozzáadódik M (2) utolsó sora és utolsó oszlopa. Az új mátrix fennmaradó elemei vagy nullák, vagy pedig a csúcspárt összekötő összes érvényes csúcscímke kerül a helyükre.

Az így kapott gráfban egy vagy két éllel van több, mint az eredeti gráfban. A 7.13. ábrán G1 és G2 is négy csúcsot és négy élt tartalmaz. Az egyesítésükkel létrejövő G3 gráf öt csúcsot tartalmaz. A G3 éleinek száma attól függ, hogy a d és e csúcsok össze vannak-e kötve. Ha d és e nincsenek összekötve, akkor G3 -ban öt él van, a hozzájuk tartozó (d,e) mátrixelem pedig nulla. Ellenkező esetben viszont G3 -ban hat él van, a (d,e) -hez tartozó mátrixelem értéke pedig az újonnan létrehozott él címkéje. Mivel ez az élcímke ismeretlen, (d,e) -hez minden lehetséges élcímkét számba kell vennünk, így a részgráf jelöltek száma lényegesen megnő.

Jelöltgenerálás élnöveléssel

Élnövelés alkalmazásakor a jelöltek generálása során egy új élt szúrunk be egy meglévő gyakori részgráfba. A csúcsnöveléssel ellentétben az eredményül kapott részgráfban nem feltétlenül nagyobb a csúcsok száma az eredeti gráfhoz képest. A 7.14. ábrán két lehetséges részgráf jelölt látható, amelyeket G1 és G2 egyesítésével kaptunk az élnöveléses stratégiát alkalmazva. Az első részgráf jelölt, G3 , egy további csúcsot tartalmaz, míg a második részgráf jelöltben, G4 -ben, ugyanannyi csúcs van, mint az eredeti gráfokban. Az ábrán szaggatott vonal jelöli a gráfok magját.

7.14. ábra - Élnöveléses stratégia

Élnöveléses stratégia

A következőképpen foglalhatjuk össze az élnöveléses részgráf jelölt generáló eljárást.

Élnöveléses részgráf egyesítő eljárás

Egy g (1) gyakori részgráfot csak akkor egyesítünk egy másik, g (2) gyakori részgráffal, ha a g (1) -ből egy él eltávolításával kapott részgráf topológiailag ekvivalens a g (2) -ből egy él eltávolításával kapott részgráffal. Az egyesítés után eredményül kapott jelölt a g (1) részgráf, amelyhez hozzáadódik az extra él g (2) -ből.

Az egyesítendő gráfok számos topológiailag ekvivalens csúcsot tartalmazhatnak. A topológiailag ekvivalens csúcsok fogalmának szemléltetéséhez tekintsük a 7.15. ábrán látható gráfokat. A G1 gráf négy azonos, ``a'' címkéjű csúcsot tartalmaz. Ha a négy csúcs bármelyikéhez egy új élt kapcsolunk hozzá, akkor az így kapott gráfok azonosak lesznek. A G1 csúcsai így topológiailag ekvivalensek egymással.

7.15. ábra - Topológiailag ekvivalens csúcsok szemléltetése

Topológiailag ekvivalens csúcsok szemléltetése

A G2 gráfban két topológiailag ekvivalens csúcspár van, v 1 és v 4 , illetve v 2 és v 3 , annak ellenére, hogy a csúcsok és élek címkéi megegyeznek. Könnyen látható, hogy v 1 topológiailag nem ekvivalens v 2 -vel, mert nem egyezik meg a csúcsokban végződő élek száma. Így ha egy új élt kapcsolunk v 1 -hez, akkor nem ugyanazt a gráfot kapjuk, mint ha ugyanazt az élt v 2 -höz csatolnánk. Ugyanakkor a G3 gráfnak nincsenek topológiailag ekvivalens csúcsai. Noha a v 1 és v 4 csúcsoknak megegyezik a csúcscímkéje és ugyanannyi él végződik bennük, más gráfot kapunk akkor, ha v 1 -hez kapcsolunk egy új élt, mint akkor, ha ugyanazt az élt v 4 -hez kapcsolnánk.

7.16. ábra - Általános módszer két részgráf élnöveléssel történő egyesítésére

Általános módszer két részgráf élnöveléssel történő egyesítésére

A topológiailag ekvivalens csúcsok fogalmán keresztül könnyebben megérthető, hogy miért generálható több részgráf jelölt az élnövelés során. Tekintsük a 7.16. ábrán látható (k1) -részgráfokat, G1 -et és G2 -t. A jelölés egyszerűsítése végett a két gráf k2 közös élt tartalmazó magját egy téglalappal ábrázoljuk. A G1 fennmaradó, nem a magba tartozó élét egy az a és b csúcsokat összekötő, ``lengő'' éllel jelöljük. A G2 fennmaradó, nem a magba tartozó élét is hasonlóan, egy a c és d csúcsokat összekötő ``lengő'' éllel ábrázoljuk. Bár a G1 és G2 gráfok magjai megegyeznek, az is előfordulhat, hogy a és c topológiailag ekvivalensek, és az is, hogy nem. Ha a és c topológiailag ekvivalensek, akkor a=c módon jelöljük őket. A magon kívüli csúcsok esetén a b=d jelölést használjuk, ha a címkéik megegyeznek.

7.17. ábra - Élnöveléssel generált részgráf jelöltek

Élnöveléssel generált részgráf jelöltek

A következő hozzávetőleges szabályok segítségével határozhatjuk meg a jelöltgenerálás során kapott részgráf jelölteket:

  1. Ha ac és bd , akkor egyetlen részgráf kapható eredményül, amint az a 7.17. (a) ábrán látható.

  2. Ha a=c de bd , akkor két lehetséges részgráf kapható eredményül, amint az a 7.17. (b) ábrán látható.

  3. Ha ac de b=d , akkor két lehetséges részgráf kapható eredményül, amint az a 7.17. (c) ábrán látható.

  4. Ha a=c és b=d , akkor három lehetséges részgráf kapható eredményül, amint az a 7.17. (d) ábrán látható.

Több részgráf generálható akkor is, ha egynél több mag társítható a két (k1) -részgráfhoz, ahogy az a 7.18. ábrán is látható. A sötét színnel jelölt csúcsok azok, amelyek élei magot alkotnak az egyesítési művelet során. Minden egyes mag más részgráf jelöltekhez vezethet. Ha két gyakori (k1) -részgráfot egyesítünk, akkor legfeljebb k2 lehetséges mag létezhet elméletileg, melyek mindegyikét úgy kapjuk, hogy valamelyik gráfból eltávolítunk egy élt. Noha az élnöveléses módszer több részgráf jelöltet is előállíthat, a részgráf jelöltek száma általában még így is kisebb, mint a csúcsnöveléses stratégiával előállítottak száma.

7.18. ábra - A jelöltek multiplicitása a jelöltgenerálás során

A jelöltek multiplicitása a jelöltgenerálás során

A jelöltek nyesése

Miután generáltuk a k -részgráf jelölteket, le kell nyesnünk azokat, amelyek (k1) -részgráfjai nem gyakoriak. A nyesés lépését elvégezhetjük úgy, hogy a k -részgráf jelöltből egymás után eltávolítjuk az éleket, és ellenőrizzük, hogy az így kapott (k1) -részgráfok gyakoriak-e. Ha nem, akkor az adott k -részgráfot elvethetjük.

A (k1) -részgráfok gyakoriságának vizsgálatához össze kell hasonlítanunk azokat más gyakori (k1) -részgráfokkal. Annak meghatározását, hogy két gráf topológiailag ekvivalens-e (vagy izomorf-e), gráfizomorfizmus problémának nevezzük. Hogy a gráfizomorfizmus probléma megoldásának nehézségét érzékeltessük, tekintsük a 7.19. ábrát. Bár a két gráf különbözőnek látszik, valójában izomorfak, mert kölcsönösen egyértelműen feleltethetők meg egymásnak a két gráf csúcsai.

7.19. ábra - Gráfizomorfizmus

Gráfizomorfizmus

A gráfizomorfizmus kezelése

A gráfizomorfizmus kezelésének egyik standard módszere, hogy mindkét gráfot egy egyedi sztring reprezentációra képezünk le, amelyet kódnak vagy kanonikus címkének nevezünk. A kanonikus címkék rendelkeznek azzal a tulajdonsággal, hogy ha két gráf izomorf, akkor kódjaik is megegyeznek. Ez a tulajdonság lehetővé teszi, hogy a kanonikus címkéik összehasonlításával ellenőrizzük gráfok izomorfizmusát.

7.20. ábra - Egy gráf szomszédsági mátrix reprezentációja

Egy gráf szomszédsági mátrix reprezentációja

Az első lépés egy gráf kanonikus címkéjének megszerkesztéséhez a gráf szomszédsági mátrix reprezentációjának előállítása. A 7.20. ábrán egy ilyen mátrixra láthatunk példát, amely a megadott gráfhoz tartozik. Elméletben egy gráfnak több szomszédsági mátrix reprezentációja is lehet, mert a csúcsokat a szomszédsági mátrixban többféleképpen is sorba rendezhetjük. A 7.20. ábrán látható példában az első sor és oszlop az a csúcshoz tartozik, melynek 3 éle van, a második sor és oszlop egy másik a csúcshoz tartozik, melynek 2 éle van, és így tovább. Ahhoz, hogy kinyerjük egy gráf összes szomszédsági mátrix reprezentációját, tekintenünk kell a mátrix sorainak (és a hozzájuk tartozó oszlopoknak) az összes lehetséges permutációját.

Matematikai értelemben minden permutáció a kezdeti szomszédsági mátrix és egy megfelelő permutációs mátrix szorzatához tartozik, mint ahogy a következő példa is mutatja.

7.3. Példa.

Tekintsük a következő mátrixot:

M=( 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ).

A következő permutációs mátrixot használhatjuk M első sorának (és oszlopának) és harmadik sorának (és oszlopának) cseréjére:

P 13 =( 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 ),

ahol P 13 -at úgy kapjuk, hogy megcseréljük az egységmátrix első és harmadik sorát. Az első és harmadik sor (és oszlop) megcseréléséhez a permutációs mátrixot megszorozzuk M -mel:

M'= P 13 T ×M× P 13 =( 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16 ).

Figyeljük meg, hogy ha jobbról szorozzuk M -et P 13 -mal, akkor M első és harmadik oszlopa cserélődik fel, míg ha balról szorozzuk M -et P 13 T -tal, akkor M első és harmadik sora. Ha mindhárom mátrixot összeszorozzuk, akkor az M' mátrixot kapjuk, amelynek az első és harmadik sora, illetve oszlopa cserélődik fel.

7.21. ábra - Szomszédsági mátrixok sztring reprezentációja

Szomszédsági mátrixok sztring reprezentációja

A második lépés a sztring reprezentáció meghatározása minden egyes szomszédsági mátrixhoz. Mivel a szomszédsági mátrix szimmetrikus, elég, ha a mátrix felső háromszög részére alapozva készítjük el a sztring reprezentációt. A 7.21. ábrán látható példában a kódot úgy kapjuk meg, hogy oszloponként összefűzzük a felső háromszögmátrix elemeit. Az utolsó lépésben összehasonlítjuk a gráf összes sztring reprezentációját, és kiválasztjuk közülük azt, amelyiknek a legkisebb (vagy a legnagyobb) a lexikografikus értéke.

Az előbb tárgyalt megközelítés költségesnek tűnhet, mivel a kanonikus címke megtalálásához meg kell vizsgálnunk a gráf összes lehetséges szomszédsági mátrixát, és mindnek ki kell számítanunk a sztring reprezentációját. Konkrétan, k! számú permutációt kell tekintenünk minden egyes k csúcsból álló gráfra. A feladat bonyolultságának csökkentésére kidolgozott módszerek közé tartozik a korábban kiszámított kanonikus címke gyorsítótárazása (így nem kell azt újra kiszámítanunk, amikor ugyanazon gráfon végezzük a izomorfizmus vizsgálatát), és a kanonikus címke meghatározásához szükséges permutációk számának csökkentése olyan további információk bevonásával, mint például a csúcsok címkéi és foka. Az utóbbi megközelítés túlmutat a könyv által tárgyalt témákon, de az érdeklődő Olvasó figyelmébe ajánljuk a fejezet végén található irodalmi megjegyzéseket.

A támogatottság kiszámítása

A támogatottság kiszámítása is költséges művelet lehet, mert meg kell határoznunk minden részgráf jelöltet, amelyet a GG gráf tartalmaz. Ezt a műveletet például úgy gyorsíthatjuk fel, hogy egy listát tartunk fenn, amely az egyes gyakori (k1) -részgráfokhoz tartozó gráfazonosítókat tartalmazza. Amikor két (k1) -részgráf egyesítésével egy új k -részgráf jelöltet generálunk, a két gráfhoz tartozó azonosítólisták metszetét vesszük. Végül, a részgráfok izomorfizmusának vizsgálatát a metszetlistában lévő gráfokon végezzük el, hogy meghatározzuk, tartalmaznak-e egy adott részgráf jelöltet.