Teorie grafů (Nebeský)                     (LS 2/1, Zk) LOG 

(Tento stručný přehled látky pomíjí důležité příklady, doplňující informace a historické poznámky, které jsou též součástí kursu. Není-li uvedeno jinak, jsou věty a tvrzení vykládány s důkazy. Součástí kursu je i průběžné komentované seznamování
s literaturou). 
 
     Definice grafu ve smyslu konečného neorientovaného grafu bez smyček a násobných hran. Rovnost grafů. Nekonečný graf; orientovaný graf (digraf); multigraf, pseudograf. Sousedství uzlu. Definice souvislého grafu založená na pojmu sousedství uzlu.
     Stupeň uzlu. Pravidelný graf. Tvrzení: součet stupňů všech uzlů v grafu se rovná dvojnásobku počtu hran. Důsledek: počet uzlů lichého stupně je sudý. Důsledek: pravidelný graf lichého stupně má sudý počet uzlů.
     Izomorfismus grafů. Grafy K(n), K(m, n), C(n), P(n). Diagram grafu.
     Podgraf, faktor, indukovaný podgraf. Komponenta grafu. Odčítání (množin) hran a uzlů. Přičítání hran. Most, artikulace. 
Věta (Lovász): Nechť G a H jsou grafy s touž množinou uzlů V o alespoň třech uzlech a nechť grafy G - u - v a H - u - v mají stejný počet hran pro libovolné různé uzly u, v množiny V. Potom G = H. 
     Pojem hranového grafu. Kartézský součin grafů. Hyperkrychle.
     Doplněk grafu. Tvrzení: alespoň jeden z komplementárních grafů  je souvislý. Ramseyova věta (ve speciální podobě; bez důkazu). Autokomplementární grafy. Věta: Autokomplementární graf s p uzly  existuje, právě když p = 0, 1 (mod 4).

     Otevřený/uzavřený sled, otevřený/uzavřený tah, cesta/kružnice v grafu.  Tvrzení: graf je souvislý, právě když pro každé dva uzly existuje cesta, která je spojuje. Tvrzení: Netriviální souvislý graf s nejvýše jedním uzlem stupně 1 obsahuje kružnici.   
     Eulerova věta.
     Strom. Tvrzení: Netriviální strom obsahuje alespoň dva uzly stupně 1. Důsledek: Strom o p uzlech má p - 1 hran.
     Kostra. Věta: graf je souvislý, právě když má kostru. Věta (Cayley) o počtu koster úplného grafu (bez důkazu).

     Vzdálenosti dvou uzlů (v souvislém grafu).  Průměr souvislého grafu. Excenticita uzlu, poloměr. Střed souvislého grafu. Jordanova věta o středu stromu (bez důkazu). Mocniny grafu.
     Nejkratší (čili geodetické) cesty v grafu. Intervalová funkce souvislého grafu. Věta: axiomatická charakterizace intervalové funkce.
     Hamiltonovské grafy. Postačující podmínka Bondyho a Chvátala, aby byl graf hamiltonovský; pojem uzávěru grafu; důsledek (Bondy a Chvátal): graf je hamiltonovský, právě když je jeho uzávěr hamiltonovský. Věta (důsledek Sekaninovy věty): Třetí mocnina souvislého grafu o alespoň třech uzlech je hamiltonovská. Fleischnerova věta o druhé mocnině grafu (bez důkazu).
 
   Mengerova věta (bez důkazu). Uzlový/hranový stupeň souvislosti a minimální stupeň grafu (nerovnosti). 
    Bipartitní graf.Věta: Netriviální graf je bipartitní, právě když neobsahuje lichou kružnici.
   Párování v grafu. Hallova věta. Věta (Berge) o maximálním párování (bez důkazu). Tvrzení o dokonalém párování v druhé mocnině grafu. Tutteova věta o dokonalém párování. Petersenova věta (jako důsledek věty Tutteovy). 
    Hranová barevnost grafu. Vizingova věta (bez důkazu).
    Nezávislá množina. Barevnost grafu. Brooksova věta (bez důkazu).

    Pojem digrafu. Stejnolehlý graf. Zdrojový strom.     
    Silně souvislý digraf. Robbinsova věta o orientovatelnosti. Turnaje. Rédeiova věta o hamiltonovské cestě. Věta o kružnicích v silně souvislém turnaji.

    Rovinné grafy, sféra. Polytopické grafy (grafy konvexních mnohostěnů), Steinitzova věta (bez důkazu). 
    Homeomorfismus grafů. Kuratowského věta (bez důkazu).
    Nerovinné grafy. (Orientovatelný) rod grafu. Buněčné vnoření. Youngsova věta (bez důkazu). (Zobecněná) Eulerova formule pro buněčné vnoření (bez důkazu).