Original title:
Užití lineární algebry v kombinatorice
Translated title:
Combinatorial applications of linear algebra
Authors:
Tesař, Marek Document type: Rigorous theses
Year:
2009
Language:
cze Abstract:
[cze][eng] Nakrytie grafu G do grafu H je "lokálny izomorfizmus": zobrazenie vrcholov grafu G na vrcholy grafu H také, že pre všetky v V (G), okolie vrchola v je zobrazené bijektívne na okolie (v H) obrazu v. My študujeme výpočetnú zložitosť problému nakrytia na graf H (rozhodnútie či pre daný graf G existuje nakrytie do H), kde graf H je regulárny graf na 8 vrcholoch, jeho hrany majú dve farby, pričom hrany jednej farby tvoria dva disjunktné 4-cykly. Podávame tu plnú charakterizáciu problému nakrytia pre takéto 3 regulárne grafy. Polynomiálne prípady riešime pomocou prevodu na sústavu lineárnych rovníc a tiež ukážeme niektoré grafy, pre ktoré táto metóda nefunguje (napriek tomu, že problém nakrytia je polynomiálne riešitelný).A covering projection from graph G onto graph H is "local isomorphism": a mapping from the vertex set of G onto the vertex set of H such that, for every v V (G), the neighborhood of v is mapped bijectively onto the neighborhood (in H) of the image of v. We study the computational complexity of the H-cover (deciding if a given graph G covers H), where G is a regular graph with 8 vertices and edges of two colors, where edges of one color create two disjoint 4-cycles. We present full characterization of H-cover problem for such 3-regular graphs. We solve polynomial cases by reduction to system of linear equations and we show some graphs for which this method doesn't work (even though H-cover is polynomial).
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/24808