Algoritimos

CEEP ISAIAS ALVES

Teoria de Grafos e suas Aplicações

SALVADOR
2014
CEEP ISAIAS ALVES
JAEMERSON SANTOS DA CONCEIÇÃO
EVANILDO NERES

Algoritmos

Trabalho apresentado à disciplina de algoritmos para obtenção de nota parcial nesta unidade.

SALVADOR
2014

Sumário

1. Definição formal de um grafo 1
2. Conceito 1
3. Principais tipos de grafos 2
4. Problema das sete pontes de Konigsberg 3
5. Problema 4
6. Modelo do problema 4
7. Solução 5
8. Teorema 5
9. Prova 5
10. Problema do caixeiro viajante 6
11. Definição e formulação do problema 6
12. Formulação combinatória 7
13. Representação continua do PCV Error: Reference source not found
14. Formulação gráfica 8
15. PCV assimétrico 9
16. PCV simétrico 10
17. Solução do PCV 11

DEFINIÇÃO FORMAL DE UM GRAFO
Grafos são modelos matemáticos utilizados para estudar as relações entre objetos de um conjunto. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

CONCEITO
Grafo: É o conjunto de vértices e arestas.

Vértice: Em teoria dos grafos, um vértice é a unidade fundamental da qual os grafos são formados. É objeto simples que pode ter nome e outros atributos.

Aresta: Uma aresta junto com os vértices forma as unidades fundamentais das quais os grafos são formados. Uma aresta pode ser não-direcionada ou direcionada.
Diversas aplicações podem ser representadas por grafos: