Charakterizace stromů

  • Nechť je graf, pak následující tvrzení jsou ekvivalentní:
    • je strom
    • Pro každé 2 vrcholy existuje právě jedna --cesta
      • Důkaz sporem: U více cest vznikne kružnice
    • je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf
      • Důkaz sporem: Nelze odebrat, jinak by tam předtím musela být kružnice a tedy by to nebyl strom
    • je souvislý a
      • Důkaz indukcí:
        • IP:

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