Teoria dos grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 13 (3241 palavras )
  • Download(s) : 0
  • Publicado : 26 de novembro de 2012
Ler documento completo
Amostra do texto
Origem: Wikipédia, a enciclopédia livre.

Esta página precisa ser reciclada de acordo com o livro de estilo.
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Editor: considere colocar o mês e o ano da marcação. Isso pode ser feito automaticamente, substituindo esta predefinição por {{subst:rec}}


Grafo com 4 vértices e 6 arestas. É um grafocompleto, conexo e planar.
A teoria dos grafos é um ramo 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 serpermitido 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 ou "o ponto".
Estruturas que podem ser representadas porgrafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de links da Wikipedia pode ser representada por um dígrafo: os vértices são os artigos da Wikipedia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estadofinito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.
Índice [esconder]
1 Histórico
1.1 Definições de grafos e digrafos
1.2 Representação gráfica (layout do grafo)
1.3 Glossário dos conceitos básicos de teoria dos grafos
2 Problemas que envolvem grafos
3 Algoritmos importantes
4 Generalizações
5 Referências
6 Ligações externas
6.1 Eminglês
6.2 Em português
6.3 Ferramentas de grafos populares
7 Ver também
[editar]Histórico

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das sete pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos.[1] É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profundaconexão entre a teoria dos grafos e topologia.
[editar]Definições de grafos e digrafos
Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia.
Um grafo direcionado (também chamado digrafo ou quiver) consiste de
um conjunto V de vértices,
um conjunto E de arestas e
mapas s, t : E → V, onde s(e) é a fonte e t(e) é o alvo daaresta direcionada e.
Um grafo não direcionado (ou simplesmente grafo) é dado por
um conjunto V de vértices,
um conjunto E de arestas e
uma função w : E → P(V) que associa a cada aresta um subconjunto de dois ou de um elemento de V, interpretado como os pontos terminais da aresta.
Em um grafo ou digrafo com pesos, uma função adicional E → R associa um valor a cada aresta, o que pode serconsiderado seu "custo"; tais grafos surgem em problemas de rota ótima tais como o problema do caixeiro viajante.
[editar]Representação gráfica (layout do grafo)
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 arestapor 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.
[editar]Glossário dos conceitos básicos de teoria dos grafos


Um grafo com 6 vértices e 7 arestas
O grafo de...
tracking img