Kostra grafu

  • Spanning tree
  • Vybrat nějakou sadu hran takovou, že bude indukovat souvislý graf
    • Bude strom
  • Nechť je souvislý graf, podgraf nazveme kostrou, pokud a je strom
    • Nesouvislé grafy nemají kostru, kostru má každá souvislá komponenta
    • Souvislý graf s kružnicemi má více koster
  • Podgraf, který obsahuje všechny vrcholy a zároveň je strom

../Attachments/03-kostra-grafu.png

Hledání kostry

  • Modifikace BFS - po zaplavení vrcholu vytvoříme zpětný pointer, odkud se zaplavilo
  • Nechť je souvislý graf
  • Hrany do předchůdců tvoří nějakou kostru grafu

Topologické uspořádání vrcholů

  • Pořadí vrcholů, aby všechny orientované hrany vedly pouze od nižších k vyšším indexům
  • Takové seřazení vrcholů , že pro každou orientovanou hranu platí platí
  • Může jich být více
  • Graf s cykly nemá řešení

../Attachments/Pasted image 20221003101547.png

Pozorování:

  • Graf má právě 1 topologické uspořádání, právě tehdy, když existuje orientovaná cesta délky v

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