Um grafo valorado ou grafo ponderado é um grafo que possui funções relacionando o conjunto de vértices ou o conjunto de arestas a conjunto de números.
O significado das funções depende do problema. Na maioria das aplicações de grafos existem dados quantitativos associados a pontos(vértices) ou ligações(arestas) relacionados ao problema . Na maioria das aplicações de grafos a problemas de engenharia, é necessário considerar-se grandezas tais como distâncias, altitudes, capacidades, fluxos, etc., associadas a localidades, estradas, etc. que definem os vértices e os arcos (ou arestas) do grafo.
Em muitos problemas, no entanto, interessa apenas o inter-relacionamento dos vértices - e não se definem funções, ou se pode considerar que elas são constantes. Diz-se então que o grafo é um grafo não-valorado.
Representação Em um grafo valorado se pode usar as representações usuais para grafos. A matriz de adjacência é comumente conhecida como matriz de valores das ligações ou simplesmente matriz de valores. Na lista de adjacência cada linha vem acompanhada de seus valores respectivos . A figura a seguir ilustra um exemplo:
Grafo valoradoMatriz de valores250px
Ver também Grafo Algoritmo de Kruskal Algoritmo de Prim Algoritmo de Dijkstra
Categoria:Teoria dos grafos Categoria:Estruturas de dados