Praktický heuristický isomorfismus grafů

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Praktický heuristický isomorfismus grafů DIPLOMOVÁ PRÁCE

Bc. Ondřej Borek

BRNO, 2014

Prohlášení Prohlašuji, že tato diplomová práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Poděkování Děkuji především vedoucímu práce doc. RNDr. Petru Hliněnému, Ph.D. za konzultace, odbornou pomoc a rychlé odpovědi na otázky. Také děkuji všem, kteří mě podporovali.

Shrnutí V diplomové práci je navržen a popsán algoritmus na řešení problému isomorfismu grafů založený na pohledech na graf. Algoritmus je rozdělen do verzí, podle toho jak se vyvíjel a verze jsou vzájemně porovnány. Nejrychlejší verze je poté srovnávána s algoritmem programu Nauty. Testovací data pro srovnání jsou rozdělena do čtyř kategorií: asymetrické isomorfní grafy, asymetrické neisomorfní grafy, vrcholově tranzitivní isomorfní grafy a vrcholově tranzitivní neisomorfní grafy.

Klíčová slova hledání isomorfismu, Cayleyho graf, Nauty

OBSAH 1. ÚVOD 2. POJMY 3. ALGORITMY PRO ŘEŠENÍ ISOMORFISMU GRAFŮ 3.1. ALGORITMUS ZALOŽENÝ NA POHLEDECH NA GRAF 3.1.1. Základní koncept algoritmu 3.1.2. První změna algoritmu – tvar podpohledu 3.1.3. Druhá změna algoritmu – zohlednění spojení uzlů při tvorbě permutace 3.1.4. Třetí změna algoritmu – zjemnění rozkladu uzlů při tvorbě permutace 3.2. ALGORITMUS V PROGRAMU NAUTY 4. POROVNÁNÍ ALGORITMŮ 4.1. VÝBĚR NEJRYCHLEJŠÍ VERZE ALGORITMU ZALOŽENÉHO NA POHLEDECH NA GRAF 4.1.1. Základní koncept algoritmu 4.1.2. První změna algoritmu – tvar podpohledu 4.1.3. Druhá změna algoritmu – zohlednění spojení uzlů při tvorbě permutace 4.1.4. Třetí změna algoritmu – zjemnění rozkladu uzlů při tvorbě permutace 4.1.5. Výběr nejrychlejší verze algoritmu 4.2. POROVNÁNÍ ALGORITMU ZALOŽENÉHO NA POHLEDECH NA GRAF S PROGRAMEM NAUTY 4.2.1. Porovnání pro asymetrické isomorfní grafy 4.2.2. Porovnání pro asymetrické neisomorfní grafy 4.2.3. Porovnání pro vrcholově tranzitivní isomorfní grafy 4.2.4. Porovnání pro vrcholově tranzitivní neisomorfní grafy 5. ZÁVĚR PŘÍLOHA A: NAUTY - ASYMETRICKÉ ISOMORFNÍ GRAFY PŘÍLOHA B: POHLEDY NA GRAF - ASYMETRICKÉ ISOMORFNÍ GRAFY PŘÍLOHA C: NAUTY - ASYMETRICKÉ NEISOMORFNÍ GRAFY PŘÍLOHA D: POHLEDY NA GRAF - ASYMETRICKÉ NEISOMORFNÍ GRAFY PŘÍLOHA E: NAUTY - VRCHOLOVĚ TRANZITIVNÍ ISOMORFNÍ GRAFY PŘÍLOHA F: POHLEDY NA GRAF - VRCHOLOVĚ TRANZITIVNÍ ISOMORFNÍ GRAFY PŘÍLOHA G: NAUTY - VRCHOLOVĚ TRANZITIVNÍ NEISOMORFNÍ GRAFY PŘÍLOHA H: POHLEDY NA GRAF - VRCHOLOVĚ TRANZITIVNÍ NEISOMORFNÍ GRAFY

3 4 5 8 8 13 16 22 26 27 28 28 32 35 39 42 43 44 48 50 54 58 60 61 62 63 64 66 68 69

SEZNAM OBRÁZKŮ Obr: 3-1 Graf a pohled na graf ...................................................................................................5 Obr: 3-2 Graf a pohledy na něj...................................................................................................9 Obr: 3-3 Pohled na graf a podpohled........................................................................................14 Obr: 4-1 Základní koncept - asymetrické isomorfní grafy .......................................................29 Obr: 4-2 Základní koncept – asymetrické neisomorfní grafy...................................................30 Obr: 4-3 Základní koncept – vrcholově tranzitivní neisomorfní grafy ....................................31 Obr: 4-4 První změna algoritmu – asymetrické isomorfní grafy..............................................32 Obr: 4-5 První změna algoritmu – asymetrické neisomorfní grafy..........................................33

1

Obr: 4-6 První změna algoritmu – vrcholově tranzitivní isomorfní grafy ...............................34 Obr: 4-7 První změna algoritmu – vrcholově tranzitivní neisomorfní grafy............................35 Obr: 4-8 Druhá změna algoritmu – asymetrické isomorfní grafy ............................................36 Obr: 4-9 Druhá změna algoritmu – asymetrické neisomorfní grafy ........................................37 Obr: 4-10 Druhá změna algoritmu – vrcholově tranzitivní isomorfní grafy ............................38 Obr: 4-11 Druhá změna algoritmu – vrcholově tranzitivní neisomorfní grafy ........................39 Obr: 4-12 Třetí změna algoritmu – asymetrické isomorfní grafy ............................................40 Obr: 4-13 Třetí změna algoritmu – asymetrické neisomorfní grafy.........................................41 Obr: 4-14 Třetí změna algoritmu – vrcholově tranzitivní isomorfní grafy ..............................41 Obr: 4-15 Třetí změna algoritmu – vrcholově tranzitivní neisomorfní grafy...........................42 Obr: 4-16 Nauty – doba odezvy pro asymetrické isomorfní grafy...........................................44 Obr: 4-17 Pohledy na graf - doba odezvy pro asymetrické isomorfní grafy............................45 Obr: 4-18 Nauty – relativní prodlužování doby odezvy na asymetrických isomorfních grafech ..........................................................................................................................................46 Obr: 4-19 Pohledy na graf – relativní prodlužování doby odezvy na asymetrických isomorfních grafech..........................................................................................................47 Obr: 4-20 Nauty – doba odezvy pro asymetrické neisomorfní grafy .......................................48 Obr: 4-21 Pohledy na graf - doba odezvy pro asymetrické neisomorfní grafy ........................48 Obr: 4-22 Nauty – relativní prodlužování doby odezvy na asymetrických neisomorfních grafech ..............................................................................................................................49 Obr: 4-23 Pohledy na graf – relativní prodlužování doby odezvy na asymetrických neisomorfních grafech ......................................................................................................50 Obr: 4-24 Nauty – doba odezvy pro vrcholově tranzitivní isomorfní grafy.............................51 Obr: 4-25 Pohledy na graf - doba odezvy pro vrcholově tranzitivní isomorfní grafy..............51 Obr: 4-26 Nauty – relativní prodlužování doby odezvy na vrcholově tranzitivních isomorfních grafech ..............................................................................................................................52 Obr: 4-27 Pohledy na graf – relativní prodlužování doby odezvy na vrcholově tranzitivních isomorfních grafech..........................................................................................................53 Obr: 4-28 Nauty – doba odezvy pro vrcholově tranzitivní neisomorfní grafy.........................54 Obr: 4-29 Pohledy na graf - doba odezvy pro vrcholově tranzitivní neisomorfní grafy ..........55 Obr: 4-30 Nauty – relativní prodlužování doby odezvy na vrcholově tranzitivních neisomorfních grafech ......................................................................................................56 Obr: 4-31 Pohledy na graf – relativní prodlužování doby odezvy na vrcholově tranzitivních neisomorfních grafech ......................................................................................................57

2

1. ÚVOD Graf je matematická struktura umožňující vizuálně zachytit podobu různých sítí. Díváme-li se na systém jako na množinu prvků a vazeb mezi těmito prvky, je graf ideální pro vizuální popis systémů. Grafem se dá modelovat počítačová síť, sociální síť zachycující kdo koho zná nebo třeba součástky nějakého stroje, kde vztah mezi součástkami spočívá v tom, jestli jsou spojeny jedna s druhou. Graf můžeme chápat jako zjednodušený model jakékoliv sítě nebo systému. U objektů, které jdou převést na graf, můžeme testovat, zda se jedná o stejné objekty pomocí algoritmu na řešení problému isomorfismu grafů. Grafy se hodně používají v chemii a biologii například na zachycení informace, které látky spolu reagují, na zachycení potravních řetězců nebo třeba neuronové sítě se synaptickými spojeními mezi neurony. Také struktura DNA a RNA se dá zachytit grafem a někdy je třeba zjistit, zda dva grafy zachycující strukturu RNA nebo DNA jsou ze stejného organismu, neboli vyřešit problém isomorfismu těchto grafů. Dále se problém isomorfismu grafů řeší při navrhování elektrických obvodů nebo při zjišťování chemických směsí v rámci chemické databáze. Tyto sítě z oblasti molekulární biologie nebo chemie jsou typicky dost rozsáhlé a vyřešit problém isomorfismu pro dvě takové sítě může být výpočetně dost náročné. Člověk takový problém nezvládne vyřešit bez pomoci strojů a i když se počítačová věda rychle vyvíjí, sítě mohou mít tak obrovský počet uzlů, že tento výpočet může trvat dlouho i velmi výkonným počítačům. Proto jsou vymýšleny různé způsoby, jak algoritmus na řešení problému isomorfismu grafů zlepšit a výpočet urychlit. V praxi se proto používají různé heuristické přístupy. Takový heuristický přístup ale často bývá na úkor obecnosti algoritmu. To znamená, že algoritmus je rychlejší jen na nějaké třídě grafů a ne pro jakékoliv grafy. Jeden takový známý heuristický přístup pochází už z roku 1976 a jeho autorem je Julian R Ullmann. Tento přístup funguje pro hledání isomorfních podgrafů. To znamená pro rozhodnutí, zda jeden zadaný graf obsahuje podgraf isomorfní druhému zadanému grafu. Metoda navržená Ullmannem používá rekurzivní zpětné vyhledávání. Od té doby vzniklo mnoho úprav a optimalizací této metody. Další možnost, jak řešit isomorfismus grafů, je pomocí převádění grafů na kanonický tvar. To používá v současnosti nejrychlejší program na řešení isomorfismu grafů Nauty. Pokud lze s nějakou složitostí převést graf na kanonický tvar, pak lze se stejnou složitostí řešit isomorfismus grafů. Ale neví se, jestli toto tvrzení platí opačně, to znamená, že pokud s nějakou složitostí umíme vyřešit isomorfismus dvou grafů, pak umíme se stejnou složitostí převést graf na kanonický tvar. Téma isomorfismu grafů je stále široce zkoumáno a aktuální.

3

2. POJMY Obyčejný graf = jednoduchý neorientovaný graf - uspořádaná dvojice, kde první složka je množina vrcholů a druhá složka je množina hran spojující vrcholy. Jedna hrana spojuje právě dva různé vrcholy a mezi dvěma vrcholy buď není hrana vůbec, nebo je zde nanejvýš jedna. Souvislý graf = graf, v němž platí, že pro každé dva vrcholy existuje alespoň jedna cesta spojující tyto vrcholy. Orientovaný graf = graf, jehož všechny hrany jsou reprezentované jako uspořádané dvojice uzlů (na rozdíl od neorientovaného grafu, jehož hrany jsou reprezentované jako dvouprvkové množiny uzlů). Samotným pojmem graf se v této práci rozumí vždy obyčejný souvislý graf (nebude-li v daném místě dokumentu řečeno jinak). Stupeň vrcholu = počet hran vycházejících z vrcholu. Isomorfismus grafů G a H = vzájemně jednoznačné zobrazení f: V(G)->V(H), pro které platí, že každá dvojice vrcholů u,v z V(G) je spojena hranou právě tehdy, když je spojena hranou i dvojice vrcholů f(u), f(v) z V(H). Dva grafy jsou isomorfní, existuje-li mezi nimi isomorfismus. Poznámka: Intuitivně - isomorfní grafy jsou grafy stejného tvaru – iso = stejný, morph = tvar. Automorfismus grafu = isomorfismus grafu sama na sebe. Vrcholově tranzitivní graf – pro libovolnou dvojici vrcholů existuje automorfismus. Poznámka: rozklad vrcholů vrcholově tranzitivního grafu podle automorfismu obsahuje pouze jednu třídu (která obsahuje všechny vrcholy grafu). Asymetrický graf = má jen jeden automorfismus, a to identitu. Poznámka: všechny třídy rozkladu vrcholů asymetrického grafu jsou jednoprvkové množiny. Cayleyho graf = graf realizovaný nad grupou (M,*). Realizace Cayleyho grafu: mějme množinu uzlů budoucího grafu {uzel(i)| i=1, 2, ..., |M|}, mějme množinu generator = {g(j)| g(j) je prvkem M}, potom pro lib i, j z množiny{1, 2, ... , N} jsou uzel(i) a uzel(j) spojené hranou právě tehdy, když existuje g(k) takové, že m(i) = m(j)*g(k). Poznámka: Cayleyho graf je vrcholově tranzitivní. Hustota grafu = <počet hran grafu>/<maximální možný počet hran grafu o stejném počtu uzlů>.

4

3. ALGORITMY PRO ŘEŠENÍ ISOMORFISMU GRAFŮ Pro řešení isomorfismu grafů jsem postupně v krocích navrhl algoritmus založený na pohledech na graf (pojem pohled na graf je definovaný dále). Intuitivně jsem přitom vycházel z myšlenky, že isomorfní grafy jsou takové grafy, které se z odpovídajících pohledů jeví stejně (isomorfní grafy jsou grafy stejného tvaru).

Pojmy použité v této kapitole Výchozí uzel pohledu = jeden konkrétní uzel pozorovaného grafu. Je to výchozí uzel pohledu na daný graf – viz dále pohled na graf. Pohled na graf = orientovaný graf vzniklý z pozorovaného grafu. Při tvorbě pohledu na graf se nejprve vybere jeden z uzlů pozorovaného grafu jako výchozí uzel pohledu. Poté se pro každý zbývající uzel zorientují hrany na všech nejkratších cestách vedoucích z uzlu pohledu do daného uzlu. Přitom se hrany zorientují ve směru od uzlu pohledu. Zbývající hrany (které neleží na žádné nejkratší cestě) se zorientují obousměrně. Poznámka: každá obousměrná hrana spojuje vždy dva uzly stejně vzdálené od uzlu pohledu. Na následujícím obrázku je graf a jeden pohled na tento graf.

Obr: 3-1 Graf a pohled na graf

V levé části obrázku je graf. V pravé části obrázku je pohled na tento graf. Výchozím uzlem pohledu je uzel 1. Hrana (1,2) získala jednosměrnou orientaci, protože je na nejkratší cestě z výchozího uzlu pohledu do uzlu 2. Hrana (1,3) získala jednosměrnou orientaci, protože je na nejkratší cestě z výchozího uzlu pohledu do uzlu 3. Hrana (2,3) získala obousměrnou orientaci, protože není na žádné nejkratší cestě z výchozího uzlu pohledu do žádného ze zbývajících uzlů. Porovnatelná veličina = veličina, u jejíchž libovolných dvou hodnot hodnota1 a hodnota2 lze jednoznačně rozhodnout, která z následujících variant platí: -

hodnota1 = hodnota2,

-

hodnota1 > hodnota2,

-

hodnota1 < hodnota2.

Poznámka: hodnoty porovnatelné veličiny lze snadno a rychle uspořádat - například uložením do binárního stromu. Kanonický tvar objektu = jednoznačná reprezentace objektu. Dva isomorfní objekty mají shodný kanonický tvar.

5

Spektrum = udává pro každou hodnotu míru jejího zastoupení. Je to množina uspořádaných dvojic, kde první složka udává hodnotu veličiny a druhá složka udává počet výskytů této hodnoty. V této práci pod pojmem spektrum máme na mysli uspořádané spektrum. Spektrum = uspořádaná množina ({(hodnota, počet výskytů)}, operace porovnání hodnot <). Spektrum = ((hodnota1, pocetVyskytu1), (hodnota2, pocetVyskytu2), ..., (hodnotaN, pocetVyskytuN)), přičemž pro všechna i, j z {1, 2, ..., N} platí: pokud i < j potom hodnotai < hodnotaj. Rozklad množiny = množina neprázdných podmnožin takových, že každý prvek původní množiny je obsažený přesně v jedné podmnožině. Tyto podmnožiny se nazývají třídy. V této práci pod pojmem rozklad máme na mysli uspořádaný rozklad. Rozklad = ({(idTridy, {prvky tridy})}, operace porovnání idTridy <). Rozklad ((idTridy1, mnozinaPrvkuTridy1), (idTridyN, mnozinaPrvkuTridyN)).

(idTridy2,

mnozinaPrvkuTridy2),

...,

Pro všechna i, j z {1, 2, ..., N} platí: pokud i < j, potom idTridyi < idTridyj.

Algoritmus vložení hodnoty do spektra Vstup: hodnota = hodnota vkládaná do spektra. Výstup: ve spektru je započítaná nová hodnota. pokud spektrum obsahuje hodnotu hodnota - tj. existuje prvek (hodnotai, pocetVyskytui) takový, že hodnotai = hodnota, potom zvýšit počet výskytů o jedna: (hodnotai, pocetVyskytui) := (hodnotai, pocetVyskytui + 1), jinak zařadit na správnou pozici j dvojici (hodnota, 1) tak, že: hodnotaj-1 < hodnota a současně hodnota < hodnotaj+1.

Algoritmus porovnání spekter (s1, s2) Vstup: -

s1 = spektrum,

-

s2 = spektrum.

Výstup: -

kladné číslo - pokud s1 > s2,

-

0 - pokud s1 = s2,

-

záporné číslo – pokud s1 < s2.

pokud Porovnání čísel(s1.pocetHodnot, s2. pocetHodnot) <> 0, potom vrátit Porovnání čísel(s1. pocetHodnot, s2. pocetHodnot), pro každé i = 1, 2, ..., s1. pocetHodnot pokud operacePorovnaniHodnot(s1.hodnotai, s2.hodnotai) <> 0, potom vrátit operacePorovnaniHodnot(s1.hodnotai, s2.hodnotai); pokud Porovnání čísel(s1. pocetVyskytui, s2. pocetVyskytui) <> 0, potom vrátit Porovnání čísel(s1. pocetVyskytui, s2. pocetVyskytui);

6

konec pro každé i; vrátit 0.

Algoritmus zatřídění prvku do třídy rozkladu Vstupy: -

idTridy = identifikátor třídy, do které se má přidat prvek,

-

prvekTridy = prvek přidávaný do třídy rozkladu.

pokud spektrum obsahuje třídu s identifikátorem idTridy - tj. existuje prvek (idTridyi, mnozinaPrvkuTridyi) takový, že idTridyi = idTridy, potom přidat prvek do třídy (idTridyi, mnozinaPrvkuTridyi) := (idTridyi, mnozinaPrvkuTridyi sjednoceno s {prvekTridy}), jinak zařadit na správnou pozici j dvojici (idTridy, {prvekTridy}) tak, že: idTridyj-1 < idTridy a současně idTridy < idTridyj+1.

Algoritmus porovnání rozkladů (r1, r2) Vstup: -

r1 = rozklad,

-

r2 = rozklad.

Výstup: -

kladné číslo - pokud r1 > r2,

-

0 - pokud r1 = r2,

-

záporné číslo – pokud r1 < r2.

pokud Porovnání čísel(r1.pocetTrid, r2. pocetTrid) <> 0, potom vrátit Porovnání čísel(r1. pocetTrid, r2. pocetTrid), pro každé i = 1, 2, ..., r1. pocetTrid pokud operacePorovnaniIdTridy(r1.idTridyi, r2. idTridyi) <> 0, potom vrátit operacePorovnaniIdTridy(r1. idTridyi, r2. idTridyi); pokud Porovnání čísel(r1.mnozinaPrvkuTridy i.mohutnost, r2.mnozinaPrvkuTridy i.mohutnost) <> 0, potom vrátit Porovnání čísel(r1.mnozinaPrvkuTridy i.mohutnost,r2.mnozinaPrvkuTridy i.mohutnost); konec pro každé i; vrátit 0. Zbytek této kapitoly obsahuje: -

navržený algoritmus na řešení problému isomorfismu,

-

stručný popis algoritmu, který používá program Nauty při řešení problému isomorfismu.

7

3.1. ALGORITMUS ZALOŽENÝ NA POHLEDECH NA GRAF V této kapitole je popsaný a vysvětlený základní koncept algoritmu založeného na pohledech na graf včetně jeho postupných vylepšení: -

rozklad podle charakteristik pohledu – vytvoří se rozklady uzlů grafů G1 a G2 podle charakteristik pohledu (tento rozklad je blízký rozkladu podle automorfismu, tj. na orbity grupy automorfismů). Nad rozklady se poté hledá isomorfismus hrubou silou. Tento algoritmus je pomalý v případě vrcholově tranzitivních grafů, u kterých uspořádaná množina tříd rozkladu uzlů grafu obsahuje pouze jednu třídu (obsahující jména všech uzlů grafu).

-

rozklad podle tvaru podpohledu a vzdálenosti od výchozího uzlu pohledu vytvoří se rozklady uzlů grafů G1 a G2 podle tvaru podpohledu a vzdálenosti od výchozího uzlu pohledu. Nad rozklady se poté hledá isomorfismus hrubou silou. Tento algoritmus není dostatečně rychlý v případě vrcholově tranzitivních grafů výsledný rozklad uzlů pohledu je sice jemnější, než rozklad uzlů grafu pomocí charakteristik pohledů, avšak mohutnost některých tříd je přesto veliká.

-

zohlednění pole spojení uzlů při tvorbě permutace - vytvoří se rozklady uzlů grafů G1 a G2 podle tvaru podpohledu a vzdálenosti od výchozího uzlu pohledu. Při hledání isomorfismu nad rozklady se zohledňují vazby mezi uzly. Vyhledání isomorfismu nad rozklady se podstatně zrychlilo, ale není dostatečně rychlé v případě hustých vrcholově tranzitivních grafů.

-

zjemnění rozkladu uzlů podle spektra spojení s ostatními třídami řezu - vytvoří se rozklady uzlů grafů G1 a G2 podle tvaru podpohledu a vzdálenosti od výchozího uzlu pohledu. Tyto rozklady se v případě potřeby zjemňují podle spektra spojení uzlu s uzly ostatních tříd stejného řezu pohledu. Při hledání isomorfismu nad rozklady se zohledňují vazby mezi uzly.

V následujících podkapitolách je popsaný základní koncept algoritmu a jeho jednotlivé změny.

3.1.1. Základní koncept algoritmu Základní koncept algoritmu využívá morfologických charakteristik pohledu na graf – viz dále definice pojmu charakteristika pohledu na graf. Intuitivně charakteristika pohledu na graf zahrnuje hodnoty údajů charakterizující tvar pohledu na graf (v charakteristikách pohledu se nesmí vyskytovat názvy uzlů grafu).

Základní pojmy Uzly řezu J pohledu na graf = množina všech takových uzlů pohledu na graf, které mají vzdálenost J od uzlu pohledu. Konektivita uzlu = je uspřádaná trojice hodnot údajů (<počet všech sousedících uzlů>,<počet odchozích hran>,<počet příchozích hran>). Poznámka: Hodnota součtu <počet odchozích hran> + <počet příchozích hran> je větší nebo rovna hodnotě <počet všech sousedících uzlů>. Důvodem nerovnosti jsou obousměrné hrany sousedící s daným uzlem. 8

dvojic Charakteristika pohledu na graf = množina uspořádaných (, Rozklad podle konektivit (Uzly řezu J pohledu na graf) + operace Porovnání čísel(c1, c2). Význam výše uvedených pojmů je vysvětlený na následujícím příkladu.

Obr: 3-2 Graf a pohledy na něj V levé části obrázku je graf a napravo od něj jsou postupně zobrazené všechny tři pohledy na tento graf. Charakteristiky dvou pohledů na graf lze porovnat pomocí operace porovnání charakteristik pohledu (algoritmus viz dále). Lze dokázat následující větu o vztahu charakteristik pohledu a automorfismu: Nechť u a v jsou dva různé uzly prostého souvislého grafu G, P(u) a P(v) jsou dva různé pohledy na graf G a Ch(P(u)) a Ch(P(v)) jsou charakteristiky pohledů na graf G. Pokud se charakteristiky dvou pohledů na graf liší (tj. Ch(P(u)) <> Ch(P(v))), potom neexistuje automorfismus mezi výchozími uzly těchto pohledů (tj. neexistuje automorfismus A takový, že (u,v) je prvkem A). Z výše uvedené věty plyne, že každá orbita automorfismů grafu je podmnožinou některé z tříd rozkladu uzlů grafu podle charakteristik pohledu na graf. Uzly řezu 0 prvního pohledu na graf = {1} Uzly řezu 1 prvního pohledu na graf = {2; 3} Konektivita uzlu (1) prvního pohledu na graf = (2, 2, 0) Konektivita uzlu (2) prvního pohledu na graf = (2, 1, 2) Konektivita uzlu (3) prvního pohledu na graf = (2, 1, 2) Charakteristika prvního pohledu na graf = ({(0, { ((2, 2, 0), 1) }) ; (1, { ((2, 1, 2), 2) })}, porovnaniCisel) Obdobným způsobem se získají hodnoty výše uvedených veličin pro druhý a třetí pohled na graf (pohled s výchozím uzlem pohledu 2 a pohled s výchozím uzlem pohledu 3).

Algoritmus porovnání čísel (c1, c2) Vrátit (c1 – c2) Porovnání dvou čísel je realizováno pomocí jejich aritmetické rozdílu.

9

Algoritmus porovnání konektivit (k1, k2) Vstupy: -

k1 = konektivita,

-

k2 = konektivita.

Výstup: -

kladné číslo - pokud k1 > k2,

-

0 - pokud k1 = k2,

-

záporné číslo – pokud k1 < k2.

Pokud Porovnání čísel(k1.pocetSousedUzlu, k2.pocetSousedUzlu) <> 0, potom vrátit Porovnání čísel(k1.pocetSousedUzlu, k2.pocetSousedUzlu). Pokud Porovnání čísel(k1.pocetOdchozHran, k2.pocetOdchozHran) <> 0, potom vrátit Porovnání čísel(k1.pocetOdchozHran, k2.pocetOdchozHran). Pokud Porovnání čísel(k1.pocetPrichozHran, k2.pocetPrichozHran) <> 0, potom vrátit Porovnání čísel(k1.pocetPrichozHran, k2.pocetPrichozHran).

Algoritmus porovnání charakteristik pohledu (ch1, ch2) Vstupy: -

ch1 = charakteristika pohledu,

-

ch2 = charakteristika pohledu.

Výstup: -

kladné číslo - pokud ch1 > ch2,

-

0 - pokud ch1 = ch2,

-

záporné číslo – pokud ch1 < ch2.

pokud Porovnání čísel(ch1.rozkladyDleKonektivit.pocet, ch2.rozkladyDleKonektivit.pocet) <> 0, potom vrátit Porovnání čísel(ch1.rozkladyDleKonektivit.pocet, ch2.rozkladyDleKonektivit.pocet), pro každé i = 1, 2, ..., ch1.rozkladyDleKonektivit.pocet pokud Porovnání rozkladu(ch1.rozkladDleKonektiviti, ch2.rozkladDleKonektiviti)<> 0, potom vrátit Porovnání rozkladu(ch1.rozkladDleKonektiviti, ch2.rozkladDleKonektiviti); konec pro každé i; vrátit 0.

Algoritmus řešení problému isomorfismu grafů Vstupem algoritmu jsou grafy G1 a G2. Výstupem je: -

buď text „grafy G1 a G2 nejsou isomorfní“,

10

-

nebo vypsaný isomorfismus.

// porovnání rozkladů G1 a G2 podle charakteristik pohledů rozkladDleCharakteristik1 := rozkladDleCharakteristikPohledu(G1) rozkladDleCharakteristik2 := rozkladDleCharakteristikPohledu(G2) pokud rozkladDleCharakteristik1 <> rozkladDleCharakteristik2, potom vypsat „grafy G1 a G2 nejsou isomorfní“ a ukončit // vyhledání isomorfismu // argumenty jsou rozklad uzlů grafu G1 a grafu G2 podle charakteristik pohledu // rozklad uzlů grafu je uspořádaná množina tříd uzlů, přičemž každá třída // je reprezentována charakteristikou pohledu na graf isomorfismus := najdiIsomorfismusHrubouSilou(G1, G2, rozkladDleCharakteristik1, rozkladDleCharakteristik2) pokud isomorfismus <> null, potom vypsat isomorfismus a ukončit, jinak vypsat „fatální chyba – dva grafy se stejným spektrem pohledů nejsou isomorfní“ a ukončit. Součástí algoritmu jsou dvě dílčí úlohy (pro výpočet rozkladu dle charakteristik pro graf G1 a pro graf G2), jejichž algoritmus je popsaný dále.

Algoritmus vytvoření rozkladu dle charakteristik pohledů na graf Vstupem algoritmu je graf G. Výstupem je rozklad dle charakteristik všech pohledů na graf G. // vytvoření prázdného rozkladu rozkladDleCharakteristikPohledu := vytvorRozklad(operacePorovnaniCharakteristikPohledu) pro každý uzel z grafu G pohledNaGraf := vytvorPohledNaGraf(uzel) – postupem uvedeným v definici pojmu Pohled na graf charakteristikaPohleduNaGraf := vytvorCharakteristikuPohleduNaGraf (pohledNaGraf); // zatřídit výchozí uzel pohledu na graf do rozkladu rozkladDleCharakteristikPohledu.zatridit(charakteristikaPohleduNaGraf, uzel) konec pro každý uzel z grafu G vrať rozkladDleCharakteristikPohledu

Algoritmus vytvoření charakteristiky pohledu na graf Vstupem algoritmu je pohled na graf. Výstupem je charakteristika pohledu na graf. // vytvoření prázdné charakteristiky pohledu na graf charakteristikaPohledu := vytvorPrazdnouCharakteristikuPohledu() // pro každý řez pohledu na graf vytvořit rozklad jeho uzlů dle konektivit // a vložit do charakteristiky pohledu dvojici (vzdálenost uzlů řezu od výchozího uzlu // pohledu, rozklad uzlů řezu dle konektivit)

11

pro vzdalOdVychUzluPohledu = 0, 1, ... pohled.maxVzdalRezu() rozkladUzluRezuDleKonektivit := vytvorRozkladUzluDleKonektivit(pohled.uzly(vzdalOdVychUzluPohledu)) charakteristikaPohledu.vloz(vzdalRezuOdVychUzluPohledu, rozkladUzluRezuDleKonektivit) konec pro vzdalOdVychUzluPohledu = 0, 1, ... pohled.maxVzdalRezu() vrať charakteristikaPohledu

Algoritmus vytvoření rozkladu množiny uzlů dle konektivit Vstupem algoritmu je kolekce uzlů. Výstupem je spektrum konektivit uzlů. // vytvoření prázdného rozkladu rozkladDleKonektivit := vytvorRozklad(operacePorovnaniKonektivit) pro každý uzel ze vstupní kolekce uzlů konektivitaUzlu :=vytvorKonektivituUzlu(uzel) postupem uvedeným v definici pojmu Konektivita uzlu // zatřídit uzel do rozkladu rozkladDleKonektivit.zatridit(konektivitaUzlu, uzel) konec pro každý uzel ze vstupní kolekce uzlů vrať rozkladDleKonektivit

Algoritmus vyhledání isomorfismu nad rozklady hrubou silou Vstupy: -

G1 = graf G1,

-

G2 = graf G2,

-

rozklad1 = rozklad uzlů grafu G1,

-

rozklad2 = rozklad uzlů grafu G2.

Výstup: -

null = G1 a G2 nejsou isomorfní,

-

isomorfismus.

permutace1 := lib. permutace nad rozkladem rozklad1 opakuj dokud existuje dalsi permutace nad rozkladem rozklad2 permutace2 := následující permutace nad rozkladem rozklad2 pokud (permutace1, permutace2) je isomorfismus G1 a G2, potom vrátit (permutace1, permutace2) konec opakuj dokud existuje dalsi permutace nad rozkladem rozklad2 vrátit null - G1 a G2 nejsou isomorfní

12

3.1.2. První změna algoritmu – tvar podpohledu Použití rozkladu uzlů grafu podle charakteristik pohledu se ukázalo jako neefektivní v případě vrcholově tranzitivních grafů, protože následné dohledávání isomorfismu metodou permutací pracovalo s velkým množstvím permutací - počet permutací je roven hodnotě funkce faktoriál(počet uzlů grafu). Pohled na graf se do určité míry "podobá" stromu, ve kterém jsou však povolené dvě následující odchylky související s existencí smyček v grafu: -

-

je povolený srůst větví = do uzlu míří dvě hrany vycházející ze dvou uzlů předchozí úrovně (úroveň uzlu = jeho vzdálenost od výchozího uzlu pohledu) – viz orientované hrany (4,7) a (5,7) na Obr: 3-3, je povolené spojení dvou uzlů stejné úrovně obousměrnou hranou – viz obousměrná hrana {4,5} na Obr: 3-3.

Byly provedeny následující změny algoritmu: -

-

místo pojmu charakteristika pohledu na graf (viz kap. 3.1.1) je zaveden pojem tvar pohledu (viz dále Pojmy) - modifikovaná varianta textového řetězce využívaného pro řešení problému isomorfismu u stromů, místo vytváření spekter všech pohledů na oba grafy, se k libovolnému pohledu na graf G1 vyhledá odpovídající pohled na graf G2, před dohledáváním isomorfismu se provádí rozklad uzlů pohledu na graf tak, že do stejné třídy se zahrnou ty uzly pohledu, které mají stejný tvar podpohledu (pojem podpohled dále) a současně mají stejnou úroveň v pohledu na graf (úroveň uzlu = jeho vzdálenost od výchozího uzlu pohledu).

Pojmy Podpohled = vytvoření podpohledu z pohledu se provede v následujících krocích: -

-

libovolný uzel pohledu se vybere jako výchozí uzel podpohledu, do podpohledu se zahrnou takové uzly z pohledu, do kterých vede cesta tvořená jednosměrně orientovanými hranami orientovanými ve směru od výchozího uzlu podpohledu, doplní se zbývající hrany z pohledu: dva vrcholy jsou spojené hranou v podpohledu právě tehdy, když jsou spojené hranou v pohledu.

13

Obr: 3-3 Pohled na graf a podpohled V levé části obrázku je pohled na graf s výchozím uzlem pohledu 1. V pravé části obrázku je podpohled s výchozím uzlem podpohledu 2. Tvar pohledu (podpohledu) = textový řetězec sestavený pomocí modifikovaného algoritmu od Olega Eterevského [A3] , přičemž jsou do řetězce přidány informace, které implicitně vypovídají o tom, zda se v uzlu uzavírají smyčky. U každého uzlu v textovém řetězci: -

je přidána jeho konektivita, místo neklesající posloupnosti všech textových řetězců, reprezentujících tvary podpohledů, je použito uspořádané spektrum tvarů podpohledů - tj. pro každý tvar podpohledu je uveden počet jeho výskytů (jeho multiplicita v pohledu).

Algoritmus řešení problému isomorfismu grafů Vstupem algoritmu jsou grafy G1 a G2. Výstupem je: -

buď text „grafy G1 a G2 nejsou isomorfní“,

-

nebo vypsaný isomorfismus.

// 1. porovnání rozkladů uzlů grafu podle konektivit // (vytvoření rozkladu dle konektivit viz kap. 3.1.1) rozkladUzluG1DleKonektivit := rozkladUzluDleKonektivit(G1.uzly) rozkladUzluG2DleKonektivit := rozkladUzluDleKonektivit (G2.uzly) // (porovnání rozkladů – viz kap. 3) pokud porovnaniRozkladu(rozkladUzluG1DleKonektivit, rozkladUzluG2DleKonektivit)<> 0, potom vypsat „grafy G1 a G2 nejsou isomorfní“ a ukončit // 2. vyhledání pohledu na G1 a pohledu na G2, které mají stejný tvar uzelG1 := rozkladUzluG1DleKonektivit.nejmensiTrida.libovolnyUzel pohledNaG1 := pohledNaGraf(uzelG1) // (tvar pohledu na graf – viz dále) tvarPohleduNaG1 := tvarPohleduNaGraf(pohledNaG1.vychoziUzel)

14

uzlyNejmensiTridyG2 := rozkladUzluG2DleKonektivit.uzlyTridy(uzelG1.konektivita) pro každý uzelG2 z uzlyNejmensiTridyG2 pohledNaG2 := pohledNaGraf(uzelG2) tvarPohleduNaG2 := tvarPohleduNaGraf(pohledNaG2.vychoziUzel) pokud tvarPohleduNaG1 <> tvarPohleduNaG2, potom pokračovat dalším uzlem z uzlyNejmensiTridyG2 // 3. rozklad uzlů pohledu na G1 a pohledu na G2 // podle vzdálenosti od výchozího uzlu pohledu // a podle tvaru podpohledu // každá třída rozkladu je reprezentována uspořádanou dvojicí (vzdálenost od // výchozího uzlu, tvar podpohledu, kde uzel třídy je výchozím uzlem // podpohledu) rozkladUzluPohledu1 := rozkladUzluDleVzdalenostiATvaru(pohledNaG1) rozkladUzluPohledu2 := rozkladUzluDleVzdalenostiATvaru(pohledNaG2) // 4. vyhledání isomorfismu // (vyhledání isomorfismu hrubou silou viz kap. 3.1.1) isomorfismus := najdiIsomorfismusHrubouSilou(G1, G2, rozkladUzluPohledu1, rozkladUzluPohledu2) pokud isomorfismus <> null, potom vypsat isomorfismus a ukončit konec pro každý uzelG2 z uzlyNejmensiTridyG2 vypsat „grafy G1 a G2 nejsou isomorfní“

Algoritmus tvar pohledu na graf Vstupem algoritmu je výchozí uzel pohledu na graf. Výstupem je textový řetězec reprezentující tvar pohledu na graf. Algoritmus je rekurzivní. // uzly další generace jsou sousední uzly připojené jednosměrnou hranou z výchozího // uzlu (tj. nejsou zahrnuty sousední uzly připojené obousměrnou hranou) uzlyDalsiGenerace := vychoziUzel.uzlyDalsiGenerace // roztřídění uzlů další generace podle tvaru podpohledu spektrumPodpohledu := vytvorPrazdneSpektrum(operacePorovnaniTvaruPodpohledu) pro každý uzel z uzlyDalsiGenerace // vytvoření řetězce reprezentujícího tvar podpohledu // pomocí rekurzivního volání tvarPodpohleduNaGraf := tvarPohleduNaGraf(uzel) // započítat tvar podpohledu na graf do spektra spektrumPodpohledu.zapocitat(tvarPodpohleduNaGraf) konec pro každý uzel z uzlyDalsiGenerace // sestavení výsledného textového řetězce // a) vložení konektivity výchozího uzlu

15

tvarPohledu := vychoziUzel.pocSousedu + "|" + vychoziUzel.pocPrichHran + "|" + vychoziUzel.pocOdchHran pokud spektrumPodpohledu.neniPrazdne, potom: tvarPohledu := tvarPohledu + "|" // b) přidání tvarů podpohledů (a jejich multiplicit) za uzly další generace pro i = 1 až spektrumPodpohledu.pocetHodnot() tvarPohledu := tvarPohledu + spektrumPodpohledu.pocetVyskytui + "(" + spektrumPodpohledu.hodnotai + ")" konec pro i = 1 až spektrumPodpohledu.pocetHodnot() vrátit tvarPohledu

3.1.3. Druhá změna algoritmu – zohlednění spojení uzlů při tvorbě permutace Použití rozkladu uzlů pohledu na graf podle jejich vzdálenosti od výchozího uzlu pohledu a podle tvaru jejich podpohledů s následným dohledáním isomorfismu generováním permutací (hrubou silou) se ukázalo jako neefektivní v případě vrcholově tranzitivních grafů. Výsledný rozklad uzlů pohledu je sice jemnější, než rozklad uzlů grafu pomocí charakteristik pohledu, avšak mohutnost některých tříd je přesto veliká. Předchozí verze algoritmu byla proto změněna tak, že místo dohledávání isomorfismu generováním permutací (hrubou silou) se nově každá permutace generuje postupně odleva postupným umisťováním uzlů do permutace na její pozice 1, 2, ... atd., přičemž se zohledňuje propojení uzlu na pozici i s uzly, které se v permutaci nacházejí vlevo (jejich pozice j < i).

Pojmy Pole spojeni(Graf, jeho permutace) = nechť perm je permutace uzlů grafu. Prvek poleSpojeni[i] obsahuje kolekci pozic j takových uzlů perm(j), pro které platí perm(j) sousedí s perm(i) a zároveň j < i. Pole spojení vlastně obsahuje stejné informace jako matice sousednosti grafu (obyčejného grafu bez hran spojujících uzel sám se sebou). Nechť jsou G1 a G2 grafy a uspořádané dvojice (permG1, poleSpojeni(G1, permG1)) a (permG2, poleSpojeni(G2, permG2)) jsou jejich reprezentace. Pokud poleSpojeni(G1, permG1) = poleSpojeni(G2, permG2), potom G1 a G2 jsou isomorfní a jejich isomorfismus je {(permG1(i),permG2(i))| i = 0, 1, ... , pocet uzlu grafu - 1}.

Algoritmus řešení problému isomorfismu grafů Algoritmus vychází z předchozí verze algoritmu pro řešení problému isomorfismu (viz kap. 3.1.2). Hledání isomorfismu pomocí generování permutací uzlů grafu hrubou silou je nahrazeno generováním permutací uzlů grafu s přihlédnutím k propojení uzlů.

Algoritmus dohledání isomorfismu grafů Vstupem algoritmu jsou pohled na graf G1 a pohled na graf G2, přičemž oba mají stejný tvar. Výstupem je: -

buď isomorfismus,

16

-

nebo null – v případě, že isomorfismus není nalezen.

// Vytvoří se jednoznačná reprezentace pohledu na graf G1 jako (permutace jeho uzlů, // pole spojení uzlů) algoritmy vytvoření permutace a vytvoření pole spojení jsou // popsány zvlášť. // Postup generování permutací uzlů pohledu. // Do permutace se postupně přidávají uzly jednotlivých řezů pohledu // (výchozí uzel pohledu, // uzly ve vzdálenosti 1 od výchozího uzlu pohledu, // uzly ve vzdálenosti 2 od výchozího uzlu pohledu, // .... // ) // Pořadí uzlů daného řezu v permutaci je silně ovlivněno umístěním jejich // sousedů z předchozího řezu v permutaci: // Nechť {u(i)|i = k, k+1, ..., l} jsou uzly řezu pohledu umístěné v permutaci // na pozicích i, i+1, ..., l. // Nechť rozkladSouseduVDalsimRezu(u) je rozklad sousedů uzlu u, // jejichž vzdálenost od výchozího uzlu pohledu je o 1 větší, než vzdálenost uzlu u. // Vytváří se seznam množin uzlů dalšího řezu, který se použije při jejich vkládání do // permutace: // (rozkladSouseduVDalsimRezu(u(i))[1], // rozkladSouseduVDalsimRezu(u(i))[2], // .... // rozkladSouseduVDalsimRezu(u(i+1))[1], // rozkladSouseduVDalsimRezu(u(i+1))[2], // .... // rozkladSouseduVDalsimRezu(u(l-1))[1], // rozkladSouseduVDalsimRezu(u(l-1))[2], // .... // rozkladSouseduVDalsimRezu(u(l))[1], // rozkladSouseduVDalsimRezu(u(l))[2], // .... // ) // kde rozkladSouseduVDalsimRezu(u(m))[n] je n-tá třída rozkladu // sousedů uzlu u(m) podle tvar podpohledu. // (Algoritmus na vytvoření permutace uzlů pohledu na první graf - viz dále.) permutaceUzluPohledu1:= vytvorPermutaci(pohledNaG1) // (Algoritmus na vytvoření pole spojení - viz dále.) vzorovePoleSpojeni := vytvorPoleSpojeni(permutaceUzluPohledu1) // vytvoření takové permutace uzlů pohledu na druhý graf, jejíž pole spojení je stejné, // jako vzorové pole spojení // (Algoritmus na vytvoření permutace uzlů pohledu na druhý graf - viz dále.) permutaceUzluPohledu2 := najdiPermutaci(pohledNaG2, vzorovePoleSpojeni) pokud permutaceUzluPohledu2 = null potom vrátit null

17

// vrátit isomorfismus (permutaceUzluPohledu1,permutaceUzluPohledu2) isomorfismus := vytvoritPrazdnouMnozinu pro i := 1 do permutace.pocetUzlu isomorfismus.vlozUspDvojici(permutaceUzluPohledu1.dejUzel(i).jmeno, permutaceUzluPohledu2.dejUzel(i).jmeno) konec pro i := 1 do permutace.pocetUzlu vrátit isomorfismus

Algoritmus vytvoření permutace pohledu na první graf Vstupy: -

pohledNaG = pohled na první graf G,

-

vzorovePoleSpojeni = vzorové pole spojení.

Výstupy: -

permutace = permutace uzlů pohledu na první graf G,

-

vzorovePoleSpojeni = vzorové pole spojení.

// prázdná permutace permutace := vytvorPrazdnou permutaci o delce pohledNaG.pocetUzlu // Seznam množin uzlů určených ke zpracování (k vložení do permutace). // Sjednocením těchto množin je množina všech uzlů řezu (přičemž uzly řezu mají // stejnou vzdálenost od výchozího uzlu pohledu). // Všechny uzly dané množiny jsou ze stejné třídy uzlů pohledu. // Tento seznam není rozkladem uzlů řezu, protože jeden uzel // může být ve více množinách seznamu. nezpracUzlyRezu := vytvorPrazdnySeznam // do seznamu ke zpracování vložit množinu obsahující výchozí uzel pohledu nezpracUzlyRezu.vlozit({pohledNaG.vychoziUzel}); // zpracovat všechny uzly ze seznamu množin nezpracUzlyRezu aktualniPoziceVPermutaci := 1 dokud nezpracUzlyRezu není prázdný // seznam množin uzlů z následujícího řezu // - tyto uzly budou zpracovány (vloženy do permutace) // v příští iteraci nezpracUzlyDalsihoRezu := vytvorPrazdnySeznam pro každou množinu mnozUzlu ze seznamu nezpracUzlyRezu pro každý uzel uzel z množiny mnozUzlu // pokud je uzel zpracovaný, pokračovat dalším uzlem pokud je uzel uzel v permutaci permutace potom pokračovat dalším uzlem z mnozUzlu // přidání uzlu do výsledné permutace permutace[aktualniPoziceVPermutaci] := uzel;

18

// Přidání uspořádaného rozkladu uzlů z následujícího řezu do seznamu // množin nezpracovaných uzlů dalšího řezu. // Každá množina obsahuje uzly splňující následující // podmínky: // uzel množiny patří do stejné třídy jako zbývající // uzly množiny a současně uzel množiny je soused uzlu uzel // připojený jednosměrnou hranou vycházející z uzlu uzel nezpracUzlyDalsihoRezu.pridejNaKonec(uzel.rozkladUzluDalsihoRezu) aktualniPoziceVPermutaci := aktualniPoziceVPermutaci + 1 konec pro každý uzel uzel z množiny mnozUzlu konec pro každou množinu mnozUzlu ze seznamu nezpracUzlyRezu nezpracUzlyRezu := nezpracUzlyDalsihoRezu konec dokud nezpracUzlyRezu není prázdný

Algoritmus vytvoření permutace pohledu na druhý graf Vstupy: -

pohledNaG2,

-

poleVzorovychSpojeni = pole spojení získané - viz dále.

Výstupy: permutace (nebo null - pokud se nepodaří permutaci vytvořit). Lokální proměnné: -

poslPozice = poslední obsazená pozice v permutaci, poleMoznychHodnot = pole množin možných hodnot permutace; poleMoznychHodnot[i] obsahuje uspořádanou množinu uzlů pohledu, které mohou být postupně vkládány na i-tou pozici permutace.

// na první pozici v permutaci se vloží výchozí uzel pohledu permutace[1] := pohledNaG2.vychoziUzel poleMoznychHodnot[1] := {pohledNaG2.vychoziUzel} poslPozice := 1 // Postupné vytváření permutace uzlů pohledu. // Uzly pohledu na graf jsou do permutace vkládány postupně po jednotlivých // řezech pohledu viz dále popis algoritmu forward. // Přitom jsou do permutace vkládány prvotní hodnoty z poleMoznychHodnot[i]. // Pokud se nepodaří v rámci iterace vytvořit celou permutaci pomocí algoritmu forward // najednou, tak se v permutaci vyhledá nejvyšší pozice i, která ještě neobsahuje nejvyšší // možný uzel z poleMoznychHodnot[i], a uzel na této pozici se nahradí nejbližším // vyšším uzlem z poleMoznychHodnot[i]. Poté se pokračuje další iterací. // Iterace probíhají tak dlouho, dokud se nepodaří vytvořit celou permutaci // nebo dokud se nevyzkoušejí všechny možné hodnoty z poleMoznychHodnot[i]. dokud poslPozice > 1 a zároveň poslPozice < permutace.delka // postupné vkládání uzlů pohledu do permutace - viz dále algoritmus forward poslPozice := forward(poslPozice)

19

// pokud se podařilo vytvořit celou permutaci, vrátit permutaci pokud poslPozice = permutace.delka, vrátit permutace // fáze backward - v permutaci nahradit uzel následujícím uzlem // z poleMoznychHodnot uzelNahrazen := ne opakuj pokud existuje v uspořádané množině poleMoznychHodnot[poslPozice] uzel větší než permutace[poslPozice], potom permutace[poslPozice] := poleMoznychHodnot[poslPozice].nejblizsiVyssiPrvek(permutace[poslPozice]) uzelNahrazen := ano vyskočit z cyklu opakuj poslPozice := poslPozice – 1 dokud poslPozice > 1 // pokud se nepodařilo nahradit žádný uzel v permutaci, // neexistuje permutace taková, že její uzly mají spojení podle // poleVzorovychSpojeni pokud uzelNahrazen = ne, vrátit null konec dokud poslPozice > 1 a zároveň poslPozice < permutace.delka // nepodařilo se dokončit tvorbu permutace vrátit null

Algoritmus vytvoření pole spojení Vstupy: -

permutaceG = permutace uzlů pohledu na graf G.

Výstupy: -

poleSpojeni = pole spojení uzlů v permutaci - viz definice pojmů na začátku této kapitoly.

poleSpojeni := vytvorPoleSpojeni() // pro každý uzel v permutaci pro poziceUzlu := 1 až permutaceG.pocetUzlu uzel := permutaceG[poziceUzlu] // vytvořit množinu pozic uzlů, které leží v permutaci vlevo od daného uzlu // a současně jsou sousedy daného uzlu poleSpojeni[poziceUzlu] := vytvorPrazdnouMnozinu(); // cyklus přes všechny uzly vlevo od uzlu uzel pro poziceUzlu2 := 1 až (poziceUzlu - 1) uzel2 := permutaceG[poziceUzlu2]

20

// přidání pozice sousedního uzlu do poleSpojeni pokud uzel.soused(uzel2) = ano potom poleSpojeni[poziceUzlu].pridej(poziceUzlu2) konec pro poziceUzlu2 := 1 až (poziceUzlu - 1) konec pro poziceUzlu := 1 až permutaceG.pocetUzlu vrátit poleSpojeni

Algoritmus forward Vstupy: -

permutace = vytvářená permutace,

-

poslPozice = poslední obsazená pozice v permutaci,

-

poleVzorovychSpojeni = pole spojení získané pomocí viz výše,

-

poleMoznychHodnot = pole množin možných hodnot permutace; poleMoznychHodnot[i] obsahuje uspořádanou množinu uzlů pohledu, které mohou být postupně vkládány na i-tou pozici permutace.

Výstupy: -

permutace = vytvářená permutace,

-

poleMoznychHodnot = pole množin možných hodnot permutace.

// najít v permutaci první a poslední pozici uzlů posledního řezu, // (poslední řez, jehož všechny uzly jsou umístěné v permutaci) prvniPoziceKomplRezu := prvniPozicePoslKomplRezu(permutace) posledniPoziceKomplRezu := posledniPozicePoslKomplRezu(permutace) // pro uzly permutace[prvniPoziceKomplRezu] až // permutace[posledniPoziceKomplRezu] // vytvořit seznam množin uzlů dalšího řezu // (postupem uvedeným výše v této kapitole v úvodním komentáři algoritmu dohledání // isomorfismu grafů) uzlyRezu := vytvorSeznamMnozinUzluDalsihoRezu(prvniPoziceKomplRezu, posledniPoziceKomplRezu, permutace); // zpracovat všechny uzly ze seznamu množin uzlyRezu dokud uzlyRezu není prázdný prvniPoziceKomplRezu := posledniPoziceKomplRezu + 1 pro každou množinu mnozUzlu ze seznamu uzlyRezu // vytvořit podmnožinu nezpracovaných uzlů z mnozUzlu // jsou to ty uzly z mnozUzlu, které nejsou dosud umístěné v permutaci mnozNezpracUzlu := mnozinaNezpracUzlu(mnozUzlu, permutace) // zpracovat podmnožinu nezpracovaných uzlů // (vložit nezpracované uzly do permutace na pozice poslPozice až poslPozice // + mnozNezpracUzlu.pocPrvku()) pro i := 1 až mnozNezpracUzlu.pocPrvku() poslPozice := poslPozice + 1;

21

// do permutace vložit první takový uzel // z poleMoznychHodnot[poslPozice], jehož spojení s uzly umístěnými // v permutaci vlevo od něj odpovídá vzorovým spojením // v poleVzorovychSpojeni[poslPozice] uzel := najdiPrvniUzelSDanymSpojenim(permutace, mnozNezpracUzlu, poleVzorovychSpojeni[poslPozice], poslPozice) pokud nebyl nalezen uzel uzel, potom vrátit poslPozice – 1 permutace[poslPozice] := mozneHodnoty.prvniPrvek() poleMoznychHodnot[poslPozice] := mnozNezpracUzlu konec pro i := 1 až mnozNezpracUzlu.pocPrvku() konec pro každou množinu mnozUzlu ze seznamu uzlyRezu posledniPoziceKomplRezu := poslPozice // pokud je vytvořená celá permutace, skončit pokud je vytvořená celá permutace (posledniPoziceKomplRezu = permutace.delka), potom vrátit poslPozice // vytvořit seznam množin uzlů dalšího řezu // (postupem uvedeným výše v této kapitole v úvodním komentáři algoritmu // dohledání isomorfismu grafů) uzlyRezu = vytvorSeznamMnozinUzluDalsihoRezu(prvniPoziceKomplRezu, posledniPoziceKomplRezu, permutation); konec dokud nezpracUzlyRezu není prázdný vrátit poslPozice;

3.1.4. Třetí změna algoritmu – zjemnění rozkladu uzlů při tvorbě permutace V předchozí verzi algoritmu se využívá rozkladu uzlů pohledu na graf podle jejich vzdálenosti od výchozího uzlu pohledu a podle tvaru jejich podpohledů. Při následném dohledání isomorfismu se místo tvorby permutací hrubou silou vytváří pouze jedna permutace postupným umísťováním uzlů jednotlivých řezů pohledu do permutace při současném zohlednění propojení uzlů v permutaci. Tento přístup urychlil vyhledání isomorfismu v případě řídkých vrcholově tranzitivních grafů. Algoritmus ale není dostatečně efektivní v případě hustých vrcholově tranzitivních grafů. Předchozí verze algoritmu byla proto změněna tak, že rozklady uzlů pohledu na graf se v případě potřeby zjemňují podle spektra spojení uzlu s uzly ostatních tříd stejného řezu pohledu.

Pojmy Spektrum spojení uzlu s uzly ostatních tříd Nechť ((idTridy1, mnozinaPrvkuTridy1), (idTridy2, mnozinaPrvkuTridy2), ..., (idTridyN, mnozinaPrvkuTridyN)) je uspořádaný rozklad uzlů. Nechť uzel u je prvkem třídy mnozinaPrvkuTridyi.

22

Nechť sousedUzlyj(u) je {v je prvkem mnozinaPrvkuTridyj a současně v je soused u}. Pak spektrum spojení uzlu u s uzly ostatních tříd = ({(idTridyj, mohutnost (sousedUzlyj(u))) | j = 1, ..., N, j <> i}, operace porovnání idTridy).

Algoritmus řešení problému isomorfismu grafů Algoritmus vychází z předchozí verze algoritmu pro řešení problému isomorfismu (viz kap. 3.1.3). Hledání isomorfismu generováním permutací uzlů pohledu na graf s přihlédnutím k propojení uzlů je nově doplněno o zjemnění tohoto rozkladu.

Algoritmus dohledání isomorfismu grafů Vstupy a výstupy algoritmu jsou stejné jako v předchozí verzi tohoto algoritmu (viz kap 3.1.3). Tělo algoritmu vychází z předchozí verze tohoto algoritmu - pouze na začátku těla přibyly dva příkazy na zjemnění rozkladu uzlů pohledu na první graf a na zjemnění rozkladu uzlů pohledu na druhý graf.

Algoritmus zjemnění rozkladu pohledu na první graf Vstupy: -

pohled = pohled na graf, jehož rozklad se má zjemnit.

Výstupy: -

pohled – některé uzly pohledu se přesunou do nově vzniklých tříd.

vzniklaNovaTrida := ne opakuj dokud rozklad uzlu pohledu obsahuje třídy, jejichž mohutnost je větší nebo rovna prahové hodnotě // trida = největší třída z rozkladu uzlů pohledu trida := pohled.nejvetsiTridaRozkladu() pokud je mohutnost trida menší než prahová hranice, potom ukončit zjemňování (vyskočit z cyklu opakuj) // vytvořit rozklad rozkladTridy uzlů třídy trida podle spektra jejich propojení // s uzly ostatních tříd stejného řezu rozkladTridy := vytvorPrazdnyRozklad(operacePorovnaniIdTridy) pro každý uzel uzel z třídy trida // vytvořit spektrum propojení uzlu uzel s uzly ostatních tříd stejného řezu // (viz dále algoritmus vytvoření spektra spojení uzlu s uzly ostatních tříd // řezu) spektrumSpojeniSTridami := uzel.spektrumSpojeniSTridami() // zatřídit uzel uzel podle spektra jeho propojení s uzly ostatních tříd rozkladTridy.zatridit(spektrumSpojeniSTridami, uzel) konec pro každý uzel uzel z třídy trida pokud rozklad třídy trida obsahuje pouze jednu třídu, potom pokračovat další iterací cyklu opakuj vzniklaNovaTrida := ano

23

// vybrat nejmenší třídu v rozkladu třídy trida nejmensiPodtrida := vyberNejmensiTridu(rozkladTridy) // pro každý uzel z nově vytvořené třídy změnit identifikátor třídy // do které uzel patří // (změnou identifikátoru třídy ve vybraných uzlech dojde k jejich vyjmutí // z původní třídy a vložení do nové třídy) identifikatorNoveTridy := trida.identifikator() + "[" + nejmensiPodtrida.spektrumSpojeniSTridami() + "]" pohled.zmenIdTridy(nejmensiPodtrida.mnozinaUzlu(), identifikatorNoveTridy) konec opakuj dokud rozklad uzlu pohledu obsahuje třídy, jejichž mohutnost je větší nebo rovna prahové hodnotě // pokud při zjemňování vznikly nové třídy, // každý uzel řezu si obnoví uspořádaný rozklad svých sousedů // z následujícího řezu pokud vzniklaNovaTrida = ano potom pohled.obnoveniRozkladu()

Algoritmus zjemnění rozkladu pohledu na druhý graf Vstupy: -

pohled = pohled na graf, jehož rozklad se má zjemnit,

-

vzorovyPohled = vzorový pohled na graf, používá se na kontrolu identifikátorů tříd nově vytvořených při zjemňování.

Výstup: -

pohled - některé uzly pohledu se přesunou do nově vzniklých tříd,

-

ano = zjemňování dokončeno (a identifikátory nových tříd v pohledu odpovídají identifikátorům ve vzorovyPohled),

-

ne = zjemňování nebylo dokončeno.

vzniklaNovaTrida := ne opakuj dokud rozklad uzlů pohledu obsahuje třídy, jejichž mohutnost je větší nebo rovna prahové hodnotě // trida = největší třída z rozkladu uzlů pohledu trida := pohled.nejvetsiTridaRozkladu() pokud je mohutnost trida menší než prahová hranice, potom ukončit zjemňování (vyskočit z cyklu opakuj) // vytvořit rozklad rozkladTridy uzlů třídy trida podle spektra jejich propojení // s uzly ostatních tříd stejného řezu rozkladTridy := vytvorPrazdnyRozklad(operacePorovnaniIdTridy) pro každý uzel uzel z třídy trida // vytvořit spektrum propojení uzlu uzel s uzly ostatních tříd stejného řezu // (viz dále algoritmus vytvoření spektra spojení uzlu s uzly ostatních tříd // řezu) spektrumSpojeniSTridami := uzel.spektrumSpojeniSTridami()

24

// zatřídit uzel uzel podle spektra jeho propojení s uzly ostatních tříd rozkladTridy.zatridit(spektrumSpojeniSTridami, uzel) konec pro každý uzel uzel z třídy trida pokud rozklad třídy trida obsahuje pouze jednu třídu, potom pokračovat další iterací cyklu opakuj vzniklaNovaTrida := ano // vybrat nejmenší třídu v rozkladu třídy trida nejmensiPodtrida := vyberNejmensiTridu(rozkladTridy) // ověřit, zda nová třída existuje také v rozkladu vzorového pohledu na graf identifikatorNoveTridy := trida.identifikator() + "[" + nejmensiPodtrida.spektrumSpojeniSTridami() + "]" pokud vzorovyPohled.neexistujeTrida(identifikatorNoveTridy) potom vrátit ne // pro každý uzel z nově vytvořené třídy změnit identifikátor třídy // do které uzel patří // (změnou identifikátoru třídy ve vybraných uzlech dojde k jejich vyjmutí // z původní třídy a vložení do nové třídy) pohled.zmenIdTridy(nejmensiPodtrida.mnozinaUzlu(), identifikatorNoveTridy) konec opakuj dokud rozklad uzlu pohledu obsahuje třídy, jejichž mohutnost je větší nebo rovna prahové hodnotě // pokud při zjemňování vznikly nové třídy, každý uzel řezu si obnoví uspořádaný // rozklad svých sousedů z následujícího řezu pokud vzniklaNovaTrida = ano potom pohled.obnoveniRozkladu() vrátit ano

Algoritmus vytvoření spektra spojení uzlu s uzly ostatních tříd řezu Vstupy: -

uzel = uzel pohledu na graf.

Výstup: -

spektrum = spektrum spojení uzlu s uzly ostatních tříd stejného řezu pohledu.

spektrum := vytvorSpektrum(operacePorovnaniIdTridy) mnozinaSousedUzluRezu := uzel.mnozinaSousedUzluRezu() pro každý sousedUzel z mnozinaSousedUzluRezu pokud uzel patří do stejné třídy jako sousedUzel, potom pokračovat dalším sousedním uzlem // započítat sousední uzel do spektra spektrum.zapocitat(sousedUzel) konec pro každý sousedUzel z mnozinaSousedUzluRezu vrátit spektrum

25

3.2. ALGORITMUS V PROGRAMU NAUTY Nauty je v současnosti nejrychlejší program na zjištění, zda jsou dané grafy isomorfní. V roce 1984 ho vytvořil Brandon D. McKay, který je profesorem na Research School of Computer Science na Australské národní univerzitě. Spoluautorem je Adolfo Piperno z Departimento di Informatica na Sapienza Universita di Roma v Itálii. Součástí Nauty je i program Traces, který má stejnou funkčnost. Název Nauty vznikl jako zkratka No AUTomorphisms, Yes?. Program je napsán v jazyce C a slouží pro určení grupy automorfismů vrcholově obarveného grafu. Samozřejmě se dá použít i pro neobarvený graf. Pak je graf chápán tak, že jsou všechny vrcholy obarvené stejnou barvou. Pro zjištění automorfismu používá program Nauty upravený Náhodný Schreierův algoritmus [A1] . Je to pravděpodobnostní algoritmus, který nedává vždy stoprocentně správný výsledek, to ale neovlivní výsledek Nauty. Někdy můžou být nalezené generátory různé, ale grupa automorfismů bude stejná. Nauty také umožňuje kanonicky zapsat graf. Díky této funkci se dá Nauty použít pro test, zda jsou dva grafy isomorfní a pro vypsání isomorfismu. Pokud mají dva grafy stejný kanonický zápis, pak jsou isomorfní.

26

4. POROVNÁNÍ ALGORITMŮ Cílem této kapitoly je vybrat z navržených algoritmů takovou verzi, která bude řešit problém isomorfismu nejrychleji a poté porovnat doby odezvy nejrychlejší verze algoritmu s dobami odezvy programu Nauty. Doba odezvy závisí, či může záviset na vlastnostech dvojice porovnávaných grafů: -

počet uzlů grafu,

-

hustota grafu,

-

isomorfnost dvojice grafů – isomorfní/neisomorfní dvojice grafů,

-

symetrie grafů - vrcholově tranzitivní graf, asymetrický graf.

Pro účely testování byla vytvořena vstupní testovací data. Vstupní data pro každý dílčí test jsou uložená v souboru ve formátu g6 (popis formátu g6 viz [A2] ). Oba grafy v testovací dvojici mají vždy stejný počet uzlů (protože grafy lišící se počtem uzlů nejsou isomorfní, což odhalí algoritmy velice rychle). Oba grafy v testovací dvojici mají vždy stejnou hustotu (protože grafy lišící se hustotou nejsou isomorfní, což odhalí algoritmy velice rychle porovnáním spekter stupňů vrcholů). Testují se pouze grafy do hustoty 50 %, protože pro hustší grafy se problém isomorfismu řeší na doplňcích grafů. Oba grafy v testovací dvojici mají vždy stejnou symetrii – buď jsou oba grafy asymetrické, nebo jsou oba grafy vrcholově tranzitivní (protože asymetrický graf nemůže být isomorfní s vrcholově tranzitivním grafem, což odhalí algoritmy velice rychle porovnáním spekter stupňů vrcholů). Každý soubor s testovacími daty obsahuje 15 dvojic grafů. Všechny grafy v jednom souboru mají vždy shodný počet uzlů, shodnou hustotu a shodnou symetrii (jsou buď všechny asymetrické, nebo jsou všechny vrcholově tranzitivní). Všechny dvojice grafů v jednom souboru jsou buď isomorfní, nebo jsou všechny neisomorfní. Byl vytvořen soubor ve formátu g6 pro každou čtveřici hodnot (<počet uzlů>,,<symetrie>,), kde: <počet uzlů> nabývá hodnot z množiny {40, 50, 60, 70, 80, 90, 100, 200, 300, 400}, nabývá hodnot z množiny {20 %, 40 %, 50 %}, <symetrie> nabývá hodnot z množiny {asymetrický, vrcholově tranzitivní}, nabývá hodnot z množiny {ano, ne}.

Postup vytvoření testovacích dat Vrcholově tranzitivní grafy s požadovanou hustotou H byly vytvořeny jako Cayleyho grafy následujícím postupem: mějme množinu uzlů budoucího grafu {uzel(i)| i=1, 2, ..., N}, mějme lib. množinu čísel generator = {cislo(j)| cislo(j) je přirozené číslo <= (N/2), j = 1, 2, ..., (N-1)*H/2}, potom Cayleyho graf vygenerujeme tak, že každý uzel(i) spojíme se všemi uzly z množiny {uzel((i + genCislo) mod N)|genCislo je prvkem množiny generator}. Poté byla ověřena souvislost grafu.

27

Asymetrické grafy s požadovanou hustotou H byly vytvořeny jako grafy s požadovaným počtem náhodně umístěných hran. Poté byla ověřena souvislost grafu a asymetrie grafu (pokud rozklad uzlů grafu podle charakteristik pohledu obsahuje pouze jednoprvkové třídy uzlů, je graf asymetrický).

Podmínky testování Hardware: -

procesor: AMD Athlon(tm) 64 3000+, 1800 MHz

-

RAM: 4 GB

Operační systém: openSuse 10.3 Java: 1.6.0_10 Výběr nejrychlejší verze z navržených algoritmů je provedený dále v kap. 4.1. Porovnání doby odezvy vybraného algoritmu s dobou odezvy programu Nauty je provedeno v kap 4.2.

4.1. VÝBĚR NEJRYCHLEJŠÍ VERZE ALGORITMU ZALOŽENÉHO NA POHLEDECH NA GRAF Cílem této kapitoly je vybrat z navržených algoritmů takovou verzi, která bude řešit problém isomorfismu nejrychleji. Postupně se provádí dílčí testy, přičemž v každém dílčím testu je hledán isomorfismus pro každý pár grafů v jednom g6 souboru. (Každý soubor obsahuje vždy grafy o stejném počtu uzlů, stejné hustotě, stejné symetrii a stejné „isomorfnosti“ - všechny páry v souboru jsou buď isomorfní, nebo žádný pár v souboru není isomorfní.) Měření doby odezvy programu Nauty se provádí pomocí příkazu jazyka c clock_gettime. Měření doby odezvy algoritmu založeného na pohledech na graf se provádí pomocí příkazu jazyka Java System.nanoTime. Měření byla prováděna v době, kdy neběžel žádný jiný program a získané doby odezvy byly ještě ověřovány porovnáním s časovým údajem získaným pomocí linuxového příkazu time.

4.1.1. Základní koncept algoritmu V této kapitole je zobrazená a posouzená rychlost základní navržené verze algoritmu na řešení problému isomorfismu grafů (podrobnosti o algoritmu viz kap. 3.1.1). Jsou zde zobrazené/prezentované výsledky měření doby odezvy programu (algoritmu) v závislosti na vzrůstajícím počtu uzlů a vzrůstající hustotě uzlů: - pro asymetrické isomorfní grafy, - pro asymetrické neisomorfní grafy, - pro vrcholově tranzitivní isomorfní grafy, - pro vrcholově tranzitivní neisomorfní grafy.

28

Asymetrické isomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních asymetrických grafů. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů.

Obr: 4-1 Základní koncept - asymetrické isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Rozptyl všech hodnot doby odezvy pro daný počet uzlů od 200 výše a pro danou hustotu nepřesahuje 5 %, protože skoro celá část doby odezvy se spotřebuje na vytvoření uspořádaného rozkladu uzlů prvního grafu a uspořádaného rozkladu uzlů druhého grafu podle charakteristik pohledu. Následné dohledání isomorfismu hrubou silou (které bývá hlavním zdrojem rozptylu hodnot doby odezvy) poté zabere jen malý zlomek času, protože všechny třídy rozkladů obsahují vždy pouze jeden uzel.

29

Asymetrické neisomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních asymetrických grafů. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů.

Obr: 4-2 Základní koncept – asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Rozptyl všech hodnot doby odezvy pro daný počet uzlů od 200 výše a pro danou hustotu nepřesahuje 10 %, protože skoro celá část doby odezvy se spotřebuje na vytvoření uspořádaného rozkladu uzlů prvního grafu a uspořádaného rozkladu uzlů druhého grafu podle charakteristik pohledu. Následné porovnání rozkladů poté zabere jen malý zlomek času. Doby odezvy jsou jen o málo menší než doby odezvy u asymetrických isomorfních grafů (viz Obr: 4-1). Je to způsobeno tím, že odpadlo dohledání isomorfismu hrubou silou.

Vrcholově tranzitivní isomorfní grafy Pro vrcholově tranzitivní isomorfní grafy algoritmus nelze použít, protože doby odezvy by byly příliš velké. Je to způsobeno dohledáváním isomorfismu hrubou silou nad uspořádanými rozklady uzlů grafu (vytvořenými podle charakteristik pohledu). Rozklad grafu v tomto případě obsahuje vždy jen jednu třídu (obsahující všechny uzly grafu).

30

Vrcholově tranzitivní neisomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních vrcholově tranzitivních grafů. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů.

Obr: 4-3 Základní koncept – vrcholově tranzitivní neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Rozptyl všech hodnot doby odezvy pro daný počet uzlů od 200 výše a pro danou hustotu nepřesahuje 10 %, protože skoro celá část doby odezvy se spotřebuje na vytvoření uspořádaného rozkladu uzlů prvního grafu a uspořádaného rozkladu uzlů druhého grafu podle charakteristik pohledu. Následné porovnání rozkladů (z výsledku porovnání se pozná, že grafy nejsou isomorfní) poté zabere jen malý zlomek času a dohledání isomorfismu hrubou silou se neprovádí. Doby odezvy jsou stejné jako doby odezvy u asymetrických neisomorfních grafů (viz Obr: 4-2).

Vyhodnocení výsledků základního konceptu algoritmu Základní koncept algoritmu má pro daný počet uzlů a danou hustotu grafu vždy stejnou dobu odezvy (s malým rozptylem hodnot) bez ohledu na to, jestli jsou grafy vrcholově tranzitivní, či asymetrické a bez ohledu na to, zda je, či není dvojice grafů isomorfní. Základní koncept algoritmu nelze použít v případě isomorfní dvojice vrcholově tranzitivních grafů z důvodu příliš dlouhé doby odezvy způsobené dohledáváním isomorfismu hrubou silou nad rozkladem dle charakteristik pohledu. V tomto případě byl ale algoritmus využit v pozměněné podobě (bylo vynecháno dohledání isomorfismu) na třídění grafů podle jejich tvarů v průběhu přípravy testovacích dat. Ukázalo se, že rozklad uzlů pohledu uspořádaný podle charakteristik pohledu na graf jednoznačně identifikoval jednotlivé tvary grafů až po grafy o devíti uzlech.

31

4.1.2. První změna algoritmu – tvar podpohledu V této kapitole je zobrazený a posouzený vliv první změny algoritmu na rychlost řešení problému isomorfismu grafů (podrobnosti o algoritmu viz kap. 3.1.2). Jsou zde zobrazené/prezentované výsledky měření doby odezvy změněného programu (algoritmu) v závislosti na vzrůstajícím počtu uzlů a na vzrůstající hustotě uzlů: - pro asymetrické isomorfní grafy, - pro asymetrické neisomorfní grafy, - pro vrcholově tranzitivní isomorfní grafy, - pro vrcholově tranzitivní neisomorfní grafy.


Obr: 4-4 První změna algoritmu – asymetrické isomorfní grafy Příčina velkého rozptylu hodnot doby odezvy spočívá v dohledávání isomorfismu hrubou silou nad rozkladem uzlů podle jejich vzdálenosti od výchozího uzlu pohledu a podle tvaru podpohledu (podrobnosti o rozkladu viz popis algoritmu v kap. 3.1.2). Tento rozklad je v případě asymetrických grafů hrubší než rozklad prováděný v předchozí (základní) verzi algoritmu. S rostoucí hustotou grafu se zvyšuje mohutnost tříd rozkladu a doba potřebná na dohledání isomorfismu hrubou silou se stává příliš dlouhou – proto jsou křivky pro hustoty grafu 40 % a 50 % ukončené už při 90 uzlech a křivka pro hustotu grafu 20 % končí na 80 uzlech.

32


Obr: 4-5 První změna algoritmu – asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Doby odezvy jsou výrazně kratší než doby odezvy v předchozí (základní verzi algoritmu) u asymetrických neisomorfních grafů (viz Obr: 4-2). Je to způsobeno tím, že rozklad uzlů grafu podle konektivit je podstatně rychlejší než rozklad uzlů grafu podle charakteristik pohledu.

33

Vrcholově tranzitivní isomorfní grafy V následujícím grafu je zobrazená doba odezvy při řešení problému isomorfismu pro testovací páry isomorfních grafů tvaru Möbiova žebříku. Grafy tvaru Möbiova žebříku jsou použity jako reprezentant velmi řídkého grafu, jehož hustota navíc klesá se zvyšujícím se počtem vrcholů (pro 20 uzlů je hustota Möbiova žebříku 17 %, pro 50 uzlů je hustota Möbiova žebříku 6 %). V případě hustších vrcholově tranzitivních isomorfních dvojic grafů není totiž tato verze algoritmu použitelná kvůli příliš velké době odezvy.

Obr: 4-6 První změna algoritmu – vrcholově tranzitivní isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu. Tato verze algoritmu je lepší než předchozí verze v případě dvojic isomorfních vrcholově tranzitivních grafů. Není však vhodná pro isomorfní dvojice vrcholově tranzitivních grafů o větší hustotě, či větším počtu uzlů.

34


Obr: 4-7 První změna algoritmu – vrcholově tranzitivní neisomorfní grafy Doby odezvy v případě neisomorfní dvojice vrcholově tranzitivních grafů jsou o cca 1020 % kratší než v předchozí (základní) verzi algoritmu – viz Obr: 4-3.

Vyhodnocení výsledků první změny algoritmu Druhá verze algoritmu má v porovnání s předchozí (základní) verzí velký rozptyl hodnot doby odezvy v případě dvojic isomorfních asymetrických grafů. Druhou verzi algoritmu nelze v tomto případě použít pro husté grafy, či grafy s velkým počtem uzlů, protože doba odezvy je příliš velká. Druhá verze algoritmu má v porovnání s předchozí (základní) verzí stabilní a podstatně kratší doby odezvy v případě dvojic neisomorfních asymetrických grafů. Druhá verze algoritmu je lepší než předchozí verze v případě dvojic isomorfních vrcholově tranzitivních grafů. Není však vhodná pro isomorfní dvojice vrcholově tranzitivních grafů o větší hustotě, či větším počtu uzlů. Doby odezvy v případě neisomorfní dvojice vrcholově tranzitivních grafů jsou o cca 1020 % kratší než v předchozí (základní) verzi algoritmu.

4.1.3. Druhá změna algoritmu – zohlednění spojení uzlů při tvorbě permutace V této kapitole je zobrazený a posouzený vliv druhé změny algoritmu na rychlost řešení problému isomorfismu grafů (podrobnosti o algoritmu viz kap. 3.1.3). Jsou zde zobrazené/prezentované výsledky měření doby odezvy změněného programu (algoritmu) v závislosti na vzrůstajícím počtu uzlů a vzrůstající hustotě uzlů:

35

- pro asymetrické isomorfní grafy, - pro asymetrické neisomorfní grafy, - pro vrcholově tranzitivní isomorfní grafy, - pro vrcholově tranzitivní neisomorfní grafy.


Obr: 4-8 Druhá změna algoritmu – asymetrické isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Tvar naměřených křivek je podobný jako v základní verzi algoritmu – viz Obr: 4-1, avšak doba odezvy se podstatně zkrátila – například pro počet uzlů 400 a hustotu grafu 50 % je doba odezvy v základním algoritmu přibližně 45krát větší. Toto výrazné zrychlení je způsobeno změnou algoritmu pro dohledání isomorfismu (popis algoritmu viz kap. 3.1.3) – zatímco v předchozích verzích algoritmu se dohledával isomorfismus hrubou silou, v této verzi algoritmu se dohledává isomorfismus pomocí pole spojení uzlů v permutaci.

36


Obr: 4-9 Druhá změna algoritmu – asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Doby odezvy jsou stejné jako v předchozí verzi algoritmu (viz Obr: 4-5) a jsou výrazně kratší než doby odezvy v první verzi algoritmu u asymetrických neisomorfních grafů. Je to způsobeno tím, že rozklad uzlů grafu podle konektivit je podstatně rychlejší než rozklad uzlů grafu podle charakteristik pohledu.

37

Vrcholově tranzitivní isomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních vrcholově tranzitivních grafů. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů.

Obr: 4-10 Druhá změna algoritmu – vrcholově tranzitivní isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Tato verze algoritmu má u isomorfních vrcholově tranzitivních grafů přijatelné doby odezvy v celém testovaném rozsahu počtu uzlů a hustot grafů.

38


Obr: 4-11 Druhá změna algoritmu – vrcholově tranzitivní neisomorfní grafy Doby odezvy v případě neisomorfní dvojice vrcholově tranzitivních grafů jsou stejné jako v předchozí verzi algoritmu – viz Obr: 4-7.

Vyhodnocení výsledků druhé změny algoritmu Třetí verze algoritmu má v oblasti asymetrických isomorfních grafů přibližně 45krát rychlejší odezvu než základní verze algoritmu. Třetí verze algoritmu má v oblasti asymetrických neisomorfních grafů stejně rychlou odezvu jako předchozí verze algoritmu a podstatně rychlejší než základní verze. Třetí verze algoritmu je v oblasti isomorfních vrcholově tranzitivních grafů podstatně lepší než obě předchozí verze algoritmu - má přijatelné doby odezvy v celém testovaném rozsahu počtu uzlů hustot grafů. Rychlost třetí verze algoritmu je v oblasti neisomorfních vrcholově tranzitivních grafů srovnatelná s předchozí verzí algoritmu.

4.1.4. Třetí změna algoritmu – zjemnění rozkladu uzlů při tvorbě permutace V této kapitole je zobrazený a posouzený vliv třetí změny algoritmu na rychlost řešení problému isomorfismu grafů (podrobnosti o algoritmu viz kap. 3.1.4). Jsou zde zobrazené/prezentované výsledky měření doby odezvy změněného programu (algoritmu) v závislosti na vzrůstajícím počtu uzlů a vzrůstající hustotě uzlů: - pro asymetrické isomorfní grafy, - pro asymetrické neisomorfní grafy,

39

- pro vrcholově tranzitivní isomorfní grafy, - pro vrcholově tranzitivní neisomorfní grafy.


Obr: 4-12 Třetí změna algoritmu – asymetrické isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Tvar naměřených křivek se oproti předchozí verzi nezměnil, doba odezvy se poněkud zkrátila u vyšších počtů uzlů. To je způsobeno zjemněním rozkladu uzlů, které bylo přidáno do této verze algoritmu (algoritmus zjemnění viz kap 3.1.4).

40


Obr: 4-13 Třetí změna algoritmu – asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu. Tvar křivek i doby odezvy jsou stejné jako v předchozí verzi algoritmu (viz Obr: 4-9).

Vrcholově tranzitivní isomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních vrcholově tranzitivních grafů. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů.

Obr: 4-14 Třetí změna algoritmu – vrcholově tranzitivní isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s počtem uzlů grafu a s hustotou grafu.

41

Tato verze algoritmu má u isomorfních vrcholově tranzitivních grafů přijatelné doby odezvy v celém testovaném rozsahu počtu uzlů a v celém rozsahu hustot.


Obr: 4-15 Třetí změna algoritmu – vrcholově tranzitivní neisomorfní grafy Doby odezvy v případě neisomorfní dvojice vrcholově tranzitivních grafů jsou oproti předchozí verzi zhruba o 30 % kratší s výjimkou malých řídkých grafů (grafy do 200 uzlů o hustotě 20 %) – viz Obr: 4-11.

Vyhodnocení výsledků třetí změny algoritmu Čtvrtá verze algoritmu má oproti předchozí verzi v oblasti asymetrických isomorfních grafů poněkud kratší dobu odezvy u vyšších počtů uzlů. Čtvrtá verze algoritmu má v oblasti asymetrických neisomorfních grafů stejně rychlou odezvu jako předchozí verze algoritmu. Čtvrtá verze algoritmu je v oblasti isomorfních vrcholově tranzitivních grafů stejně rychlá jako předchozí verze algoritmu. Čtvrtá verze algoritmu je oproti předchozí verzi v oblasti neisomorfních vrcholově tranzitivních grafů zhruba o 30 % rychlejší s výjimkou malých řídkých grafů (grafy do 200 uzlů o hustotě 20 %).

4.1.5. Výběr nejrychlejší verze algoritmu Jsou zde porovnány výsledky měření doby odezvy všech čtyř verzí algoritmu pro jednotlivé kategorie grafů: - pro asymetrické isomorfní grafy, - pro asymetrické neisomorfní grafy, 42

- pro vrcholově tranzitivní isomorfní grafy, - pro vrcholově tranzitivní neisomorfní grafy. Pro asymetrické isomorfní grafy dává nejlepší výsledky poslední verze algoritmu. Oproti základní verzi má mnohem kratší doby odezvy, oproti druhé verzi je použitelná i pro větší počet uzlů (víc než 80 uzlů) oproti třetí verzi je zde malé zrychlení. Pro asymetrické neisomorfní grafy jsou druhá, třetí a čtvrtá verze stejně rychlé, pouze první verze je výrazně pomalejší. Pro vrcholově tranzitivní isomorfní grafy první verze algoritmu není použitelná. Druhá verze je použitelná omezeně pouze pro velmi řídké grafy. Třetí a čtvrtá verze jsou použitelné v celém rozsahu testovaných počtu uzlů a v celém rozsahu testovaných hustot a mají přibližně stejné doby odezvy. Pro vrcholově tranzitivní neisomorfní grafy jsou první tři verze algoritmu přibližně stejné. Čtvrtá verze algoritmu je oproti třem předchozím výrazně rychlejší, zhruba o 30 %. Celkově vychází z porovnání ve všech čtyřech kategoriích nejlépe čtvrtá verze algoritmu.

4.2. POROVNÁNÍ ALGORITMU ZALOŽENÉHO NA POHLEDECH NA GRAF S PROGRAMEM NAUTY Cílem této kapitoly je porovnat nejrychlejší verzi algoritmu založeného na pohledech na graf s algoritmem programu Nauty. Pro grafy s hustotou nad 50 % jde řešit problém isomorfismu pomocí doplňku grafu. Isomorfismus nalezený na doplňcích grafů je isomorfismem i pro původní grafy. Protože se při testování ukázalo, že doby odezvy programu Nauty pro grafy o hustotách blízkých 100 % jsou delší než doby odezvy pro grafy o hustotách blízkých 0 %, provádí se testy i pro grafy o hustotách větších než 50 %. Grafy tvořící testovací data jsou rozděleny do čtyř kategorií: - asymetrické isomorfní grafy, - asymetrické neisomorfní grafy, - vrcholově tranzitivní isomorfní grafy, - vrcholově tranzitivní neisomorfní grafy. V každé kategorii jsou grafy o počtu uzlů 100, 200, 300, 400, 500, 600, 700, 800 a o hustotě grafu 20 %, 50 %, 90 % a také grafy o hustotách blízkých 0 % (Möbiův žebřík) a grafy o hustotách blízkých 100 % („klika mínus kružnice“). Výsledky jsou prezentovány formou grafů – naměřená data jsou v přílohách. Program Nauty implementovaný v jazyce c je vysoce optimalizovaný - implementace není objektově orientovaná, využívá makra, graf je uložený v poli bitů, využívá se celé délky slova procesoru, využívá se více procesorů najednou. To vše snižuje paměťové nároky a zároveň zvyšuje rychlost programu Nauty. Algoritmus založený na pohledech na graf je implementovaný v jazyce Java objektově orientovaným způsobem.

43

Aby se odstínily výše uvedené implementační vlivy, neporovnávají se absolutní časy (doby odezvy), ale relativní prodloužení odezvy po přidání jednoho uzlu při konstantní hustotě grafu. Relativní prodloužení odezvy na jeden uzel = (time(uzly(i+1)) - time(uzly(i))) / time(uzly(i)) / (uzly(i+1) - uzly(i)).

4.2.1. Porovnání pro asymetrické isomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních asymetrických grafů pomocí programu Nauty. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha A: Nauty - asymetrické isomorfní grafy.

Obr: 4-16 Nauty – doba odezvy pro asymetrické isomorfní grafy Z grafu je zřejmé, že doba odezvy programu Nauty vzrůstá s počtem uzlů grafu a s hustotou grafu.

44

V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních asymetrických grafů pomocí algoritmu založeného na pohledech na graf. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha B: Pohledy na graf - asymetrické isomorfní grafy.

Obr: 4-17 Pohledy na graf - doba odezvy pro asymetrické isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s hustotou grafu a maximálních hodnot nabývá pro grafy o hustotě 50 %. Doby odezvy pro grafy o hustotě 90 % jsou kratší než u grafů o hustotě 20 %, protože u grafů o hustotě větší než 90 % se problém isomorfismu řeší pro doplňky grafů.

45

V následujícím grafu je zobrazené relativní prodloužení doby odezvy programu Nauty způsobené zvětšením grafu o jeden uzel. Relativní prodloužení doby odezvy je počítáno ze zdrojových dat pro graf na Obr: 4-16 podle vzorce uvedeného na konci úvodní části kapitoly 4.2.

Obr: 4-18 Nauty – relativní prodlužování doby odezvy na asymetrických isomorfních grafech Z grafu je zřejmé, že pro grafy všech zkoumaných hustot (20 %, 50 %, 90 %) je průběh prodlužování doby odezvy podobný. K největšímu relativnímu prodloužení doby odezvy dochází při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. Pro uzly v rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy zhruba poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotě 0,3 % na uzel.

46

V následujícím grafu je zobrazené relativní prodloužení doby odezvy algoritmu založeného na pohledech na graf způsobené zvětšením grafu o jeden uzel. Relativní prodloužení doby odezvy je počítáno ze zdrojových dat pro graf na Obr: 4-17 podle vzorce uvedeného na konci úvodní části kapitoly 4.2.

Obr: 4-19 Pohledy na graf – relativní prodlužování doby odezvy na asymetrických isomorfních grafech Pro grafy o hustotách 20 % dochází k největšímu relativnímu prodloužení doby odezvy (o 1,8 % na uzel) pro grafy v rozmezí 100 až 200 uzlů. V rozmezí 200 až 800 uzlů relativní prodlužování doby odezvy vytrvale klesá až k hodnotě 0,3 % na uzel. Pro grafy o hustotě 50 % relativní prodloužení doby odezvy v intervalu 100 až 300 uzlů zvolna klesá (pokles od 2,3 do 2,2 % na uzel). V rozmezí 300 až 400 uzlů relativní prodloužení doby odezvy kleslo víc než dvakrát a dále v rozmezí uzlů 400 až 800 relativní prodloužení doby odezvy zvolna klesá až k hodnotě 0,3 % na uzel. Pro grafy o hustotě 90 % relativní prodloužení doby odezvy na začátku zvolna klesá v rozmezí 100 až 500 uzlů. Pouze v rozmezí 500 až 700 uzlů mírně kolísá.

Shrnutí výsledků Z porovnání grafů na Obr: 4-18 a na Obr: 4-19 plyne: -

křivky pro grafy o hustotách 20 % nabývají podobných hodnot, přičemž hodnoty relativního prodlužování doby odezvy v programu Nauty jsou menší.

-

pro grafy o hustotách 50 % jsou hodnoty relativního prodlužování doby odezvy v programu Nauty menší,

-

pro grafy o hustotách 90 % jsou hodnoty relativního prodlužování doby odezvy menší u algoritmu založeného na pohledech na graf v rozmezí 100 až 300 uzlů, v rozmezí 300 až 400 uzlů jsou hodnoty podobné a v rozmezí 400 až 800 uzlů jsou hodnoty relativního prodlužování doby odezvy v programu Nauty menší.

47

4.2.2. Porovnání pro asymetrické neisomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních asymetrických grafů pomocí programu Nauty. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha C: Nauty - asymetrické neisomorfní grafy.

Obr: 4-20 Nauty – doba odezvy pro asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy programu Nauty vzrůstá s počtem uzlů grafu a s hustotou grafu. V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních asymetrických grafů pomocí algoritmu založeného na pohledech na graf. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha D: Pohledy na graf - asymetrické neisomorfní grafy.

Obr: 4-21 Pohledy na graf - doba odezvy pro asymetrické neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s hustotou grafu a maximálních hodnot nabývá pro grafy o hustotě 50 %. V následujícím grafu je zobrazené relativní prodloužení doby odezvy programu Nauty způsobené zvětšením grafu o jeden uzel. Relativní prodloužení doby odezvy je počítáno

48

ze zdrojových dat pro graf na Obr: 4-20 podle vzorce uvedeného na konci úvodní části kapitoly 4.2.

Obr: 4-22 Nauty – relativní prodlužování doby odezvy na asymetrických neisomorfních grafech Z grafu je zřejmé, že pro grafy všech zkoumaných hustot (20 %, 50 %, 90 %) je průběh prodlužování doby odezvy podobný. K největšímu relativnímu prodloužení doby odezvy dochází při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. Pro uzly v rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy zhruba poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotě 0,3 % na uzel.

49


Obr: 4-23 Pohledy na graf – relativní prodlužování doby odezvy na asymetrických neisomorfních grafech Pro grafy o hustotách 20 % a 90 % relativní prodloužení doby odezvy při přidávání uzlů do grafu pozvolna klesá v celém rozmezí s mírnou odchylkou v rozmezí 200 až 400 uzlů pro hustotu 90 %. Pro grafy o hustotě 50 % relativní prodloužení doby odezvy rovnoměrně klesá v celém rozmezí až k hodnotě 0,3 % na uzel. Pouze v intervalu 300 až 500 uzlů je malá odchylka.


-

-

křivky pro grafy o hustotách 20 % mají podobný tvar a nabývají podobných hodnot, přičemž hodnoty relativního prodlužování doby odezvy programu Nauty jsou větší v rozmezí 100 až 300 uzlů a menší v rozmezí 300 až 800 uzlů, pro grafy o hustotách 50 % jsou hodnoty relativního prodlužování doby odezvy v programu Nauty menší, ale algoritmus založený na pohledech na graf se hodnotám Nauty postupně přibližuje a v rozmezí 700 až 800 uzlů se s nimi srovná, pro grafy o hustotách 90 % jsou hodnoty relativního prodlužování doby odezvy menší u algoritmu založeného na pohledech na graf v rozmezí 100 až 300 uzlů, v rozmezí 300 až 800 uzlů se hodnoty srovnají.

4.2.3. Porovnání pro vrcholově tranzitivní isomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních vrcholově tranzitivních grafů pomocí programu 50

Nauty. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha E: Nauty - vrcholově tranzitivní isomorfní grafy.

Obr: 4-24 Nauty – doba odezvy pro vrcholově tranzitivní isomorfní grafy Z grafu je zřejmé, že doba odezvy programu Nauty pro grafy různých hustot leží v pásmu ohraničeném shora křivkou pro grafy tvaru „klika mínus kružnice“ a ohraničeném zdola křivkou pro grafy tvaru „Möbiův žebřík“. V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár isomorfních vrcholově tranzitivních grafů pomocí algoritmu založeného na pohledech na graf. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha F: Pohledy na graf - vrcholově tranzitivní isomorfní grafy.

Obr: 4-25 Pohledy na graf - doba odezvy pro vrcholově tranzitivní isomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s hustotou grafu a maximálních hodnot nabývá pro grafy o hustotě 50 %. Nejkratší jsou doby odezvy pro grafy o hustotách blízkých 0 % nebo 100 %. V následujícím grafu je zobrazené relativní prodloužení doby odezvy programu Nauty způsobené zvětšením grafu o jeden uzel. Relativní prodloužení doby odezvy je počítáno

51

ze zdrojových dat pro graf na Obr: 4-24 podle vzorce uvedeného na konci úvodní části kapitoly 4.2.

Obr: 4-26 Nauty – relativní prodlužování doby odezvy na vrcholově tranzitivních isomorfních grafech Z grafu je zřejmé, že k největšímu relativnímu prodloužení doby odezvy dochází při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. Pro uzly v rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy zhruba poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotám okolo 0,4 % na uzel.

52


Obr: 4-27 Pohledy na graf – relativní prodlužování doby odezvy na vrcholově tranzitivních isomorfních grafech Pro grafy o hustotách 20 % a 50 % dochází k největšímu relativnímu prodloužení doby odezvy při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. V rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy zhruba poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotě 0,4 % na uzel. Pro grafy o hustotách 10 % a 90 % relativní prodloužení doby odezvy kolísá v rozmezí od 0,4 % do 1,3 % na jeden uzel. Zvláštním případem jsou grafy o hustotách blízkých 0 % a 100 %, pro které nabývá relativní prodloužení doby odezvy velmi nízkých hodnot v rozmezí od 0 % do 0,6 % na jeden uzel.


-

křivky pro grafy o hustotách 20 % a 50 % mají podobný tvar a nabývají podobných hodnot, avšak pokles hodnot není rovnoměrný; hodnoty relativního prodlužování doby odezvy programu Nauty kolísají v blízkosti hodnot programu založeného na pohledech na graf, pro grafy o hustotách 90 % v rozmezí 100 až 400 uzlů jsou hodnoty relativního prodlužování doby odezvy u algoritmu založeného na pohledech na graf menší než u programu Nauty, v rozmezí 400 až 800 uzlů je tomu naopak,

53

-

pro grafy o hustotách blízkých 0 % (Möbiův žebřík) a blízkých 100 % („klika mínus kružnice“) jsou hodnoty relativního prodlužování doby odezvy podstatně menší u algoritmu založeného na pohledech na graf skoro v celém rozmezí 100 až 800 uzlů.

4.2.4. Porovnání pro vrcholově tranzitivní neisomorfní grafy V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních vrcholově tranzitivních grafů pomocí programu Nauty. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha G: Nauty - vrcholově tranzitivní neisomorfní grafy.

Obr: 4-28 Nauty – doba odezvy pro vrcholově tranzitivní neisomorfní grafy Z grafu je zřejmé, že doba odezvy programu Nauty vzrůstá s počtem uzlů grafu a s hustotou grafu.

54

V následujícím grafu je zobrazená průměrná doba odezvy při řešení problému isomorfismu pro jeden pár neisomorfních vrcholově tranzitivních grafů pomocí algoritmu založeného na pohledech na graf. Každá průměrná hodnota je vypočítaná jako průměr za 15 párů grafů. Zdrojová data grafu jsou v Příloha H: Pohledy na graf - vrcholově tranzitivní neisomorfní grafy.

Obr: 4-29 Pohledy na graf - doba odezvy pro vrcholově tranzitivní neisomorfní grafy Z grafu je zřejmé, že doba odezvy vzrůstá s hustotou grafu a maximálních hodnot nabývá pro grafy o hustotě 50 %.

55

V následujícím grafu je zobrazené relativní prodloužení doby odezvy programu Nauty způsobené zvětšením grafu o jeden uzel. Relativní prodloužení doby odezvy je počítáno ze zdrojových dat pro graf na Obr: 4-28 podle vzorce uvedeného na konci úvodní části kapitoly 4.2.

Obr: 4-30 Nauty – relativní prodlužování doby odezvy na vrcholově tranzitivních neisomorfních grafech Z grafu je zřejmé, že k největšímu relativnímu prodloužení doby odezvy dochází při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. Pro uzly v rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy méně než poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotě 0,4 % na uzel.

56


Obr: 4-31 Pohledy na graf – relativní prodlužování doby odezvy na vrcholově tranzitivních neisomorfních grafech Pro grafy všech zkoumaných hustot dochází k největšímu relativnímu prodloužení doby odezvy při přidávání uzlů do grafu v rozmezí 100 až 200 uzlů. V rozmezí 200 až 300 uzlů je relativní prodlužování doby odezvy méně než poloviční (oproti rozmezí 100 až 200 uzlů). V dalších rozmezích počtu uzlů relativní prodloužení doby odezvy na jeden uzel dále klesá, ale již pozvolněji až k hodnotám okolo 0,6 % na uzel.

Shrnutí výsledků Z porovnání grafů na Obr: 4-30 a na Obr: 4-31 plyne, že křivky pro všechny zkoumané hustoty mají podobný tvar. Hodnoty relativního prodlužování doby odezvy pro 100 až 200 uzlů jsou v programu Nauty téměř dvakrát menší, ale tento rozdíl se s rostoucím počtem uzlu zmenšuje.

57

5. ZÁVĚR V této diplomové práci je navržen algoritmus na řešení problému isomorfismu grafů a ten je porovnán s programem Nauty. V kapitole 3 jsou navrženy čtyři verze algoritmu na řešení problému isomorfismu grafů. Všechny čtyři verze jsou založené na pohledech na graf. V kapitole 4.1 je porovnána rychlost jednotlivých verzí algoritmu ve čtyřech kategoriích grafů: asymetrické isomorfní, asymetrické neisomorfní, vrcholově tranzitivní isomorfní a vrcholově tranzitivní neisomorfní. Porovnání jsou provedena pro různé počty uzlů a pro různé hustoty grafů. Jako nejrychlejší je vybrána čtvrtá verze algoritmu (popis algoritmu viz kap. 3.1.4). Kapitola 4.2 obsahuje porovnání nejrychlejší verze algoritmu založeného na pohledech na graf s programem Nauty. Porovnává se relativní prodloužení doby odezvy po přidání jednoho uzlu při konstantní hustotě grafu. Za lepší se v dané oblasti hustot a počtů uzlů považuje ten algoritmus, jehož relativní prodloužení doby odezvy nabývá v této oblasti menších hodnot. V kategorii asymetrických isomorfních grafů je algoritmus založený na pohledech lepší pro grafy o velké hustotě pro počty uzlů méně než 400. Pro řídké grafy (např.: hustota 20 %) jsou algoritmy srovnatelné. V ostatních je rychlejší algoritmus v programu Nauty. V kategorii asymetrických neisomorfních grafů je algoritmus založený na pohledech lepší pro velmi husté nebo velmi řídké grafy (např.: hustoty 20 % a 90 %) pro počty uzlů do 300. Jinak je lepší algoritmus Nauty s tím, že algoritmus založený na pohledech se s ním pro větší počty uzlů (od 500 uzlů) vyrovná. V kategorii vrcholově tranzitivních isomorfních grafů od 300 uzlů výše mají oba algoritmy podobné hodnoty relativního prodloužení doby odezvy. Výjimkou jsou grafy o hustotách blízkých 0 % a 100 % (Möbiův žebřík, „klika mínus kružnice“), u kterých je podstatně lepší algoritmus založený na pohledech. V kategorii vrcholově tranzitivních neisomorfních grafů je program Nauty pro nízké počty uzlů (100 až 200 uzlů) zhruba dvakrát lepší, avšak tento rozdíl se s rostoucím počtem uzlů postupně neustále zmenšuje, takže v rozmezí 700 až 800 je program Nauty již jen o 50 procent lepší.

58

Literatura [A1] Stephen G. Hartle. McKay’s Canonical Graph Labeling Algorithm. [online]. A. J. Radcliffe. [citováno 15. 12. 2013]. Dostupné z: http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf. [A2] Brendan D. McKay. Nauty and Traces User’s Guide (Version 2.5). [online]. Adolfo Piperno. 17. 1. 2013, [citováno 4. 12. 2013]. Dostupné z: http://pallini.di.uniroma1.it/Guide.html. [A3] Oleg Eterevsky. Tree Isomorphism Algorithms. [online]. Arist Kojevnikov. [citováno 28. 11. 2013]. Dostupné z: http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf.

59

PŘÍLOHA A: NAUTY - ASYMETRICKÉ ISOMORFNÍ GRAFY Doby odezvy programu jsou v tisícinách sekundy. Hustoty grafu jsou v procentech.

20

100 uzlů hustoty 50

90

0,349 0,260 0,261 0,259 0,319 0,261 0,259 0,260 0,259 0,285 0,259 0,258 0,259 0,259 0,280 0,273 0,258 0,349

0,434 0,347 0,373 0,366 0,401 0,368 0,346 0,347 0,345 0,370 0,345 0,345 0,346 0,345 0,366 0,363 0,345 0,434

0,550 0,460 0,460 0,476 0,499 0,459 0,459 0,459 0,458 0,481 0,458 0,458 0,472 0,459 0,482 0,473 0,458 0,550

20


4,82 4,62 4,60 4,58 4,62 4,60 4,60 4,58 4,63 4,59 4,59 4,58 4,60 4,63 4,58 4,62 4,58 4,82

7,19 6,98 7,09 6,97 7,10 6,97 7,08 7,11 6,99 6,94 7,05 7,07 6,98 6,97 6,97 7,03 6,94 7,19

pár č. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max


20


20


90

0,960 0,864 0,916 0,881 0,900 0,880 0,885 0,901 0,884 0,901 0,878 0,882 0,901 0,878 0,896 0,894 0,864 0,960

1,347 1,222 1,246 1,227 1,231 1,206 1,219 1,221 1,215 1,243 1,211 1,209 1,230 1,219 1,232 1,232 1,206 1,347

1,685 1,605 1,616 1,595 1,603 1,582 1,596 1,591 1,597 1,616 1,606 1,602 1,623 1,601 1,619 1,609 1,582 1,685

90

20


9,00 8,77 8,79 8,76 8,80 8,75 8,80 8,76 8,80 8,77 8,78 8,76 8,78 8,81 8,77 8,79 8,75 9,00

6,77 6,49 6,51 6,47 6,49 6,52 6,47 6,48 6,51 6,46 6,47 6,52 6,53 6,52 6,49 6,51 6,46 6,77

10,20 9,93 9,92 9,87 9,95 9,91 9,92 9,92 9,93 9,89 9,95 9,89 9,97 9,92 10,02 9,95 9,87 10,20

20


90

90

1,895 1,780 1,740 1,790 1,760 1,741 1,765 1,749 1,753 1,771 1,749 1,769 1,755 1,776 1,758 1,770 1,740 1,895

2,754 2,648 2,601 2,615 2,615 2,611 2,621 2,600 2,609 2,634 2,607 2,609 2,620 2,633 2,609 2,626 2,600 2,754

3,499 3,368 3,336 3,386 3,337 3,349 3,341 3,328 3,383 3,380 3,353 3,333 3,329 3,351 3,341 3,361 3,328 3,499

3,226 3,060 3,065 3,057 3,039 3,042 3,053 3,042 3,057 3,033 3,070 3,054 3,045 3,038 3,033 3,061 3,033 3,226

4,730 4,619 4,595 4,590 4,542 4,553 4,553 4,768 4,696 4,534 4,556 4,570 4,564 4,537 4,536 4,596 4,534 4,768

5,868 5,729 5,693 5,704 5,691 5,742 5,711 5,689 5,698 5,679 5,727 5,700 5,709 5,696 5,684 5,715 5,679 5,868

90

20


90

20


12,71 12,56 12,84 12,44 12,44 12,41 12,42 12,46 12,42 12,43 12,45 12,40 12,42 12,42 12,42 12,48 12,40 12,84

9,07 8,83 8,82 8,76 8,83 8,77 8,78 8,77 8,79 8,74 8,80 8,80 8,78 8,77 8,81 8,81 8,74 9,07

13,75 13,40 13,46 13,44 13,42 13,40 13,43 13,49 13,50 13,43 13,45 13,43 13,39 13,55 13,45 13,47 13,39 13,75

90

17,07 16,82 16,82 16,81 16,78 16,81 16,79 16,85 16,80 16,79 16,81 16,77 16,79 16,84 16,78 16,82 16,77 17,07

11,69 11,34 11,35 11,37 11,31 11,40 11,32 11,42 11,53 11,39 11,47 11,35 11,43 11,44 11,41 11,42 11,31 11,69

17,81 17,40 17,42 17,47 17,43 17,45 17,43 17,43 17,46 17,46 17,80 17,42 17,43 17,43 17,45 17,49 17,40 17,81

22,06 21,65 21,67 21,68 21,66 21,72 21,70 21,65 21,68 21,71 21,68 21,67 21,66 21,71 21,65 21,70 21,65 22,06

60

PŘÍLOHA B: POHLEDY NA GRAF - ASYMETRICKÉ ISOMORFNÍ GRAFY Doby odezvy programu jsou v sekundách. Hustoty grafu jsou v procentech. pár č. 20 1 0,401 2 0,056 3 0,045 4 0,038 5 0,048 6 0,034 7 0,036 8 0,039 9 0,035 10 0,035 11 0,034 12 0,036 13 0,035 14 0,034 15 0,042 Průměr 0,063 Min 0,034 Max 0,401

pár č. 20 1 2,117 2 1,674 3 1,632 4 1,670 5 1,595 6 1,570 7 1,550 8 1,672 9 1,608 10 1,565 11 1,550 12 1,671 13 1,573 14 1,589 15 1,674 Průměr 1,647 Min 1,550 Max 2,117

100 uzlů hustoty 50 0,559 0,117 0,102 0,098 0,102 0,093 0,103 0,098 0,131 0,076 0,073 0,075 0,072 0,074 0,078 0,123 0,072 0,559 500 uzlů hustoty 50 4,956 4,644 4,555 4,661 4,491 4,742 4,652 4,418 4,645 4,412 4,521 4,534 5,721 4,246 4,425 4,642 4,246 5,721

90 0,278 0,062 0,029 0,029 0,046 0,022 0,021 0,023 0,021 0,022 0,019 0,019 0,019 0,022 0,019 0,044 0,019 0,278

90 0,957 0,778 0,497 0,754 0,487 0,606 0,643 0,476 0,674 0,492 0,695 0,480 0,576 0,646 0,472 0,616 0,472 0,957

20 0,579 0,223 0,177 0,164 0,210 0,132 0,127 0,132 0,200 0,125 0,126 0,124 0,127 0,160 0,127 0,182 0,124 0,579

200 uzlů hustoty 50 0,872 0,485 0,358 0,364 0,356 0,338 0,363 0,348 0,378 0,334 0,375 0,343 0,379 0,339 0,393 0,402 0,334 0,872

20 2,982 2,595 2,512 2,586 2,446 2,505 2,442 2,490 2,453 2,713 2,421 2,690 2,486 2,623 2,430 2,558 2,421 2,982

600 uzlů hustoty 50 7,276 7,026 6,810 6,911 7,110 6,761 6,892 7,100 7,779 6,794 6,856 6,961 6,647 6,619 6,903 6,963 6,619 7,779

90 0,516 0,107 0,079 0,077 0,078 0,074 0,071 0,087 0,129 0,062 0,057 0,061 0,059 0,058 0,061 0,105 0,057 0,516

90 1,551 1,376 1,205 1,062 1,216 1,175 1,022 1,216 1,197 1,014 1,191 1,203 1,037 1,179 1,193 1,189 1,014 1,551

20 0,841 0,542 0,337 0,481 0,524 0,335 0,445 0,319 0,487 0,322 0,415 0,410 0,323 0,473 0,323 0,439 0,319 0,841

300 uzlů hustoty 50 1,642 1,361 1,257 1,226 1,438 1,409 1,344 1,272 1,247 1,346 1,298 1,249 1,372 1,323 1,267 1,337 1,226 1,642

20 4,180 3,836 3,730 3,771 3,702 3,616 3,706 3,678 3,713 3,663 3,690 3,661 3,594 3,601 3,668 3,721 3,594 4,180

700 uzlů hustoty 50 10,714 10,073 10,004 10,026 10,194 11,760 9,663 9,821 9,674 10,005 9,771 10,827 9,924 9,794 10,097 10,156 9,663 11,760

90 0,607 0,209 0,176 0,168 0,228 0,172 0,142 0,138 0,203 0,142 0,143 0,141 0,141 0,181 0,137 0,195 0,137 0,607

90 1,886 1,712 1,554 1,611 1,611 1,447 1,567 1,588 1,604 1,591 1,433 1,567 1,567 1,602 1,571 1,594 1,433 1,886

20 1,373 1,039 0,903 1,058 0,849 0,888 0,943 0,953 0,908 0,914 1,051 0,865 0,920 0,929 0,974 0,971 0,849 1,373

400 uzlů hustoty 50 2,891 2,744 2,615 2,672 2,496 2,672 2,453 2,551 2,566 2,488 2,636 2,487 2,686 2,520 2,642 2,608 2,453 2,891

90 0,661 0,368 0,419 0,292 0,319 0,387 0,276 0,276 0,300 0,264 0,374 0,268 0,263 0,380 0,273 0,341 0,263 0,661

20 5,465 5,020 4,994 4,896 4,927 5,184 4,968 4,946 5,172 5,105 4,958 5,040 5,717 4,919 4,845 5,077 4,845 5,717

800 uzlů hustoty 50 14,254 13,810 13,578 13,626 16,711 13,522 13,345 13,611 14,936 13,122 13,212 13,469 14,933 13,565 13,604 13,953 13,122 16,711

90 2,785 2,366 2,339 2,347 2,393 2,338 2,358 2,269 2,373 2,302 2,391 2,391 2,313 2,270 2,333 2,371 2,269 2,785

61

PŘÍLOHA C: NAUTY - ASYMETRICKÉ NEISOMORFNÍ GRAFY Doby odezvy programu jsou v tisícinách sekundy. Hustoty grafu jsou v procentech.

20


90

0,311 0,223 0,220 0,227 0,250 0,228 0,226 0,232 0,231 0,232 0,231 0,231 0,230 0,229 0,275 0,238 0,220 0,311

0,394 0,304 0,302 0,304 0,307 0,307 0,305 0,308 0,305 0,310 0,314 0,304 0,304 0,301 0,342 0,314 0,301 0,394

0,545 0,428 0,429 0,441 0,436 0,429 0,437 0,444 0,433 0,427 0,434 0,425 0,434 0,424 0,478 0,443 0,424 0,545

20


4,58 4,36 4,37 4,35 4,36 4,36 4,36 4,36 4,40 4,37 4,38 4,36 4,39 4,40 4,39 4,39 4,35 4,58

6,97 6,74 6,73 6,73 6,73 6,71 6,74 6,70 6,75 6,73 6,71 6,75 6,74 6,73 6,78 6,75 6,70 6,97



20


20


90

0,896 0,776 0,777 0,753 0,770 0,761 0,820 0,774 0,800 0,793 0,754 0,765 0,790 0,784 0,806 0,788 0,753 0,896

1,231 1,130 1,137 1,122 1,125 1,131 1,152 1,124 1,131 1,147 1,126 1,125 1,131 1,121 1,163 1,140 1,121 1,231

1,584 1,503 1,492 1,511 1,527 1,465 1,489 1,485 1,514 1,487 1,485 1,501 1,499 1,513 1,567 1,508 1,465 1,584

90

20


8,69 8,55 8,49 8,44 8,45 8,53 8,49 8,43 8,48 8,55 8,56 8,51 8,52 8,51 8,51 8,51 8,43 8,69

6,50 6,25 6,20 6,20 6,27 6,24 6,22 6,24 6,25 6,20 6,24 6,27 6,20 6,26 6,26 6,25 6,20 6,50

9,91 9,62 9,65 9,60 9,64 9,62 9,64 9,60 9,63 9,60 9,62 9,63 9,68 9,62 9,66 9,65 9,60 9,91

20


90

90

1,779 1,665 1,633 1,682 1,631 1,652 1,648 1,670 1,638 1,637 1,676 1,627 1,676 1,634 1,691 1,663 1,627 1,779

2,589 2,491 2,463 2,488 2,474 2,475 2,465 2,473 2,450 2,489 2,489 2,470 2,485 2,472 2,508 2,485 2,450 2,589

3,327 3,202 3,180 3,178 3,183 3,195 3,184 3,174 3,191 3,225 3,188 3,194 3,159 3,181 3,212 3,198 3,159 3,327

3,023 2,832 2,857 2,831 2,877 2,851 2,834 2,813 2,831 2,847 2,825 2,849 2,864 2,839 2,874 2,857 2,813 3,023

4,516 4,357 4,321 4,322 4,344 4,343 4,354 4,331 4,345 4,347 4,354 4,362 4,334 4,351 4,415 4,360 4,321 4,516

5,671 5,543 5,551 5,506 5,512 5,522 5,524 5,494 5,507 5,576 5,531 5,524 5,577 5,527 5,555 5,541 5,494 5,671

90

20


90

20


90

12,48 12,19 12,15 12,18 12,12 12,16 12,15 12,13 12,07 12,13 12,13 12,08 12,14 12,06 12,12 12,15 12,06 12,48

8,75 8,43 8,45 8,41 8,43 8,40 8,40 8,42 8,42 8,42 8,40 8,46 8,38 8,43 8,45 8,44 8,38 8,75

13,53 13,10 13,08 13,08 13,05 13,05 13,08 13,09 13,11 13,06 13,07 13,06 13,05 13,04 13,11 13,10 13,04 13,53

16,68 16,31 16,36 16,32 16,36 16,30 16,33 16,32 16,40 16,29 16,30 16,35 16,68 16,38 16,40 16,39 16,29 16,68

11,27 10,95 10,97 10,98 10,96 10,90 10,97 10,93 10,93 10,95 10,96 10,96 10,94 10,97 11,05 10,98 10,90 11,27

17,39 17,03 17,06 17,12 17,03 17,03 17,05 17,06 17,10 17,04 17,07 17,04 17,09 17,06 17,12 17,09 17,03 17,39

21,66 21,41 21,32 21,38 21,31 21,38 21,34 21,38 21,26 21,43 21,43 21,42 21,36 21,35 21,38 21,39 21,26 21,66

62

PŘÍLOHA D: POHLEDY NA GRAF - ASYMETRICKÉ NEISOMORFNÍ GRAFY Doby odezvy programu jsou v sekundách. Hustoty grafu jsou v procentech. pár č. 20 1 0,161 2 0,048 3 0,008 4 0,008 5 0,010 6 0,008 7 0,009 8 0,007 9 0,010 10 0,008 11 0,009 12 0,008 13 0,015 14 0,006 15 0,006 Průměr 0,021 Min 0,006 Max 0,161


100 uzlů hustoty 50 0,234 0,037 0,037 0,017 0,015 0,017 0,017 0,016 0,021 0,016 0,015 0,015 0,015 0,016 0,015 0,033 0,015 0,234

500 uzlů hustoty 50 0,987 0,841 0,995 0,795 0,787 0,923 0,787 1,046 0,785 0,803 1,034 0,726 0,853 0,868 0,846 0,872 0,726 1,046

90 0,097 0,104 0,006 0,009 0,005 0,006 0,005 0,005 0,006 0,005 0,005 0,007 0,005 0,005 0,005 0,018 0,005 0,104

90 0,305 0,153 0,112 0,118 0,102 0,111 0,116 0,115 0,100 0,120 0,118 0,121 0,103 0,096 0,095 0,126 0,095 0,305

20 0,218 0,063 0,035 0,036 0,038 0,024 0,025 0,025 0,027 0,024 0,024 0,024 0,025 0,023 0,025 0,042 0,023 0,218

200 uzlů hustoty 50 0,285 0,104 0,090 0,079 0,075 0,073 0,071 0,072 0,074 0,070 0,071 0,069 0,077 0,072 0,069 0,090 0,069 0,285

20 0,580 0,411 0,384 0,388 0,403 0,355 0,354 0,350 0,457 0,330 0,322 0,333 0,325 0,389 0,375 0,384 0,322 0,580

600 uzlů hustoty 50 1,479 1,661 1,259 1,746 1,250 1,707 1,250 1,428 1,345 1,364 1,337 1,354 1,595 1,340 1,775 1,459 1,250 1,775

90 0,219 0,060 0,017 0,017 0,017 0,017 0,018 0,021 0,015 0,013 0,014 0,014 0,012 0,016 0,013 0,032 0,012 0,219

90 0,407 0,201 0,177 0,182 0,179 0,180 0,169 0,184 0,170 0,157 0,167 0,164 0,156 0,150 0,167 0,187 0,150 0,407

20 0,268 0,099 0,072 0,061 0,063 0,064 0,066 0,060 0,064 0,060 0,061 0,062 0,062 0,059 0,059 0,079 0,059 0,268

300 uzlů hustoty 50 0,405 0,235 0,209 0,207 0,227 0,227 0,220 0,233 0,199 0,191 0,189 0,191 0,197 0,196 0,227 0,224 0,189 0,405

20 0,763 0,593 0,578 0,579 0,539 0,520 0,615 0,532 0,539 0,768 0,540 0,533 0,792 0,529 0,525 0,596 0,520 0,792

700 uzlů hustoty 50 2,000 2,009 2,411 1,800 2,097 1,993 2,258 1,687 1,995 2,338 2,493 1,671 1,997 2,244 2,568 2,104 1,671 2,568

90 0,214 0,075 0,051 0,035 0,036 0,032 0,033 0,034 0,030 0,032 0,031 0,031 0,032 0,032 0,032 0,049 0,030 0,214

90 0,428 0,279 0,236 0,249 0,247 0,358 0,216 0,231 0,227 0,232 0,237 0,376 0,225 0,215 0,221 0,265 0,215 0,428

20 0,310 0,175 0,145 0,146 0,131 0,132 0,127 0,133 0,134 0,168 0,138 0,120 0,121 0,114 0,116 0,147 0,114 0,310

400 uzlů hustoty 50 0,602 0,484 0,470 0,471 0,455 0,441 0,438 0,438 0,438 0,402 0,396 0,395 0,455 0,399 0,399 0,445 0,395 0,602

90 0,231 0,128 0,076 0,068 0,068 0,069 0,072 0,070 0,063 0,063 0,064 0,063 0,064 0,066 0,065 0,082 0,063 0,231

20 0,996 0,809 0,907 0,758 1,159 0,764 0,751 0,988 0,761 1,131 0,762 0,759 0,980 0,766 1,144 0,896 0,751 1,159

800 uzlů hustoty 50 2,699 2,509 2,532 2,523 2,566 2,950 2,992 2,993 3,013 3,023 3,023 3,018 3,015 2,993 3,008 2,857 2,509 3,023

90 0,573 0,395 0,353 0,356 0,417 0,321 0,303 0,300 0,294 0,338 0,338 0,322 0,298 0,421 0,302 0,355 0,294 0,573

63

PŘÍLOHA E: NAUTY - VRCHOLOVĚ TRANZITIVNÍ ISOMORFNÍ GRAFY Doby odezvy programu jsou v tisícinách sekundy. Hustoty grafu jsou v procentech. 100 uzlů pár č. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

klika Möbiův mínus žebřík kružnice

2,22 2,52 2,56 2,87 2,17 2,13 2,12 2,51 1,73 2,54 2,87 2,11 2,86 2,11 2,51 2,39 1,73 2,87

1,79 1,27 1,52 1,70 1,53 1,48 1,72 1,91 1,72 1,28 1,48 1,27 1,68 1,47 1,73 1,57 1,27 1,91

200 uzlů hustoty

20

50

90

1,80 1,19 1,45 1,17 1,45 1,44 1,66 1,43 1,66 1,46 1,18 1,43 1,42 1,67 1,45 1,46 1,17 1,80

1,49 1,71 1,73 1,71 1,73 1,69 1,70 1,71 1,71 2,03 2,00 2,01 1,99 2,00 2,02 1,82 1,49 2,03

2,41 1,95 2,00 1,96 1,64 2,65 2,65 2,65 2,30 2,34 2,31 1,95 2,31 1,96 1,98 2,20 1,64 2,65


7,83 9,35 9,45 7,62 7,65 9,33 9,36 7,65 7,63 11,04 9,31 9,31 9,37 9,34 7,67 8,79 7,62 11,04

7,64 7,42 7,56 6,33 6,34 7,41 7,43 6,34 6,33 7,44 6,30 6,28 6,35 6,32 5,25 6,72 5,25 7,64

300 uzlů klika Möbiův pár č. mínus žebřík kružnice

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

29,98 29,83 25,05 34,46 24,99 29,63 25,16 34,49 25,09 25,13 34,31 25,05 29,76 20,50 29,72 28,21 20,50 34,49

19,93 16,79 19,75 16,93 16,68 16,71 19,81 16,72 16,74 16,72 13,65 13,66 16,70 16,74 13,68 16,75 13,65 19,93

hustoty 20

50

90

5,81 6,90 5,79 8,17 5,70 6,95 5,66 8,22 5,68 6,95 9,43 6,91 8,21 5,65 8,19 6,95 5,65 9,43

8,35 6,70 6,86 6,69 6,72 8,17 8,18 8,21 8,17 6,70 6,69 6,67 6,70 6,70 6,69 7,21 6,67 8,35

7,12 8,59 8,66 6,97 8,60 8,51 8,48 6,94 8,49 10,08 8,50 10,08 8,51 10,06 8,53 8,54 6,94 10,08

20

hustoty 50

90

43,08 35,91 35,84 28,91 29,34 49,30 49,22 42,41 42,89 42,86 36,05 35,69 36,11 36,01 29,10 38,18 28,91 49,30

33,74 41,15 41,51 41,17 41,26 41,59 41,80 41,31 41,35 48,92 49,34 49,09 49,26 49,00 49,36 43,99 33,74 49,36

46,29 37,34 54,59 55,21 46,13 46,07 63,46 64,47 55,09 54,94 54,67 46,55 72,50 63,86 63,43 54,97 37,34 72,50

400 uzlů

20

hustoty 50

90

17,93 14,55 17,70 21,20 17,71 17,73 21,08 24,37 21,08 17,78 21,06 17,77 24,32 21,06 24,36 19,98 14,55 24,37

20,99 17,06 16,90 20,95 16,97 20,82 20,91 24,71 20,86 17,03 20,85 17,02 20,79 16,99 21,28 19,61 16,90 24,71

27,42 23,09 22,93 23,14 27,22 31,55 31,60 31,58 35,87 27,29 27,35 31,63 27,22 31,57 31,60 28,74 22,93 35,87


51,20 50,90 69,74 50,88 60,62 41,37 60,25 41,57 51,15 60,34 41,58 50,56 60,92 69,97 50,96 54,13 41,37 69,97

46,45 34,28 33,85 33,78 39,95 40,42 40,21 40,13 46,14 27,84 27,61 33,76 27,45 34,09 33,78 35,98 27,45 46,45

64

500 uzlů pár č. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max


104,5 71,2 87,8 71,4 71,4 104,4 120,5 105,0 104,8 87,4 71,3 72,2 87,1 88,2 71,9 87,9 71,2 120,5

60,2 70,4 59,7 70,7 60,1 59,9 48,4 59,8 48,8 59,4 70,5 59,6 59,9 48,2 59,4 59,7 48,2 70,7

600 uzlů

20

hustoty 50

90

51,4 50,9 51,1 51,3 74,0 51,1 51,5 51,5 74,1 51,0 51,0 75,2 50,8 74,6 75,0 59,0 50,8 75,2

72,5 58,1 58,2 85,4 57,8 71,9 72,0 99,4 71,5 58,1 85,3 58,5 84,3 58,1 85,2 71,8 57,8 99,4

80,6 65,4 64,7 65,0 65,2 81,2 80,1 80,4 80,5 65,3 64,4 64,8 64,9 65,4 64,5 70,2 64,4 81,2


162,8 162,7 136,3 136,2 137,3 162,4 136,0 136,0 137,2 136,7 136,6 136,9 110,9 111,6 111,9 136,8 110,9 162,8

96,3 95,6 96,0 78,2 150,6 113,6 113,9 96,4 168,7 113,7 96,0 169,1 95,9 168,3 150,2 120,2 78,2 169,1


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

164,0 208,1 202,3 240,5 239,7 200,4 200,7 239,0 238,1 238,4 275,9 277,0 276,0 276,9 313,8 239,4 164,0 313,8

172,8 144,0 117,4 144,2 144,9 198,2 172,4 199,3 199,9 143,6 172,2 171,9 145,1 143,8 172,2 162,8 117,4 199,9

20

hustoty 50

90

82,2 81,6 138,7 120,3 101,2 81,5 138,8 120,1 101,5 139,5 119,8 100,9 178,7 158,8 138,7 120,2 81,5 178,7

135,5 113,5 113,6 114,3 113,8 156,7 157,1 157,9 157,3 135,2 135,5 136,1 135,8 135,3 135,3 135,5 113,5 157,9

126,6 102,5 101,9 126,4 151,2 127,1 126,5 150,8 176,8 102,7 126,6 150,9 126,8 152,0 175,1 134,9 101,9 176,8

20

hustoty 50

90

179,0 177,7 220,0 261,9 177,8 177,7 219,9 261,8 178,1 220,4 262,5 177,4 305,0 219,9 261,9 220,1 177,4 305,0

337,9 245,2 197,5 244,5 243,7 384,4 337,1 386,0 384,2 244,1 291,4 291,4 244,5 244,6 290,1 291,1 197,5 386,0

268,0 270,2 268,9 216,0 266,7 320,5 319,8 268,3 320,0 319,5 267,8 319,4 266,5 319,5 268,1 285,3 216,0 320,5

800 uzlů

20

hustoty 50

90

181,7 122,2 152,1 180,4 152,0 179,8 210,4 238,8 210,5 150,9 181,6 151,6 210,8 179,8 210,2 180,9 122,2 238,8

170,1 169,0 170,0 169,1 169,7 200,7 202,3 201,4 202,2 200,5 201,9 201,9 202,5 200,4 202,0 190,9 169,0 202,5

224,1 223,7 186,8 188,1 187,4 295,8 258,9 260,3 259,3 258,7 258,6 259,9 223,5 222,7 222,6 235,4 186,8 295,8


392,5 339,0 284,9 284,5 283,5 392,9 339,3 339,5 338,1 284,4 285,9 284,0 230,9 231,2 231,1 302,8 230,9 392,9

250,0 249,6 249,5 289,5 288,7 169,3 169,4 209,0 208,8 169,5 209,2 209,6 208,9 210,3 248,9 222,7 169,3 289,5

65

PŘÍLOHA F: POHLEDY NA GRAF - VRCHOLOVĚ TRANZITIVNÍ ISOMORFNÍ GRAFY Doby odezvy programu jsou v sekundách. Hustoty grafu jsou v procentech. 100 uzlů pár č. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max


0,144 0,081 0,021 0,023 0,022 0,047 0,012 0,010 0,011 0,009 0,011 0,009 0,011 0,009 0,032 0,030 0,009 0,144

0,165 0,023 0,023 0,022 0,024 0,044 0,011 0,011 0,011 0,010 0,012 0,010 0,011 0,025 0,011 0,028 0,010 0,165

10 0,277 0,068 0,034 0,033 0,060 0,023 0,022 0,023 0,031 0,022 0,021 0,022 0,029 0,022 0,022 0,047 0,021 0,277

200 uzlů

hustoty 20 50 0,323 0,056 0,085 0,042 0,039 0,041 0,038 0,042 0,037 0,039 0,039 0,037 0,043 0,037 0,040 0,062 0,037 0,323

0,540 0,121 0,113 0,092 0,094 0,086 0,086 0,113 0,124 0,076 0,071 0,072 0,073 0,072 0,073 0,120 0,071 0,540

90 0,252 0,093 0,031 0,027 0,028 0,051 0,023 0,024 0,032 0,024 0,021 0,023 0,021 0,022 0,021 0,046 0,021 0,252


0,216 0,087 0,025 0,024 0,024 0,044 0,019 0,018 0,016 0,018 0,030 0,017 0,016 0,015 0,017 0,039 0,015 0,216

0,281 0,050 0,071 0,024 0,022 0,022 0,035 0,021 0,020 0,020 0,020 0,029 0,019 0,019 0,021 0,045 0,019 0,281


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

0,274 0,097 0,042 0,059 0,031 0,031 0,041 0,027 0,027 0,026 0,029 0,025 0,025 0,040 0,026 0,053 0,025 0,274

0,270 0,098 0,075 0,035 0,031 0,047 0,031 0,030 0,031 0,031 0,041 0,030 0,029 0,029 0,039 0,057 0,029 0,270

10 0,666 0,245 0,193 0,181 0,174 0,195 0,153 0,140 0,192 0,147 0,160 0,151 0,186 0,143 0,142 0,205 0,140 0,666

0,507 0,119 0,106 0,089 0,092 0,078 0,088 0,119 0,073 0,069 0,062 0,065 0,064 0,065 0,060 0,110 0,060 0,507

hustoty 20 50 0,713 0,325 0,229 0,197 0,238 0,195 0,230 0,194 0,239 0,188 0,226 0,187 0,224 0,189 0,222 0,253 0,187 0,713

0,889 0,629 0,357 0,559 0,347 0,527 0,350 0,532 0,361 0,537 0,348 0,536 0,341 0,496 0,343 0,477 0,341 0,889

90 0,507 0,113 0,092 0,081 0,083 0,083 0,083 0,079 0,108 0,064 0,062 0,063 0,059 0,059 0,058 0,106 0,058 0,507

400 uzlů

hustoty 20 50 1,149 0,729 0,633 0,671 0,579 0,632 0,706 0,575 0,626 0,736 0,574 0,615 0,737 0,572 0,622 0,677 0,572 1,149

10

1,670 1,386 1,420 1,192 1,262 1,405 1,188 1,267 1,403 1,159 1,264 1,387 1,237 1,262 1,375 1,325 1,159 1,670

90 0,633 0,213 0,187 0,178 0,184 0,155 0,137 0,136 0,181 0,135 0,135 0,138 0,187 0,134 0,134 0,191 0,134 0,633


0,289 0,111 0,078 0,044 0,053 0,039 0,040 0,039 0,048 0,041 0,047 0,031 0,032 0,030 0,029 0,063 0,029 0,289

0,297 0,104 0,070 0,047 0,058 0,047 0,047 0,043 0,056 0,063 0,031 0,032 0,032 0,030 0,030 0,066 0,030 0,297

10 0,723 0,413 0,386 0,287 0,380 0,278 0,388 0,287 0,287 0,379 0,274 0,351 0,282 0,380 0,273 0,358 0,273 0,723

hustoty 20 50 1,835 1,411 1,363 1,293 1,324 1,299 1,304 1,284 1,270 1,346 1,350 1,315 1,337 1,340 1,262 1,356 1,262 1,835

2,936 2,698 2,437 2,559 2,387 2,515 2,522 2,581 2,616 2,342 2,512 2,339 2,462 2,607 2,528 2,536 2,339 2,936

90 0,709 0,414 0,347 0,314 0,376 0,293 0,369 0,310 0,350 0,288 0,354 0,291 0,376 0,301 0,374 0,364 0,288 0,709

66

500 uzlů pár č. klika Möbiův mínus žebřík kružnice 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

0,356 0,119 0,097 0,071 0,063 0,073 0,061 0,102 0,043 0,047 0,043 0,041 0,063 0,048 0,069 0,087 0,041 0,356

0,390 0,103 0,092 0,072 0,063 0,062 0,096 0,046 0,051 0,046 0,046 0,046 0,047 0,071 0,047 0,085 0,046 0,390

10 1,092 0,629 0,853 0,811 0,824 0,868 0,786 0,799 0,914 0,890 0,861 0,846 0,922 0,761 0,842 0,847 0,629 1,092

600 uzlů

hustoty 20 50 2,745 2,407 2,305 2,330 2,344 2,275 2,292 2,288 2,319 2,274 2,289 2,350 2,327 2,281 2,322 2,343 2,274 2,745

4,857 4,495 4,611 4,473 4,274 4,340 4,579 4,550 4,614 4,393 4,527 4,468 4,389 5,277 4,310 4,544 4,274 5,277

90 0,984 0,792 0,760 0,510 0,616 0,681 0,761 0,497 0,634 0,650 0,755 0,500 0,626 0,627 0,753 0,676 0,497 0,984


0,411 0,111 0,084 0,078 0,066 0,094 0,055 0,047 0,049 0,047 0,048 0,064 0,049 0,049 0,048 0,087 0,047 0,411

0,437 0,108 0,088 0,081 0,074 0,096 0,053 0,053 0,052 0,052 0,082 0,053 0,051 0,051 0,054 0,092 0,051 0,437


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Průměr Min Max

0,530 0,135 0,109 0,101 0,104 0,088 0,088 0,083 0,121 0,066 0,091 0,067 0,066 0,080 0,069 0,120 0,066 0,530

0,496 0,134 0,117 0,110 0,095 0,090 0,077 0,077 0,105 0,078 0,077 0,075 0,112 0,078 0,075 0,120 0,075 0,496

10 2,639 2,206 2,094 2,100 2,093 2,057 2,046 2,078 2,072 2,089 2,091 2,067 2,059 2,134 2,099 2,128 2,046 2,639

1,821 1,422 1,326 1,308 1,339 1,279 1,312 1,283 1,346 1,272 1,344 1,265 1,324 1,268 1,271 1,345 1,265 1,821

4,097 3,659 3,521 3,606 3,610 3,499 3,513 3,584 3,623 3,602 3,479 3,597 3,551 3,604 3,607 3,610 3,479 4,097

7,319 6,921 6,756 6,759 6,723 6,765 6,770 6,892 7,936 6,859 6,559 6,563 6,764 6,559 6,701 6,856 6,559 7,936

90 1,871 1,488 1,358 1,360 1,351 1,359 1,346 1,367 1,353 1,384 1,405 1,369 1,390 1,376 1,317 1,406 1,317 1,871

800 uzlů

hustoty 20 50 5,975 5,505 5,576 5,727 5,618 5,607 5,502 5,438 5,352 5,411 5,576 5,631 5,606 5,534 5,534 5,573 5,352 5,975

10

hustoty 20 50

10,604 10,114 9,760 9,919 9,988 10,199 10,867 9,536 9,754 9,664 9,783 9,662 11,080 9,594 9,745 10,018 9,536 11,080

90 2,966 2,582 2,494 2,490 2,512 2,490 4,813 2,518 2,497 2,413 2,427 2,474 2,492 2,494 2,512 2,678 2,413 4,813


0,445 0,141 0,112 0,128 0,086 0,073 0,072 0,082 0,073 0,071 0,105 0,077 0,072 0,072 0,094 0,114 0,071 0,445

0,537 0,145 0,124 0,137 0,095 0,084 0,122 0,081 0,082 0,081 0,099 0,082 0,081 0,116 0,081 0,130 0,081 0,537

10 3,388 3,097 3,090 2,879 2,885 2,992 2,989 2,906 2,940 2,988 2,842 2,905 2,990 2,894 2,972 2,984 2,842 3,388

hustoty 20 50 8,222 7,843 7,610 7,582 7,806 7,819 7,535 7,792 7,747 7,728 7,539 7,837 8,610 7,643 7,394 7,780 7,394 8,610

16,255 13,676 14,009 13,473 15,176 13,355 13,021 13,062 14,822 13,322 13,224 13,404 14,978 13,186 13,258 13,881 13,021 16,255

90 5,249 4,900 4,706 4,745 4,778 4,699 4,746 4,674 4,717 4,846 4,674 4,911 4,704 4,822 4,635 4,787 4,635 5,249

67

PŘÍLOHA G: NAUTY - VRCHOLOVĚ TRANZITIVNÍ NEISOMORFNÍ GRAFY Doby odezvy programu jsou v tisícinách sekundy. Hustoty grafu jsou v procentech.

20


90

1,22 1,13 1,13 1,11 1,15 1,13 1,12 1,11 1,10 1,12 1,09 1,09 1,13 1,11 1,14 1,13 1,09 1,22

1,44 1,36 1,34 1,33 1,34 1,34 1,35 1,33 1,34 1,36 1,33 1,34 1,33 1,34 1,37 1,35 1,33 1,44

1,64 1,52 1,55 1,51 1,51 1,52 1,54 1,51 1,50 1,56 1,52 1,51 1,54 1,53 1,54 1,53 1,50 1,64

20


50,5 50,6 51,0 50,6 50,5 50,7 51,0 50,3 50,5 50,5 50,8 50,1 50,5 50,6 50,9 50,6 50,1 51,0

57,9 58,0 57,7 58,0 57,4 57,8 57,8 58,0 57,4 57,6 57,7 58,1 57,2 57,6 57,7 57,7 57,2 58,1



20


20


90

5,70 5,57 5,57 5,56 5,58 5,53 5,55 5,52 5,54 5,55 5,53 5,54 5,53 5,55 5,57 5,56 5,52 5,70

6,75 6,67 6,62 6,66 6,67 6,64 6,60 6,64 6,63 6,64 6,66 6,64 6,63 6,62 6,70 6,65 6,60 6,75

7,05 6,93 6,93 6,93 6,93 6,91 6,93 6,91 6,93 6,92 6,90 6,91 6,91 6,91 6,96 6,93 6,90 7,05

90

20


64,5 64,7 65,0 64,5 64,6 65,0 65,2 64,7 64,7 64,7 65,2 64,2 64,8 64,7 65,4 64,8 64,2 65,4

81,2 81,2 81,2 81,4 81,0 80,8 81,1 81,5 81,2 80,9 81,0 81,3 81,1 81,0 81,0 81,1 80,8 81,5

91,8 91,3 91,3 91,5 91,6 91,3 91,0 91,4 92,1 91,4 91,0 91,7 91,7 91,3 90,9 91,4 90,9 92,1

20


90

90

14,45 14,23 14,25 14,27 14,25 14,22 14,27 14,28 14,26 14,22 14,20 14,18 14,23 14,24 14,28 14,26 14,18 14,45

16,90 16,81 16,78 16,80 16,75 16,78 16,77 16,76 16,71 16,82 16,83 16,77 16,77 16,75 16,79 16,79 16,71 16,90

18,46 18,33 18,33 18,36 18,31 18,33 18,38 18,37 18,33 18,36 18,39 18,35 18,39 18,36 18,43 18,37 18,31 18,46

29,01 28,83 28,76 28,96 28,96 28,74 28,66 28,89 28,72 28,82 28,63 28,99 28,73 28,64 28,59 28,80 28,59 29,01

33,42 33,61 33,15 33,48 33,51 33,16 33,03 33,40 33,19 33,20 33,10 33,40 33,18 33,22 33,10 33,28 33,03 33,61

36,95 37,14 37,06 37,14 36,78 37,11 37,01 37,15 36,83 37,28 37,12 36,86 37,14 37,35 37,18 37,07 36,78 37,35

90

20


90

20


90

101,4 101,4 101,8 101,7 101,2 101,1 101,7 101,6 101,2 101,4 101,6 101,2 101,8 101,4 101,7 101,5 101,1 101,8

122,1 122,2 121,8 122,2 121,9 122,1 121,8 122,2 122,0 122,1 121,6 122,4 121,8 122,5 121,5 122,0 121,5 122,5

136,9 136,1 136,8 136,1 136,7 136,0 136,9 136,5 136,9 136,0 136,8 136,1 137,4 135,9 136,7 136,5 135,9 137,4

151,1 151,7 151,3 151,9 151,2 150,9 150,8 151,3 150,7 151,5 151,1 151,4 151,2 151,2 151,2 151,2 150,7 151,9

177,3 176,7 176,4 176,1 176,7 176,8 177,0 176,4 177,0 176,8 176,8 176,5 176,7 176,5 176,5 176,7 176,1 177,3

195,7 196,0 195,7 195,2 195,1 195,5 195,6 195,3 195,3 195,7 195,6 195,9 195,1 195,8 195,7 195,5 195,1 196,0

214,6 214,1 214,0 213,9 213,8 214,5 213,9 213,7 214,1 214,0 213,9 213,4 214,0 214,3 213,8 214,0 213,4 214,6

68

PŘÍLOHA H: POHLEDY NA GRAF - VRCHOLOVĚ TRANZITIVNÍ NEISOMORFNÍ GRAFY Doby odezvy programu jsou v sekundách. Hustoty grafu jsou v procentech. pár č. 20 1 0,545 2 0,259 3 0,268 4 0,255 5 0,226 6 0,229 7 0,241 8 0,225 9 0,209 10 0,260 11 0,232 12 0,246 13 0,236 14 0,215 15 0,223 Průměr 0,258 Min 0,209 Max 0,545


100 uzlů hustoty 50 0,958 0,701 0,656 0,566 0,689 1,077 0,628 0,808 0,618 0,579 0,585 0,594 0,599 0,582 0,585 0,682 0,566 1,077 500 uzlů hustoty 50 142,88 138,91 139,08 141,50 138,52 141,74 141,34 142,92 137,38 140,33 139,23 136,68 140,59 136,27 138,47 139,72 136,27 142,92

90 0,354 0,109 0,110 0,117 0,113 0,110 0,089 0,099 0,092 0,092 0,094 0,102 0,092 0,094 0,096 0,118 0,089 0,354

90 25,39 24,41 24,21 24,05 23,51 24,45 24,27 24,08 23,83 24,28 24,02 23,61 24,01 23,93 23,79 24,12 23,51 25,39

20 2,952 2,304 2,277 2,151 2,159 2,252 2,245 2,155 2,192 2,520 2,159 2,175 2,145 2,168 2,359 2,281 2,145 2,952

200 uzlů hustoty 50 6,239 5,643 5,635 5,653 6,216 5,662 5,744 5,630 5,630 5,694 5,573 5,705 6,050 5,724 5,708 5,767 5,573 6,239

20 101,48 103,38 99,26 104,44 98,78 99,92 98,87 99,51 100,67 101,92 101,35 102,79 101,75 104,39 102,01 101,37 98,78 104,44

600 uzlů hustoty 50 287,49 286,02 285,36 286,48 288,20 285,86 285,60 288,30 286,34 285,06 285,98 285,87 287,93 288,98 284,95 286,56 284,95 288,98

90 1,320 0,925 0,903 0,922 0,872 0,913 0,889 0,901 0,889 0,889 0,900 0,878 0,916 0,866 0,871 0,924 0,866 1,320

90 50,12 46,59 45,40 46,05 45,36 46,52 45,23 46,12 47,95 45,44 46,20 46,23 46,30 46,77 46,43 46,45 45,23 50,12

20 9,367 8,793 10,761 8,645 8,740 8,968 9,156 8,714 9,029 9,701 8,767 9,651 8,685 8,828 8,724 9,102 8,645 10,761

300 uzlů hustoty 50 23,323 22,426 23,071 22,478 22,555 22,349 22,459 22,338 22,396 22,546 22,345 22,353 22,563 22,592 22,638 22,562 22,338 23,323

20 177,18 167,14 173,09 166,48 168,04 169,41 172,59 168,84 173,08 171,53 171,11 171,54 174,93 176,69 180,06 172,11 166,48 180,06

700 uzlů hustoty 50 511,62 503,47 504,57 501,21 508,02 549,75 589,60 504,10 505,86 511,10 501,12 513,16 509,63 505,02 510,25 515,23 501,12 589,60

90 4,215 3,772 3,636 3,881 3,759 3,755 3,621 3,871 3,765 3,650 3,928 3,771 3,862 3,749 3,738 3,798 3,621 4,215

90 85,11 84,92 86,40 86,50 85,33 85,21 86,62 86,78 84,94 85,46 86,45 85,21 87,25 85,83 87,20 85,95 84,92 87,25

20 29,917 24,136 23,768 24,283 24,682 23,897 23,399 23,880 24,321 23,629 25,304 25,156 24,613 24,871 24,579 24,696 23,399 29,917

400 uzlů hustoty 50 61,907 60,816 60,636 60,619 60,941 60,888 60,213 60,202 61,380 61,113 60,454 60,372 61,315 60,951 60,848 60,844 60,202 61,907

90 10,517 10,401 10,085 10,134 10,216 10,362 10,098 10,109 10,209 10,161 10,399 10,103 10,172 10,304 10,186 10,230 10,085 10,517

20 273,30 279,29 277,40 287,42 284,37 288,29 291,24 295,56 280,37 291,71 288,71 282,28 290,56 280,05 281,28 284,79 273,30 295,56

800 uzlů hustoty 50 869,10 871,37 870,83 918,29 925,63 918,05 911,14 913,22 908,73 909,88 916,71 911,81 909,37 916,08 923,73 906,26 869,10 925,63

90 142,43 132,96 130,65 138,22 136,13 129,10 130,08 136,97 136,89 129,99 138,38 138,86 139,24 145,25 140,27 136,36 129,10 145,25

69

Praktický heuristický isomorfismus grafů

Recommend Documents