| Meno: | Drahomír
|
|---|
| Priezvisko: | Mrózek
|
|---|
| Názov: | Algoritmy pre cyklickú súvislosť grafov
|
|---|
| Vedúci: | prof. RNDr. Martin Škoviera, PhD.
|
|---|
| Rok: | 2016
|
|---|
| Kľúčové slová: | Cyklická súvislosť, atóm cyklickej súvislosti, snark.
|
|---|
| Abstrakt: | Cyklický hranový rez je minimálny hranový rez rozdelujúci graf na 2 komponenty, z
ktorých každý obsahuje cyklus. Cyklická súvislosť je mohutnosť minimálneho cyklic-
kého rezu.Cyklická súvislosť je užtočná vlastnosť grafu pre rôzne oblasti teórie grafov,
napríklad pre štúdium snarkov. Cyklický part je komponent grafu po odstránení mini-
málneho cyklického rezu. Atóm je cyklický part minimálny na inklúziu. Kubické grafy
sú grafy v ktorých každý vrchol má troch susedov. V tejto práci som opísal teoretické
vlastnosti cyklickej súvislosti a atómov cyklickej súvislosti, ukázal niektoré súvislosti
týchto pojmov so štúdiom snarkov, porovnal 2 algoritmy pre cyklickú súvislosť regu-
lárnych grafov a vytvoril funkčnú aplikáciu pre kubické grafy, ktorá navyše ku cyklickej
súvislosti vypočíta aj netriviálne atómy cyklickej súvislosti.
|
|---|