Graf

  • Neorientovaný graf je uspořádaná dvojice , kde:
    • - neprázdná konečná množina vrcholů (Vertex)
    • - množina hran (Edge)
      • Hrana je 2-prvková podmnožina - neuspořádaná dvojice vrcholů
      • Množinu všech možných hran (všech 2-prvkových podmnožin množiny ) označujeme
  • Obvykle graf označuje neorientovaný graf

Vrcholy

  • Množina vrcholů grafu
  • Počet vrcholů

Hrany

  • Množina hran grafu

  • Počet hran

  • Nechť , pak řekneme, že:

    • Vrcholy jsou koncové vrcholy hrany
    • je sousedem a naopak
    • i jsou incidentní s hranou (incidence)

  • Hrana je 2-prvková podmnožina , platí tedy , např. pro

Sled a cesta

Sled

  • Sled délky je sekvence vrcholů a hran v grafu

Cesta

  • Značíme
  • Cesta je sled, ve kterém se neopakují vrcholy a tedy ani hrany
  • Pro koncové vrcholy a mluvíme o s-t-cestě (připouštíme , tedy může mít i 0 délku)
  • Délka s-t-cesty je počet hran v této cestě

- pole vzdáleností
- pole předchůdců

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