Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Charakterizace DAG-depth orientovaného grafu

Characterizing DAG-depth of directed graphs

Matúš Bezek
Anotace

Študujeme DAG-depth, štrukturálnu hĺbkovú mieru orientovaných grafov, ktorá prirodzene rozširuje tree-depth neorientovaných grafov. Definujeme DAG-depth dekompozíciu ako policajnú stratégiu vo verzii hry na policajtov a zlodeja, kde položený policajt ostane v danom vrchole do konca hry. DAG-depth dekompozícia sa vzťahuje k DAG-depth podobne ako eliminačný strom k tree-depth. Poskytujeme definíciu zlúčiteľných …více

Abstract

We study DAG-depth, a structural depth measure of directed graphs, which naturally extends the tree-depth of ordinary graphs. We define a DAG-depth decomposition as a strategy for the cop player in the lift-free version of the cops-and-robber game on directed graphs. The DAG-depth decomposition is related to DAG-depth in a similar way as an elimination tree is related to the tree-depth. We provide …více

Klíčová slova
DAG-depth DAG-depth decomposition graph theory directed graph cops-and-robber DAG-depth dekompozícia teória grafov orientované grafy hra na policajtov a zlodeja
Zadání práce
The DAG-depth of a digraph is defined as the minimum number of cops that catch a visible infinitely fast robber in the digraph, under the condition that cops cannot move after landing on the graph. This work will characterize the DAG-depth in terms of a suitable natural decomposition of the digraph, and investigate the corresponding "closure" of the obtained decomposition in relation to the original digraph and to a winning strategy for the cop player.
Administrativní informace
Práce zkontrolována:
20. 5. 2016 10:51, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
387,7 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
22. 6. 2016
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

doc. Mgr. Jan Obdržálek, PhD., učo 1552
ITI FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.