Vægt (grafteori)

Fra Wikipedia, den frie encyklopædi
Jump to navigation Jump to search
Disambig bordered fade.svg For alternative betydninger, se Vægt. (Se også artikler, som begynder med Vægt)

En graf kaldes for en vægtet graf, hvis hver kant i grafen har en tilknyttet vægt; dvs. en værdi som typisk er et tal. Afhængig af hvad grafen modellere, kan disse kant vægte repræsenter forskellige ting. Det kan f.eks. være afstand (som i TSP), tid, hastighed og mange andre fænomener.