Königov poučak (teorija grafova): razlika između inačica
Izbrisani sadržaj Dodani sadržaj
mNema sažetka uređivanja |
Broj spašenih izvora: 1; broj poveznica koje su označene kao mrtve: 0) #IABot (v2.0.8 |
||
| Redak 1: | Redak 1: | ||
'''Königov poučak''', matematički [[poučak]]. Nosi ime po matematičkom [[teorija grafova|teoretičaru grafova]] [[Dénes Kőnig| Dénesu Kőnigu]]. Broj bridova u [[bipartitni graf|bipartitnom grafu]] u maksimalnom [[sparivanje grafova|sparivanju]] jednak je broju vrhova u minimalnom pokrivaču tog [[graf]]a. Sparivanjem se naizva skup bridova za koji ne postoje dva brida iz tog skupa koji imaju zajednički vrh. Pokrivač je skup vrhova za koji vrijedi da svaki brid im barem jedan kraj u nekom od tih vrhova.<ref name=Bašić>[https://web.math.pmf.unizg.hr/nastava/studnatj/poset.pdf PMF Zagreb] Matija Bašić: '' Uvod u algebarsku topologiju - Parcijalno uređeni skupovi - O lancima i antilancima'', 21. svibnja 2014., str. 1 (pristupljeno 19. prosinca 2019.)</ref> |
'''Königov poučak''', matematički [[poučak]]. Nosi ime po matematičkom [[teorija grafova|teoretičaru grafova]] [[Dénes Kőnig| Dénesu Kőnigu]]. Broj bridova u [[bipartitni graf|bipartitnom grafu]] u maksimalnom [[sparivanje grafova|sparivanju]] jednak je broju vrhova u minimalnom pokrivaču tog [[graf]]a. Sparivanjem se naizva skup bridova za koji ne postoje dva brida iz tog skupa koji imaju zajednički vrh. Pokrivač je skup vrhova za koji vrijedi da svaki brid im barem jedan kraj u nekom od tih vrhova.<ref name=Bašić>[https://web.math.pmf.unizg.hr/nastava/studnatj/poset.pdf PMF Zagreb] {{Webarchive|url=https://web.archive.org/web/20191219211234/https://web.math.pmf.unizg.hr/nastava/studnatj/poset.pdf |date=19. prosinca 2019. }} Matija Bašić: '' Uvod u algebarsku topologiju - Parcijalno uređeni skupovi - O lancima i antilancima'', 21. svibnja 2014., str. 1 (pristupljeno 19. prosinca 2019.)</ref> |
||
Ekvivalentni poučci su [[Birkhoff-von Neumannov teorem za dvostruko stohastičke matrice]], [[Ford-Fulksersonov teorem o protoku u mrežama]] i dr.<ref name=Bašić/> |
Ekvivalentni poučci su [[Birkhoff-von Neumannov teorem za dvostruko stohastičke matrice]], [[Ford-Fulksersonov teorem o protoku u mrežama]] i dr.<ref name=Bašić/> |
||
Inačica od 10. kolovoza 2021. u 09:28
Königov poučak, matematički poučak. Nosi ime po matematičkom teoretičaru grafova Dénesu Kőnigu. Broj bridova u bipartitnom grafu u maksimalnom sparivanju jednak je broju vrhova u minimalnom pokrivaču tog grafa. Sparivanjem se naizva skup bridova za koji ne postoje dva brida iz tog skupa koji imaju zajednički vrh. Pokrivač je skup vrhova za koji vrijedi da svaki brid im barem jedan kraj u nekom od tih vrhova.[1]
Ekvivalentni poučci su Birkhoff-von Neumannov teorem za dvostruko stohastičke matrice, Ford-Fulksersonov teorem o protoku u mrežama i dr.[1]
Izvori
- ↑ a b PMF Zagreb Arhivirana inačica izvorne stranice od 19. prosinca 2019. (Wayback Machine) Matija Bašić: Uvod u algebarsku topologiju - Parcijalno uređeni skupovi - O lancima i antilancima, 21. svibnja 2014., str. 1 (pristupljeno 19. prosinca 2019.)