Uteženi graf

Iz MaFiRaWiki

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.

Glej tudi

Osebna orodja