MLG - Orientované grafy

up:: MLG

Notion

New

• Notace
  • (🎥)
    • strom ⇒ pre/post/infix
    • pre/post/infix ⇒ strom ⇒ pre/post/infix
  • prefix - z leva okolo doprava je i píše
  • postfix - z prava okolo doleva je i píše
    • z prava se píše i větvě stromu
  • infix
    • výskyt
      • 1x - konstanty
      • 2x - znaménka
        • 1x = závorka
        • +|x,2 ⇒ x+2
    • z leva píše +
• Kritická cesta
  • (🎥)
  • [->|<-]
    • -> MAX
      • (počkat na nejdelší task)
      • nepřehlídnout žádnou hranu !
    • <- MIN (>max: = max)
  • Kritické
    • ?
      • v = vrchol
        • kv - kritický vrchol
      • h = hrana
    • body ⇒ v1=v2
    • cesta ⇒ hrany (kv+h=kv2)
• Minimální tok
  • (🎥)
  • free|inUse
  • setup
    • vybraní cesty (1.└── 2.┌──)
    • inUse += minHrana
      • write (+{minHrana}) ((+4) └──)
    • repeat (0 in way)
  • max tok = součet hran do T |f|=?
    • (|f|=h1->t + h2->t)
  • min řez = utvar před režem ({S,A,C})

Orientovaný

( můžeš jít jenom po šipkách )

• Dijkstra (Nejkratší cesta)
  • (🎥 1, A-B)
  • nezapomenou
    • přičíst minulou hodnotu
    • opsat nepoužité hodnoty
    • vybrat pouze jeden
• Eulerovský graf
  • (🎥)
  • je spojen (souvislý)
  • presne 2x liche = platí jinak ne
    • OUT+IN=? Liche
  • kreslení
    • lichý bod (x>y)
    • začít v bodě kde vychází než přichází
    • (idk)
    • konec (x<y)