Teoria de grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1393 palavras )
  • Download(s) : 0
  • Publicado : 4 de junho de 2012
Ler documento completo
Amostra do texto
Teoria dos Grafos

A teoria dos grafos é um dos ramos da matemática discreta, assim como a lógica, a teoria dos números, a recursão entre outras. Todas se caracterizam pelo fato de não requererem ou suportarem a noção de continuidade.
Especificamente, a teoria dos grafos é o estudo dos grafos, elementos matemáticos usados para modelar uma série de problemas práticos, e as relações entreeles.

História
A primeira publicação sobre a teoria dos Grafos foi realizada pelo matemático Leonhard Euler, em 1736. Euler foi um importante matemático responsável também pelo sistema de notação utilizado na matemática atual e contribuiu para importantes avanços na Teoria dos Números e na Análise Numérica, entre outros campos. Após eles, outros matemáticos como Cauchy e L’Huillier continuaram otrabalho na área.
Euler resolveu em 1736, o problema das Sete Pontes de Könisberg, estabelecendo assim os primeiros conceitos da Teoria dos Grafos, os conceitos de vértice.


O problema consistia em passar por todos os pontos da cidade utilizando cada ponte apenas uma vez. Euler esquematizou o problema de forma que cada caminho fosse representado por umareta e cada intersecção por um ponto, criando assim o primeiro grafo da história.
Euler ainda observou que, só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos.
O problema das pontes de Könisberg representa um problema do tipo combinatório e sua resolução estilizada por Eulerabriu as portas para o surgimento posterior da topologia.

Conceituações
Um grafo é uma estrutura formada por dois tipos de objetos: vértices e arestas. Cada aresta é um par não ordenado de vértices, ou seja, um conjunto com exatamente dois vértices.

Uma aresta é a linha única que une 2 vértices. Assim, na figura abaixo temos 6 vértices e 7 arestas:

Em ciência da computação, o grafo é umaestrutura de dados abstrata que implementa operações do tipo:
adjacente(G,x,y): Testa se existe aresta entre o vértice x e y no grafos G.
neighbors(G, x): Lista todos os vértices que estejam conectados por uma aresta a x.
, etc. que são funções manipulativas dos grafo em si.

A partir desse conjunto de conceitos básicos, desdobram-se outras variadas conceituações, a saber:
* Grafosimples é um grafo não direcionado, sem laços e que existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). No grafo de exemplo dado acima, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.
* Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dosdemais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
* Grafo nulo é o grafo cujo conjunto de vértices é vazio.
* Grafo vazio é o grafo cujo conjunto de arestas é vazio.
* Grafo trivial é o grafo que possui apenas um vérticee nenhuma aresta.
* Grafo regular é um grafo em que todos os vértices têm o mesmo grau.
* Multigrafo é um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).
* Laço (loop) num grafo ou num dígrafo é uma aresta e em E cujas terminações estão no mesmo vértice.
* Pseudografo é um grafo que contém arestas paralelas e laços.
* Ciclo (ou circuito) éum caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo acima, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um...
tracking img