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
- ↑ 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 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ FURTADO, Antonio Luz (1973). Teoria dos Grafos. Algoritmos. Rio de Janeiro, Guanabara: LTC/Editora da USP. p. 2-3. CDD 511.2076
- ↑ a b BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 10. ISBN 85-212-0292-X
- ↑ 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 !CS1 manut: Nomes múltiplos: lista de autores (link)
Ver também
- Grafo
- Algoritmo de Kruskal
- Algoritmo de Prim
- Algoritmo de Dijkstra
