Cvičení z kombinatoriky a grafů II (ZS 2011/2012)
Cvičení se koná každé pondělí od 14:00 na Malé Straně v učebně S7, stránku k přednášce najdete zde.
Konzultace
Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.
Zápočet
Zápočet je za 15 bodů, které lze získat za vyřešení zápočtových příkladů (celkem max. 30 bodů) případně za velmi aktivní účast během cvičení.
Zadani příkladů budou zveřejňována na webu přednášky (ve třech sériích v průběhu semestru).
Co jsme dělali?
3.10.2011
Úvodní cvičení, suploval Zdeněk Dvořák.
- Opakování a příklady na Hallovu větu,
- rovinné grafy (Kuratowského věta, Eulerova formule),
- barevnost a její vztah vůči klikovosti/velikosti maximální nezávislé množině/maximálnímu stupní.
10.10.2011
- Tutte-Bergeho formule pro velikost největšího párování v obecném grafu G (alternativní důkaz nepoužívající větu z přednášky o Edmonds-Gallaiově dekompozici můžete najít zde),
- párování M v grafu G je největší právě tehdy když v G neexistuje volná M-střídavá cesta,
- pro každý kubický graf bez mostů a jeho libovolnou hranu e existuje perfektní párování,
- které hranu e obsahuje, a také existuje perfektní párování, které e neobsahuje.
17.10.2011
- V každém kubickém grafu bez mostů existuje perfektní párování, které neobsahuje dvě libovolně předepsané hrany,
- kubický graf s nejvýše dvěma mosty obsahuje perfektní párování,
- k-regulární hranově (k-1)-souvislý graf se sudým počtem vrcholů obsahuje perfektní párování,
- pro každé k existuje k-regulární hranově (k-2)-souvislý graf se sudým počtem vrcholů, který neobsahuje perfektní párování (dokončeno 24.10.),
- kubický bipartitní graf obsahuje alespoň 9/4×(4/3)^n perfektních párování (dokončení důkazu z přednášky, více zde).
24.10.2011
- Nakreslení úplného grafu K_6 do projektivní roviny + dualní graf je izomorfní Petersenovi,
- nakreslení úplného grafu K_7 na torus,
- libovolné nakreslení K_7 jako triangulace na nějaké ploše musí být orientovatelné nakreslení (tudíž K_7 nelze na Kleinovu lahev),
- změna rodu plochy po přidání jednoho ucha resp. jednoho křížítka.
31.10.2011
- Pokud graf H má maximální stupeň nejvýše tři, potom každý graf G obsahuje podrozdělení H právě tehdy když G obsahuje H jako minor,
- G je vnějškově rovinný právě tehdy když G neobsahuje podrozdělení K_2,3 nebo K_4 (a to je právě tehdy když neobsahuje K_2,3 či K_4 jako minor),
- 3-souvislý rovinný graf má jednoznačné kombinatorické nakreslení,
- rovinný graf lze vždy nakreslit do roviny tak, že všechny hrany jsou nakresleny pomocí úseček.
7.11.2011
- Pro každé c existuje (multi)graf G, který obsahuje hranu s násobností c a má hranovou barevnost Delta(G) + c,
- každý bipartitní graf G má hranové obarvení pomocí Delta(G) barev (tzv. Königova věta),
- ekvivalence mezi větou o čtyřech barvách a tvrzením, že každý kubický graf bez mostů má hranové 3-obarvení,
- příklad dvou grafů, které mají stejný line-graf,
- v každém line-grafu G lze sousedství každého vrcholu pokrýt pomocí dvou úplných grafů,
- náznak toho, kde selhává původní důkaz Vizingovy věty pro grafy s násobnými hranami.
14.11.2011
- Comparability grafy (grafy vzniklé z částečných uspořádání) jsou perfektní,
- split grafy (grafy, jejíchž vrcholy lze rozdělit na dvě části, kde první část indukuje úplný graf a druhá indukuje nezávislou množinu) jsou perfektní,
- intervalové grafy (průnikové grafy intervalů na reálné ose) jsou perfektní,
- v chordálním grafu (graf bez indukované kružnice délky >3) indukuje každý minimální vrcholový řez úplný podgraf,
- G je perfetní právě tehdy když pro každý jeho indukovaný podgraf H platí, že H obsahuje nezávislou množinu protínající všechny kliky největší velikosti,
- buď G perfektní a G' graf vzniklý z G nahrazením jednoho vrcholu x hranou uv tak, že všechny sousedy x spojíme v G' s u i s v; potom G' je perfektní.
21.11.2011
- Dokončení z minule: v chordálním grafu indukuje každý minimální vrcholový řez úplný podgraf + po zdvojení libovolného vrcholu v perfektním grafu dostaneme opět perfektní graf,
- vyjádření počtu acyklických podgrafů pomocí rekurzivní formule používající kontrakce a odebírání hran, vyjádření též pomocí chromatického a Tutteho polynomu,
- pokud G je rovinný graf vnořený do roviny a H k němu duální graf, potom T(G,x,y) = T(H,y,x),
- buď G graf vzniklý buď jako disjunktní sjednocení dvou grafů G_1 a G_2, nebo jako slepení G_1 a G_2 za jeden vrchol; potom T(G,x,y) = T(G_1,x,y)×T(G_2,x,y),
- pro každé n mají všechny stromy na n vrcholech stejný Tutteho polynom.
28.11.2011
- Definice nikde nulového k-toku + základní pozorování o tocích a hranových řezech,
- tokový polynom grafu pro Z_k a jeho vyčíslení pomocí univerzálního resp. Tutteho polynomu,
- dtto, ale pro libovolnou aditivní grupu F s k prvky (neboli nikde nulových F-toků závisí jen na počtu prvků F),
- souvislost mezi nikde nulovými toky a barevností v rovinných grafech,
- souvislost mezi nikde nulovým 4-tokem a hranovým 3-obarvením v kubických grafech,
- příklad tuhého grafu, který není hamiltonovský (např. Petersenův graf),
- pokud G je souvislý, tak G^3 obsahuje hamiltonovskou kružnici (dokonce pro každou hranu e v G existuje v G^3 hamiltonovská cesta mezi jejími konci).
5.12.2011
- "Kuchařka" pro konstrukce sjednocení / dvojic / posloupností / (multi)množin / cyklů objektů z prvků již známé obyčejné / exponenciální vytvořující funkce,
- počet součtů přirozeného čísla n≥2 pomocí lichého resp. sudého počtu kladných celých sčítanců, kde záleží na pořadí, je stejný,
- počet součtů přirozeného čísla n pomocí různých sčítanců resp. pomocí jen lichých sčítanců, kde v obou případech NEzáleží na pořadí, je stejný,
- vytvořující funkce více proměnných a jejich použití na třídy objektů s parametrem,
- střední počet cyklů v náhodné permutaci na n prvcích,
- obecný postup, jak zjistit z vytvořující funkce pro objekty s parametrem střední hodnotu parametru pro náhodně uniformně vybraný objekt velikosti n.
12.12.2011
Cvičení suploval Ján Mazák.
- Počet stěnových obarvení krychle pomocí n barev (kde obarvení, která se liší jen otočením, považujeme za stejná),
- počet náhrdelníků se 4 korálky s celkem n typy korálků,
- počet neizomorfních grafů na 4 vrcholech,
- rekurzivní formule pro počet zakořeněných ternárních stromů.
19.12.2011
- Pokud je G uplný multipartitní graf na n vrcholech s největším možným počtem hran a neobsahující K_r, potom G je úplný balancovaný (r-1)-partitní graf (Turánův graf T_n),
- má-li graf G nejvýše k*n/2 hran, potom obsahuje nezávislou množinu velikosti alespoň n/(k+1) (rovnost nastává právě tehdy, když G je doplněk Turánova grafu),
- největší možná velikost množinového systému nad [n] takového, že každé dvě množiny mají neprázdný průnik,
- největší možná veliokst množinového systému nad [n] takového, že každá množina má velikost k a sjednocení lib. dvou množin nepokrývá celé [n],
- Kneserův graf KG(n,k) a souvislost mezi velikostí největší nezávislé množiny v KG(n,k) a Erdös-Ko-Radovou větou,
- Hellyho vlastnost pro množinové systémy obsahující množinu velikosti přesně k a vlastností, že každých k+1 množin má neprázdný průnik.
9.1.2012
- Horní odhad na Ramseyovo číslo R(3,3,3),
- Schurova věta: pro každé r existuje n takové, že každé obarvení čísel 1,…,n pomocí r barev obsahuje jednobarevné řešení rovnice a+b=c,
- každá posloupnost realných čísel obsahuje vybranou podposloupnost, která je buď rostoucí, nebo klesající, nebo konstantní,
- znění van den Wardenovy věty: pro každé k a r existuje n takové, že v libovolném obarvení čísel 1,…,n existuje jednobarevná aritmetická posloupnost délky k,
- existuje 2-obarvení přirozených čísel takové, že v něm neexistuje nekonečná jednobarevná aritmetická posloupnost,
- Erdös-Szekeresovo lemma: pro každou posloupnost n×m+1 různých čísel existuje vyb. rostoucí podposloupnost délky n+1, nebo vyb. klesající podposloupnost délky m+1,
- Dilworthova věta (duální tvrzení k větě o dlouhém & širokém): prvky každého částečného uspořádán lze pokrýt k řetězci, kde k je délka jeho nejdelšího antiřetězce,
- Lemma o slunečnici: pokud rodina t-prvkových množin má velikost větší než t!(k-1)^t , potom obsahuje slunečnici s alespoň k listy (viz: S. Jukna: Extremal Combinatorics),
- naopak existuje rodina t-prvkových množin velikosti (k-1)^t , která neobsahuje slunečnici s k listy.
Objevíte-li někde chybu, dejte mi, prosím, vědět.
Stránka vytvořena za pomoci programů vi, bash a perl. Poslední změna: 10.01.2012