Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2376 palavras )
  • Download(s) : 0
  • Publicado : 21 de janeiro de 2013
Ler documento completo
Amostra do texto
ESTÁCIO FIB – CENTRO UNIVERSITÁRIO

TIAGO MESQUITA DE ARAÚJO CUNHA


GRAFOS E SEUS RESPECTIVOS TIPOS

Salvador
2012
TIAGO MESQUITA DE ARAÚJO CUNHA


GRAFOS E SEUS RESPECTIVOS TIPOS

Trabalho apresentado como requisito parcial para avaliação da disciplina Teoria dos Grafos e Complexidade de Algoritmos, do curso de Ciência da Computação, sob a orientação do Professor Antônio JoséAssunção Cordeiro.

Salvador
2012

LISTA DE FIGURAS

Figura 1 - Exemplo de grafo. 5
Figura 2 - Exemplo de grafo não planar (a) e planar (b). 6
Figura 3 - Exemplo de grafo completo. 7
Figura 4 - Exemplos de grafos completos. 7
Figura 5 - Exemplo de grafo bipartido. 8
Figura 6 - Exemplo de grafo conexo onde todos os vértices possuem conexão. 9
Figura 7 - Exemplo de grafo desconexoonde ocorre um vértice sem aresta de ligação. 9
Figura 8 - Exemplo de grafo regular 10
Figura 9 - Exemplo de grafo regular de ordem 3. 10
Figura 10 - Exempos de grafos Eulerianos 11
Figura 11 - Exemplo de grafo hamiltoniano 12
Figura 12 - Exemplo de grafo árvore 13
Figura 13 - Exemplo de grafo Floresta 14

* SUMÁRIO

1 INTRODUÇÃO 5
2 GRAFOS PLANARES 5
3 GRAFOS COMPLETOS 6
4GRAFOS BIPARTIDOS 7
5 GRAFOS CONEXOS 8
6 GRAFOS REGULARES 10
7 GRAFO EULERIANO 11
8 GRAFOS HAMILTONIANOS 12
9 GRAFOS ÁRVORES 13
10 GRAFOS FLORESTAS 14
11 CONCLUSÃO 15
12 REFERENCIAS 15

INTRODUÇÃO

Conforme (LIPSCHUTZ, 2004) os grafos em sua forma geral são elementos que se relacionam através de nós ou vértices de algum modo, que pode ser arcos ou arestas. Essas relações podem contervalor e não existem restrições.
A formalização de grafos pode ser dada pela definição: G = {V,E}, onde V é um conjunto de nós ou vértices e E é um conjunto de relações, sendo arcos ou arestas entre nós vizinhos. Conforme podemos visualizar no exemplo abaixo na figura 1:

Figura 1 - Exemplo de grafo. Fonte (LIPSCHUTZ, 2004)

Nesse exemplo é possível visualizar uma estrutura formada por V e Eonde V = {0,1,2,3,4} e E é formada pelo grupo dos valores E = {(1,2),(1,3),(3,4),(4,1),(0,0)}. (Duarte).

Os grafos podem ser classificados em tipos diferentes como Dirigidos ou não-dirigidos, Cíclicos ou acíclicos e conexo ou desconexo. Quanto a classificação existem duas classificações importantes de grafos: Implícita, que surge em vários problemas; explícitas, comuns e mais fáceis detrabalhar. (Duarte)

GRAFOS PLANARES

Grafos planares são aqueles que podem ser desenhados em um plano onde suas arestas não se cortam. Um grafo completo com 4 vértices pode ser representado conforme a figura 2 a baixo, podemos notar no primeiro exemplo (a) que existe o corte de arestas, apesar disso o mesmo gráfico de 4 vértices pode ser representado conforme o exemplo (b) onde não existe o corte dearestas, de modo planar (LIPSCHUTZ, 2004).

Figura 2 - Exemplo de grafo não planar (a) e planar (b). Fonte (LIPSCHUTZ, 2004)

Conforme (Patricio, 2006) um grafo planar é aquele que divide o plano em região por suas arestas, onde cada uma dessas divisões pode ser denominada de face do grafo. Sendo assim é possível dizer que dois pontos do plano estão na mesma face apenas se existir uma curva doplano que os une sem cortar nenhuma das arestas desse grafo.

Abaixo segue algumas informações importantes que podemos observar quanto aos grafos planares observadas a partir de (Patricio, 2006):

* Todo grafo plano (V,E) corresponde naturalmente a um grafo “abstrato”.
* Um grafo plano é um subconjunto fechado e limitado do plano R².
* Uma face de um grafo plano G é qualquer regiãodo conjunto aberto R² -G, sendo que H é subgrafo de G então toda face de H é parte de uma face de G.
* Não existe grafo plano isomorfo a K^5.
GRAFOS COMPLETOS

(Patricio, 2006) define um grafo completo como sendo um grafo onde todos os vértices são adjacentes a todos os outros vértices existentes nesse grafo. Na imagem 3 podemos visualizar um grafo completo onde todos os vértices são...
tracking img