Orientovaný graf

  • Uspořádaná dvojice , kde:
    • - neprázdná konečná množina vrcholů
    • - množina orientovaných hran (šipky)
  • Orientovaná hrana je uspořádaná dvojice
    • - předchůdce
    • - následník
    • - smyčka

../Attachments/02-graf-orientovany.png

Modrá/červená hrana

  • Nejvýš 1 modrá hrana:
    • Udělám 2 kopie grafu jako orientovaný graf
    • Červené hrany budou obousměrné v obou kopiích
    • Modré hrany budou vést mezi kopiemi (orientované z jedné kopie do druhé)

../Attachments/02-graf-modry-cerveny.png

Zbytkové třídy

  • Číslo vynásobím základem, přičtu novou cifru (0 nebo 1), modulím základem, zbytek je opět hrana k další třídě

../Attachments/02-zbytkove-tridy.png

Symetrizace

  • Každou orientovanou šipku nahradím neorientovanou hranou
  • "Zapomenu orientaci"

Slabá souvislost orientovaného grafu

Souvisí s 02 Souvislost grafu

  • Je slabě souvislý, pokud je souvislá jeho symetrizace

Silná souvislost

  • Je silně souvislý, pokud pro každé vrcholy existuje orientovaná cesta tam i nazpátek (nemusí být přímo jen délky 1)

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