Navazuje na 01 Graf

Druhy grafů

Úplný graf (klika)

../Attachments/01-graf-uplny.png

Úplný bipartitní graf

  • Nechť počet vrcholů a
  • Je tvořen 2 partitami o a vrcholech
  • Graf tedy vrcholy jsou sjednocení vrcholů z grafů a , hrany vedou z vrcholu do
  • Každý vrchol vlevo má hranu ke každému vpravo, tedy počet hran

../Attachments/01-graf-bipartitni.png

Cesta

  • Značíme
  • Délka cesty
  • Cesta je graf = tedy graf s vrcholy a hranami takový, že hrana jde vždy z předchozího do dalšího vrcholu
Pozor!

U cesty udává index počet hran, nikoli vrcholů!

../Attachments/01-graf-cesta.png

Kružnice

  • Počet vrcholů je alespoň 3 =
  • Vrcholy propojené v kruhu

../Attachments/01-graf-kruznice.png

Doplněk grafu

  • Doplněk grafu je graf

  • Tedy úplný graf se všemi hranami kromě hran grafu

  • Nechť

  • Pak

../Attachments/01-graf-doplnek.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25