Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Teorie grafů     LS 2016/2017

Předmět: 470-4302/01: Teorie grafů   (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2016/2017

Osnova předmětu je v systému Edison.

Průběh cvičení

Během semestru studenti odevzdají zápočtový projekt (maximálně za 20 bodů). Zápočet dostanou ti studenti, kteří získají alespoň 10 bodů.

Příklady k procvičení

Příklad k procvičení najdete v učebním textu, který najdete v seznamu literatury. Obsah souborů se průběžně aktualizuje.
Na zkoušku vybírám příklady vždy z učebního textu (z platné verze ke konci semestru). Pokud najdete v textu chyby, dejte mi, prosím, vědět.

 

Projekty   (20 bodů)

Můžete se podívat na seznam projektů z let 2007/2008, 2008/2009, 2009/2010, 2010/2011, 2011/2012, 2012/2013, 2013/2014 a 2015/2016 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

  1. Grafy s velkým obvodem   Ukažte, že pokud má rovinný 2-souvislý graf obvod alespoň 6, tak obsahuje vrchol stupně 2. Platí tvrzení i pro nerovinné grafy?
  2. Duální rovinné grafy   Pro která přirozená čísla n existuje takový jednoduchý rovinný graf G s n vrcholy, že jeho duální graf G* je isomorfní s grafem G?
  3. Strnulé grafy   Najděte strnulý kubický graf pro každé sudé n≥12.
  4. Barvení grafů s úplným párováním   Najděte nekonečnou třídu grafů třídy 1 takových, že žádný graf G z této třídy, ve kterém nejsou při žádném jeho dobrém Δ(G)-barvení obarveny hrany nějakého úplného párování stejnou barvou. Tj. žádná jeho barevná třída nemůže být úplným párováním, aniž by se použilo více než Δ(G) barev. Ukažte, že grafy mají požadované vlastnosti. Pokud takový graf neexistuje, dokažte to.
  5. Speciální bipartitní grafy   Najděte bipartitiní graf, který má každý vrchol sudého stupně alespoň 4, není pravidelný a navíc jeho hrany je možno obarvit dvěma barvami červenou a modrou tak, aby každý vrchol byl sousední se stejným počtem červených jako modrých hran. Jakých řádů může být nejmenší hledaný graf? Najdete nekonečnou třídu takových grafů?
  6. Sudé rovinné grafy   Mějme rovinný graf G, který má stupně všech vrcholů sudé. Dokažte, že chromatické číslo jeho duálního grafu G* je dva.
  7. Souvislé grafy   Dokažte, že v každém souvislém grafu G s alespoň třemi vrcholy existují dva různé vrcholy u, v takové, že všechny grafy G-u, G-v a G-{ u,v } jsou souvislé.
  8. Orientace rovinného grafu   Ukažte, že každý rovinný graf je možno zorientovat tak, že nejvyšší odchozí stupeň vrcholů v grafu je 3.
  9. Bridge-it   Ukažte, že ve hře Bridge-it (kapitola 3.4. ve skriptech) nemůže nastat remíza.
  10. Téma dle dohody

Termín odevzdání projektů je čtvrtek 4.5.2017.

Témata, která jsou už zadaná, jsou šedá. Očekává se, že projekty budou vypracovány na úrovni, která odpovídá studentům magisterského nebo doktorského studia. Nezapomeňte na správné citace použitých zdrojů. Případná různá obtížnost témat bude kompenzována mírou, jak přísně budou projekty hodnoceny.

 

Literatura

Je možné používat i jiné úvodní knihy a skripta, ovšem pozor: některé detaily se mohou lišit! (zejména definice pojmů) a u zkoušky platí to, co bylo probráno na přednášce.

 

Animace

Pro lepší pochopení vybraných pojmů můžete při studiu využít následující animace.

 

Konzultační hodiny

Zastihnete mne nejlépe během konzultačních hodin. Během zimního semestru 2017/2018 jsou stanoveny následující konzultační hodiny

DenČasMístnost
Pondělí10:00-11:00EA536*
*Jestliže přijde více studentů (>5), konzultace budou na EA553.

Po předchozí domluvě jsou konzultace možné i v jinou dobu.


email
kancelář EA536, tel. 597 325 972
Upraveno: 12.05.2017