Grafy z wagami Przez zdefiniowanie funkcji z lub w pewien zbiór można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji. Etykiety liczbowe są często nazywane wagami, a graf grafem z wagami (grafem z ważeniem, grafem ważonym).
W grafie ważonym krawędziowo zbiór tworzący graf jest rozszerzony o funkcję taką, że dla każdej krawędzi jest wagą danej krawędzi.
Grafem ważonym wierzchołkowo nazywa się graf w którym jest funkcją przypisującą każdemu wierzchołkowi pewną liczbę naturalną nazywaną wagą wierzchołka. Graf taki oznacza się przez (lub po prostu a to, że jest ważony wynika z kontekstu), natomiast wagę wierzchołka oznacza się przez .
Warianty definicji W wielu zastosowaniach podstawowe definicje grafów nie są wystarczające, dlatego wprowadza się pewne modyfikacje. Na przykład aby wprowadzić pętlę, czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe albo użyć dwuelementowego multizbioru W grafie skierowanym pętla jest naturalnie reprezentowana przez parę .