Řezy v grafu

  • Množiny vrcholů A a B
  • Hrany mezi vrcholy, které leží jedním vrcholem A a druhým v B budeme říkat řez grafu
Definice
  • Nechť je podmnožina vrcholů grafu a její doplněk,
  • Množina všech hran, které leží jedním vrcholem v a druhým v , budeme říkat řez grafu určený množinami a .
Lemma (o řezech v grafu s unikátními vahami)
  • Nechť je souvislý ohodnocený graf s unikátními vahami,
  • nějaký jeho řez,
  • nejlehčí hrana tohoto řezu.
  • Pak (každá) minimální kostra obsahuje hranu .

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