Title: Státnice / Společná matematika / Teorie grafů

Q: Základní pojmy teorie grafů: graf, vrcholy a hrany, izomorfismus grafů, podgraf, okolí vrcholu a stupeň vrcholu, doplněk grafu, bipartitní
graf
A: všichni známe

Q: Základní příklady grafů: úplný graf a úplný bipartitní graf, cesty a kružnice
A: všichni známe

Q: Souvislost grafů, komponenty souvislosti, vzdálenost v grafu
A: všichni známe

Q: Stromy: definice a základní vlastnosti (existence listů, počet hran stromu)
A: |E| = |V| - 1

Stromy: ekvivalentní charakteristiky stromů

Rovinné grafy: definice a základní pojmy (rovinný graf a rovinné nakreslení grafu, stěny)

Q: Rovinné grafy: Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití)
A: Pro rovinný graf bez trojúhelníků platí ještě odhad |E| <= 2|V| - 4

Barevnost grafů: definice dobrého obarvení

Barevnost grafů: vztah barevnosti a klikovosti grafu

Hranová a vrcholová souvislost grafů: hranová a vrcholová verze Mengerovy věty

Orientované grafy, silná a slabá souvislost

Toky v sítích: definice sítě a toku v ní

Q: Toky v sítích: existence maximálního toku (bez důkazu)
A: Kdyby to někoho zajímalo, tak cvičení dva:

Q: Toky v sítích: princip hledání maximálního toku v síti s celočíselnými kapacitami (například pomocí Ford-Fulkersonova algoritmu)
A: Stačí princip, tak rozbor vynechávám.