Uteženi graf
Iz MaFiRaWiki
[spremeni]
Definicija
Uteženi graf povezuje vsa vozlišča v grafu. Teže so navadno realna števila. Lahko so omejena na racionalna ali naravna števila. Določeni algoritmi zahtevajo nadaljne omejitve tež; npr. Dijkstrov algoritem deluje le za pozitivne uteži. Teža povezave ali teža drevesa je enaka vsoti tež izbranih vozlišč.
Če ni posebej označeno, je graf domnevno neutežen.
V posameznih teorijah je termin mreža sopomenka za uteženi graf. Mreža je lahko usmerjena ali neusmerjena, lahko vsebuje cikle.
Standardni problemi pri mrežah so:
- najcenejše vpeto drevo,
- najkrajša pot,
- maksimalni pretok.
[spremeni]
