Grafy I.

Grafy I.

1. Handshaking lemma

   • Neorientovaný graf
     • Suma stupňů všech uzlů je rovna dvojnásobku počtu hran grafu
     • Sudý počet uzlů má lichý stupeň
   • Orientovaný graf
     • Suma odchozích a příchozích stupňů všech uzlů je rovna dvojnásobku počtu hran grafu

2. Úplnost grafu

   • Kompletní (úplný graf)
     • Všechny uzly se všemi
     • Právě V nad 2 hran
     • Stupeň každého uzlu je V - 1
     • Orientovaný grafu kde platí oba směry orientace nazýváme úplný symetricky orientovaný graf
   • Prázdný graf
     • Žádné uzly ani hrany
   • Diskrétní graf
     • Pouze izolované uzly bez hran
   • Bipartitní graf
     • Částečně úplný
     • Graf lze rozdělit na dvě části
       • Uzly mezi sebou v dané části nemají žádné hrany
       • Z každého uzlu v jedné části vede hrana do každého uzlu v druhé části

3. Posloupnosti v grafu

   • Sled (walk) je posloupnost uzlů a hran s počátečním a koncovým uzlem
     • Otevřený
       • Hrany ani uzly se nemůžou opakovat
         • Cesta (path)
       • Hrany se nemůžou opakovat
         • Tah (trail, chain)
     • Uzavřený
       • Uzavřený sled je sled, kde počáteční a koncový uzel je stejný
       • Hrany se nemůžou opakovat
         • Uzavřený tah (cycle)
           • V češtině se cyklus používá pro označení kružnic.  Uzavřený tah, který projde všechny hrany grafu, je Eulerovský tah
       • Hrany ani uzly se nemůžou opakovat
         • Kružnice, cyklus (circuit)
           • Kružnicí označujeme spíše neorientované grafy Cyklus spíše v orientovaném  grafu
     • V orientovaném grafu
       • Nazýváme sled spojení
       • Ve spojení lze propojit pouze uzly ve směru orientace
       • Tah (cesta, cyklus) v orientovaném je také tah v neorientovaném po zrušení orientace

4. Definice a základní vlastnosti

   • Orientace
     • V neorientovaném grafu na pořadí uzlů ve dvojici nezáleží
     • Orientovaný graf má uspořádanou množinu dvojic uzlů
   • G={V,E}
     • V = uzly (vertices)
       • Stupeň uzlu je počet jeho sousedů
         • Orientované grafy rozlišují odchozí(-) a příchozí(+) stupeň
       • Izolovaný uzel nemá sousedy
     • E = hrany (edges)
       • Počet hran je max E nad 2
         • E nad 2 je počet hran v souvislém grafu, tj. grafu, kde každý uzel je spojen s každým
       • Lze přidělovat váhu - obvykle funkcí
       • Smyčka je hrana která vede ze stejného uzlu do kterého přichází
         • Graf bez rovnoběžných hran a smyček je tzv. obyčejný
       • Rovnoběžné hrany jsou hrany, které mají shodnou dvojici uzlů
         • Graf bez rovnoběžných hran je tzv. prostý
         • Graf s rovnoběžnými hranami je multigraf
       • V grafu určeny funkcí incidence (hranám přiděluje uzly), nebo množinou dvojic uzlů
   • Podgrafy
     • Podmnožina uzlů a hran je podgraf
     • Podgraf, který redukuje pouze hrany a nevynechá žádný uzel je faktor
       • Faktorizace grafu je rozpad grafu na všechny jeho faktory
     • Kostra je minimální podgraf, která spojuje všechny uzly grafu a zároveň neobsahuje cykly
       • Vynechávám hrany tak dlouho dokud můžu
       • Žádný uzel nesmím izolovat
       • Každý uzel má maximálně dva sousedy
   • Strom
     • Obyčejný graf, který neobsahuje kružnice

5. Souvislost

   • Komponenta je každý maximálně souvislý podgraf
   • Neorientovaný graf = slabá
     • Existuje tah mezi libovolnými dvěma uzly
   • Orientovaný graf = silná
     • Existuje spojení mezi libovolnými dvěma uzly
     • Každá jeho hrana je obsažena v nějakém cyklu

6. Operace

   • Sjednocení
     • Sjednocení množiny uzlů, hran a incidencí
   • Průnik
     • Průnik množiny uzlů, hran a incidencí
     • Vznikne-li průnikem prázdný graf, grafy jsou vzájemně disjunktní
   • Doplněk
     • Graf, který vznikne odečtením G od úplého grafu nad stejnou množinou uzlů
   • Rozdíl
     • Laicky - z grafu A odstraním uzly a hrany grafu B
     • Formálně - výsledek je graf, jehož sjednocení s odečteným grafem dá graf původní

7. Zobrazení

   • Bijekce
     • Vzájemně jednoznačné zobrazení
     • Přejmenuju uzly a hrany, žádnou hranu ani uzel nevynechám a stupně uzlů zůstanou stejné
   • Izomorfismus
     • Bijekce která zachovává strukturu
     • Přejmenované uzly jsou propojeny se stejnými uzly jako předtím, než došlo k přejmenování
   • Bijekce která není izomorfismus
     • Mohu uzly a hrany přejmenovat a žádný nevynechat, ale přejmenované uzly budou vzájemně propojené jinak, než předtím

8. SELFTEST

   • Grafy I. - selftest