Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 16 (3905 palavras )
  • Download(s) : 0
  • Publicado : 16 de setembro de 2012
Ler documento completo
Amostra do texto
Introdução

Um grafo é uma estrutura matemática usada para representar as relações entre as coisas, para facilitar sua visualização e sua compreensão, grafos são representados graficamente eles tem diversas aplicações e pode nos ajudar a resolver problemas práticos.
Este trabalho formaliza a definição de grafos, desde seus primeiros resultados, também mostra conceitos básicos, suasrepresentações geométricas e exemplos de aplicação. Fala também sobre complementos , representação com matrizes e coloração de grafos e dígrafo (ou um grafo dirigido).

GRAFOS

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. É também considerado um dos primeiros resultados topológicos na geometria; istoé, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

1. Definição

Antes de mais nada, vamos tentar entender o que é um grafo. Um grafo é uma estrutura matemática usada para representar as relações entre as coisas.
Essas "coisas" que se relacionam entre si são chamados de nós do grafo. Cada relacionamento entre os nós é chamadode aresta. Normalmente, para facilitar sua visualização e sua compreensão, grafos são representados graficamente. Não confunda as duas palavras! Grafos são entidades matemáticas, abstratas, que possuem nós (coisas) e arestas (relacionamento entre essas coisas). Gráficos são imagens. Grafos podem ser representados graficamente, mas o grafo não é a sua representação gráfica - existem várias outrasmaneiras de representar grafos que não graficamente.
Um grafo é um tipo especial de dígrafo, também conhecido como grafo não-dirigido e grafo não-orientado. Um grafo é um dígrafo simétrico. Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v.
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 evé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 dígrafo.
Convém tratar esse par de arcos com distinção. Assim, diremos que um par de arcos anti-paralelos é uma aresta (= edge). As pontas dos dois arcos são as pontas da aresta. As duas pontas de uma arestasão indistinguíveis: não há ponta inicial nem ponta final.
Uma aresta com pontas v e w será denotada, indiferentemente, por v-w ou w-v.
Diremos que uma aresta v-w liga os vértices v e w. Diremos também que v-w incide em v e em w. O número de arestas de um grafo é a metade do seu número de arcos. Se E denota o número de arestas e A denota o número de arcos então A = 2•E. 

2. ConceitosBásicos

Grafo G (V,E)
V é um conjunto finito não-vazio. 
E é um conjunto de pares não ordenados de elementos distintos de V.

V = {1, 2, 3, 4, 5}
E = {(1, 2), (1, 4), (2, 3), (2, 5), (4, 3), (5, 1)}

Elementos de V são vértices de G, e os de E são as arestas de G.
Cada aresta e pertencente a E será denotada pelo par de vértices e = (v,w) que a forma. Os vértices v e w são os extremos daaresta e sendo denominados adjacentes. A aresta e é dita incidente a ambos os vértices v e w.
Duas arestas são adjacentes quando possuem um extremo comum.
Notação:
n = |V|
m = |E| 
quando |V| = 1, G é trivial

3. Representação Geométrica

Os vértices correspondem a pontos distintos do plano, em posições arbitrárias, enquanto que a aresta (v,w) é associada a uma linha arbitrária unindo ospontos v e w.

3.1 Laço 
Uma aresta do tipo e = (v,v)
3.2 Arestas Múltiplas 
Ocorre quando se permite a existência de mais de uma aresta entre o mesmo par de vértices.
3.3 Multigrafo 
É um grafo cujo conjunto de arestas contém laços e/ou arestas múltiplas.
3.4 Grau de um vértice v pertencente a V

É o número de vértices adjacentes a v.
3.5 Vértice...
tracking img