MLG - NeOrientované grafy

up:: MLG

Resource

• 💾
  • P:: 6, 7, 8
  • F:: 6, 7, 8
  • AT
• 🎥

Test

• Posloupnost
  • může být ?kostrou? prostého grafu? → nakreslit
• Orelovský graf
  • graf → je orelovský? → najdete orelovský tah
• Minimální kostra
  • hledání m. k. → 2 postupy → očíslujte
• Diskra

  • najděte nejkratší cestu → strom nejkratší cest

6

• Izomorfní
  • (🎥)
  • stejný počet vrcholů
  • stejné score
    • score = počet hran
    • (čar z bodu)
  • lze změnit tvar aby byly stejný
  • spojit stejné vrcholy
• Skoré 3321 -> 210 (Je prostý?)
  • (🎥)
  • sudé
    • sečíst stupně ⇒ (Y+X) = sudé
      • sudé ⇒ next
      • liché vyškrtat ⇒ nelze sestavit
  • snižování
    • z leva vymažem a odečteme tolik 1 napravo
      • sort!!!
    • -1 → graf nexistuje
    • 0 - nakreslit (od spoda)
• Eulerovský graf
  • (🎥)
  • je spojen (souvislý)
  • stupně vrcholů
    • počítáme pouze liché
    • lichý bod (0, sudý počet hran)
  • kreslení
    • nahodně
    • pokud neplatí, jdu druhou stranou
      • =n
    • ⇒ souvslá a má právě dva vrcholy lichého stupně

7

• Kostry izomorfní
  • (🎥)
  • kostra = spojit všechny body s nejmenší počtem hran
  • min hran = p.vrcholu-1
• Kostra minimální
  • (🎥)
  • Hladový
    • 0→9 (nejmenší → největší)
    • přidáváme postupně
      • všechny spojené / kružnice
  • Jarníkův
    • zvolit jeden vrchol
    • zvolit
      • vychází z aktivních vrcholů
      • není připojen
      • minimální váhu

8

• Nejkratší cesta (Dijkstrův algoritmus)
  • (🎥 1, A-B)
  • nezapomenou
    • přičíst minulou hodnotu
    • opsat nepoužité hodnoty
    • vybrat pouze jeden