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

Referências

  1. ↑ GOODRICH, Michael T.; TAMASSIA, Roberto (2001). Estruturas de Dados e Algoritmos em Java 2ª ed. Porto Alegre: Bookman. p. 532-560. ISBN 85-363-0043-4 
  2. ↑ FURTADO, Antonio Luz (1973). Teoria dos Grafos. Algoritmos. Rio de Janeiro, Guanabara: LTC/Editora da USP. p. 2-3. CDD 511.2076 
  3. ↑ a b BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 10. ISBN 85-212-0292-X 
  4. ↑ a b BOAVENTURA NETTO, Paulo Oswaldo; JURKIEWICZ, Samuel (2009). Grafos:Introdução e Prática. São Paulo: Edgard Blücher. p. 19. ISBN 978-85-212-0473-2 

Ver também