grafos algoritmo

1003 palavras 5 páginas
Universidade Estadual e Maringá

Estrutura de grafos - Algorítmo

Acadêmicos: Tiago Timóteo Zenon R.A.: 53648

Maringá-PR

Introdução Neste trabalho abordaremos um pedaço da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas. Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.
Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta. Note que essa representação gráfica (o layout) não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Vários diferentes layouts podem corresponder ao mesmo grafo.2 O que importa é quais vértices estão conectados entre si por quantas arestas. O grafo de exemplo exibido à direita é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } (com o mapeamento w sendo a identidade).
Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm

Relacionados

  • Algoritmos em grafos
    2963 palavras | 12 páginas
  • Algoritmos de grafos
    1431 palavras | 6 páginas
  • Algoritmo para Resolução de Grafos
    1560 palavras | 7 páginas
  • Comparativo entre algoritmos em grafos e programação matemática
    3121 palavras | 13 páginas
  • Algoritmo Para C Lculo De Centralidade Em Grafos
    6662 palavras | 27 páginas
  • Classe Grafo do algoritmo de prim
    507 palavras | 3 páginas
  • Estudo comparativo de algoritmos de busca com menor caminho em grafos
    2289 palavras | 10 páginas
  • Utilização de correspondência de grafos para reconhecimento de cenas através de algoritmos genéticos
    1067 palavras | 5 páginas
  • grafos- UFMG
    9612 palavras | 39 páginas
  • Teoria de grafos
    786 palavras | 4 páginas