| Meno: | Juraj
|
|---|
| Priezvisko: | Zemianek
|
|---|
| Názov: | Bipartizujúce párenia v kubických grafoch
|
|---|
| Vedúci: | Prof. RNDr. Martin Škoviera, PhD.
|
|---|
| Rok: | 2009
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | Bipartizujúce párenie, Dominujúca kružnica, Snark, Dominating Cycle Conjecture, Sabidussi Compatibility Conjecture, Cycle Double Cover Conjecture, Bipartizing Matchings Conjecture, Nowhere-zero 5-flow Conjecture
|
|---|
| Abstrakt: | Bipartizujúce párenia v kubických grafoch sú jedným z prístupov, ako nájsť v grafe dvojité pokrytie cyklami a nikde nulový 5-tok. K tomu je potrebné nájsť k grafu dominujúcu kružnicu a k nej dve dizjunktné bipartizujúce párenia. Fleischner (2002) vyslovil hypotézu, že pre každý snark a jeho dominujúcu kružnicu sa dá takáto dvojica párení nájsť. Hoffmann-Ostenhof (2007) hypotézu vyvrátil a vznikla nová, ktorá je slabším tvrdením predošlej.
V diplomovej práci sa podrobne zaoberáme bipartizujúcimi páreniami. Podrobne analyzujeme definíciu a ilustrujeme ju na príklade. Ďalej ukážeme, ako nájsť v grafe nikde nulový 5-tok a dvojité pokrytie cyklami, keď poznáme dominujúcu kružnicu a k nej dve dizjunktné bipartizujúce párenia. V experimentálnej časti preskúmame pomocou programu, do akej miery platí pôvodná hypotéza o nájdení dvoch biparitizujúcich párení na potenciálnych kontrapríkladoch (snarkoch) do 30 vrcholov a aká veľká je sila zmenenej hypotézy.
|
|---|