Ctvrtek 9:00 - S1
Přednášíme společně s dr. Jelínkem.
Zkousky ve ctvrtky 16.1., 30.1., 6.2. a 13.2. vzdy v 9:00 v S1.
3.10.2013
Chordalni grafy
Definice chordalnich grafu jako grafu bez indukovanych kruznic delky delsi nez 3.
Definice simplicialniho vrcholu. Lemma, ze v chordalnim grafu kazdy minimialni vrcholovy rez indukuje kliku.
Veta, ze kazdy chordalni graf obsahuje alespon jeden simplicialni vrchol.
Definice PES (perfect elimination scheme), dusledek, ze chordalni grafy jsou perfektni a nejvetsi klika i optimalni obarveni lze najit z PES v polynomialnim case metodou barveni First Fit.
Definice stromoveho rozkladu grafu, definice klikove-stromoveho rozkladu.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
10.10.2013
Algoritmus na rozpoznavani chordalnich grafu (prednasel V. Jelinek)
Prohledavani grafu LexBFS, konstrukce PES v linearnim case, overeni PES v linearnim case.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
17.10.2013
Intervalove, permutacni a srovnatelne grafy
Dokonceni dukazu charakterizacni vety o chordalnich grafech: Nasledujici jsou ekvivalentni (1) G je chordalni (2) G ma PES (3) G ma klikove stromovy rozklad (4) G je prunikovy graf podstromu ve stromech.
Intervalove grafy, definice.
Srovnatelne grafy (grafy porovnatelnosti v castecnych usporadanich), definice.
Permutacni grafy, definice.
Funkcni grafy (prunikove grafy grafu spojitych funkci na uzavrenem intervalu), definice.
Charakterizacni vety:
24.10.2013
Struktura tranzitivnich orientaci Blokem B(xy) orientovane hrany xy nazveme
nejmensi relaci B \subset VxV takovou, ze
(S) (ab\in B) & (ac\in E) & (bc \not\in E) implikuje ac\in B (a soucasne (ba\in B) & (ac\in E) & (bc \not\in E) implikuje ca\in B).
Hlavni veta rika, ze G je tranzitivne orientovatelny prave tehdy kdyz
B(xy) je antisymetricka relace pro kazdou hranu xy\in E.
Tato podminka je evidentne nutna. Postacujicnost plyne z nekolika pozorovani:
1. Je-li B(xy) antisymetricky blok, pak je i tranzitivni.
2. Rozklad na bloky je ekvivalence, tedy kdyz ab\in B(xy), pak B(ab) = B(xy).
3. Je-li M\subset VxV tranzitivni orientace nekterych hran grafu splnujici pravidlo (S) a hrana xy neni v M orientovana zadnym smerem, pak tranzitivni uzaver M\cup B(xy) je antisymetricka tranzitivni relace orientujici (ne nutne vsechny) hrany grafu.
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004
Prunikove grafy usecek, konvexnich mnozin a krivek v rovine. Predstaveni techto trid, podrobnejsi povidani o STRING grafech (prunikove grafy krivek). Napr ze kazdy konecny STRING graf ma reprezentaci s konecnym poctem pruseciku.
Souvislost STRING grafu a abstraktnich topologickych grafu. Funkce str(n) a at(m) jako maxima poctu pruseciku, ktere vyzaduji STRING grafy na n vrcholech (resp. slabe realizovatelne AT grafy o m hranach), jsou polynomialne ekvivalentni. Priklad ukazujici at(m) >= 2^{\Omega(m)}.
Jan Kratochvíl, Jirí Matousek: String graphs requiring exponential representations. J. Comb. Theory, Ser. B 53(1): 1-4 (1991)
31.10.2013
Rozpoznavani STRING grafu a slabe realizovatelnych AT grafu
Rekurzivni (i kdyz velmi velmi casove narocny) algoritmus bude plynout z dokazani jakehokoliv (vycislitelneho) horniho odhadu na potrebny pocet pruseciku. Ukazali jsme si krasny dukaz Schaefer-Stefankovice nasledujici nerovnosti:
at(m) <= m2^m.
Marcus Schaefer, Daniel Stefankovic: Decidability of string graphs. J. Comput. Syst. Sci. 68(2): 319-334 (2004)
7.11.2013 (prednasel V. Jelinek)
Chi-omezenost PC grafu
Definice chi-omezenych trid grafu.
Definice CA ("circular-arc") grafu, a dukaz, ze jsou chi-omezene.
Definice PC ("polygon-circle") grafu jako prunikovych grafu mnohouhelniku
v kruznici.
Alternativni reprezentace PC grafu pomoci mnozin cisel, kdy dva vrcholy
jsou sousedi kdyz jejich mnoziny maji alternaci delky 4.
Dukaz, ze PC grafy jsou chi-omezene.
Alexandr V. Kostochka, Jan Kratochvíl: Covering and coloring polygon-circle graphs. Discrete Mathematics 163(1-3): 299-305 (1997)
14.11.2013 (prednasel V. Jelinek)
Jeste k PC grafum chordální grafy jsou podmnožina PC-grafů
Jeste k chi-omezenosti SEG grafy nejsou chi-omezené
Pawlik, A., Kozik, J., Krawczyk, T., Lasoń, M., Micek, P., Trotter, W.T., Walczak, B.: Triangle-free intersection graphs of line segments with large chromatic number http://arxiv/abs/1209.1595
Klikovost a nezavislost v nekterych prunikovych tridach grafu
v chordálních grafech lze (hladově) najít největší nezávislou množinu (a
připomenul jsem, jak najít největší kliku),
v intervalových grafech lze polynomiálně najít největší váženou
nezávislou množinu
Interval-filament grafy definice IFA a nahlédnutí, že PC a co-comparability jsou podmnožina IFA
21.11.2013 (prednasel V. Jelinek)
Klika a nezavisla mnozina v IFA grafech - polynomialni algoritmy, predpokladem je dana IFA reprezentace.
Fanica Gavril: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5-6): 181-188 (2000)
28.11.2013 (prednasel V. Jelinek)
Rozpoznavani string grafu je v NP cast I.
5.12.2013 (prednasel V. Jelinek)
Rozpoznavani string grafu je v NP cast II.
Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2): 365-380 (2003)
19.12.2013
Rozpoznavani string grafu je NP-tezke
Jan Kratochvíl: String graphs. II. recognizing string graphs is NP-hard. J. Comb. Theory, Ser. B 52(1): 67-78 (1991)
2.1.2014
Rozpoznavani SEG grafu a 2-DIR grafu je NP-tezke
Jan Kratochvíl: A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness. Discrete Applied Mathematics 52(3): 233-252 (1994)
9.1.2014
Boxicita grafu. Bipartitni graf boxicity 2 je 2-DIR graf.
S. Bellantoni, Irith Ben-Arroyo Hartman, Teresa M. Przytycka, Sue Whitesides: Grid intersection graphs and boxicity. Discrete Mathematics 114(1-3): 41-49 (1993)