Grafo valorado
Um grafo valorado ou grafo ponderado[1] é um grafo que possui funções relacionando o conjunto de vértices ou o conjunto de arestas a conjunto de números.[2][3]
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[3] . 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.[4] Na lista de adjacência cada linha vem acompanhada de seus valores respectivos[4] . A figura a seguir ilustra um exemplo:
| Grafo valorado | Matriz de valores |
|---|---|
|