Grafos

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 desconexo onde 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
4 GRAFOS 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 conter valor 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 E