Estrutura de dados (grafos)

2461 palavras 10 páginas
TRABALHO DE ESTRUTURA DE DADOS

Grafos

Definição para Grafo:

Um Grafo é uma forma de representar relacionamentos que existem entre pares de objetos. Isto é um conjunto de objetos, chamados vértices, juntamente com uma coleção entre pares de vértices. A propósito, esta noção de “grafos” não deve ser confundida com diagrama de barras de funções plots.
Visto de forma abstrata, um grafo (G) é simplesmente um conjunto (V) de vértices e uma coleção (E) de pares de vértices de (V), chamados de arestas. Assim um grafo é uma forma de representar conexões ou relações entre pares de objetos de algum conjunto (V). Alguns livros usam uma terminologia diferente para grafos e referem-se ao que se chama de vértices, como nodos; e ao que se chama de arestas, como arcos. Serão utilizados aqui o termo “vértices” e “arestas”.
As arestas em um grafo podem ser dirigidas ou não- dirigidas. Uma aresta (u,v) é dita dirigida de (u) para (v) se o par (u,v)for ordenado,com (u) precedendo (v).Uma aresta (u,v) é dita não-dirigida se o par (u,v) não for ordenado.

Os grafos são visualizados tipicamente desenhando-se os vértices como ovais ou retângulos e as arestas como segmentos ou curvas conectando pares de ovais ou retângulos. A seguir são apresentados alguns exemplos de grafos dirigidos e não-dirigidos.

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o

Relacionados

  • O Corpo Fala (Ricardo Serravalle Guimarães) 101
    784 palavras | 4 páginas
  • Grafos
    1368 palavras | 6 páginas
  • Baricentro
    5138 palavras | 21 páginas
  • nao sei
    1860 palavras | 8 páginas
  • Graduando
    2298 palavras | 10 páginas
  • EO A1 Estrutura de dados Final
    1012 palavras | 5 páginas
  • pesquisa e ordenação
    3072 palavras | 13 páginas
  • Rvores
    815 palavras | 4 páginas
  • ATPS 1 BimVFinal
    3364 palavras | 14 páginas
  • hooke
    2869 palavras | 12 páginas