Vægt (grafteori)

Fra Wikipedia, den frie encyklopædi
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.