Grafy I.

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

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

1. Sled (walk) je posloupnost uzlů a hran s počátečním a koncovým uzlem
   1. Otevřený
      1. Hrany ani uzly se nemůžou opakovat
         1. Cesta (path)
      2. Hrany se nemůžou opakovat
         1. Tah (trail, chain)
   2. Uzavřený
      1. Uzavřený sled je sled, kde počáteční a koncový uzel je stejný
      2. Hrany se nemůžou opakovat
         1. Uzavřený tah (cycle)

            Annotations:

            • V češtině se cyklus používá pro označení kružnic.  Uzavřený tah, který projde všechny hrany grafu, je Eulerovský tah
      3. Hrany ani uzly se nemůžou opakovat
         1. Kružnice, cyklus (circuit)

            Annotations:

            • Kružnicí označujeme spíše neorientované grafy Cyklus spíše v orientovaném  grafu
   3. V orientovaném grafu
      1. Nazýváme sled spojení
      2. Ve spojení lze propojit pouze uzly ve směru orientace
      3. Tah (cesta, cyklus) v orientovaném je také tah v neorientovaném po zrušení orientace

1. Orientace
   1. V neorientovaném grafu na pořadí uzlů ve dvojici nezáleží
   2. Orientovaný graf má uspořádanou množinu dvojic uzlů
2. G={V,E}
   1. V = uzly (vertices)
      1. Stupeň uzlu je počet jeho sousedů
         1. Orientované grafy rozlišují odchozí(-) a příchozí(+) stupeň
      2. Izolovaný uzel nemá sousedy
   2. E = hrany (edges)
      1. Počet hran je max E nad 2

         Annotations:

         • E nad 2 je počet hran v souvislém grafu, tj. grafu, kde každý uzel je spojen s každým
      2. Lze přidělovat váhu - obvykle funkcí
      3. Smyčka je hrana která vede ze stejného uzlu do kterého přichází
         1. Graf bez rovnoběžných hran a smyček je tzv. obyčejný
      4. Rovnoběžné hrany jsou hrany, které mají shodnou dvojici uzlů
         1. Graf bez rovnoběžných hran je tzv. prostý
         2. Graf s rovnoběžnými hranami je multigraf
      5. V grafu určeny funkcí incidence (hranám přiděluje uzly), nebo množinou dvojic uzlů
3. Podgrafy
   1. Podmnožina uzlů a hran je podgraf
   2. Podgraf, který redukuje pouze hrany a nevynechá žádný uzel je faktor
      1. Faktorizace grafu je rozpad grafu na všechny jeho faktory
   3. Kostra je minimální podgraf, která spojuje všechny uzly grafu a zároveň neobsahuje cykly
      1. Vynechávám hrany tak dlouho dokud můžu
      2. Žádný uzel nesmím izolovat
      3. Každý uzel má maximálně dva sousedy
4. Strom
   1. Obyčejný graf, který neobsahuje kružnice

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

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

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

Attachments:

• Grafy I. - selftest