Aula01
5723 palavras
23 páginas
TEORIA DOS GRAFOSAPRESENTAÇÃO DA DISCIPLINA
Prof. Paulo Malcher prcmalcher@gmail.com Sumário
• Apresentação da Disciplina
Apresentação do Professor
• Prof. Paulo Malcher
•
•
•
•
Bacharel em Ciência da Computação – UFPA
Mestre em Ciência da Computação – PPGCC-UFPA
Professor Faculdades Integradas Ipiranga
Pesquisador Laboratório Spider-UFPA
Apresentação da Disciplina
•
OBJETIVO GERAL
•
Introduzir conceitos e algoritmos da Teoria de
Grafos e sua aplicabilidade na computação.
Apresentação da Disciplina
•
OBJETIVOS ESPECÍFICOS
•
•
•
Identificar grafos e identificar problemas que podem ser modelados por grafos.
Apresentar os conceitos principais de grafos e a utilização de grafos em um contexto computacional.
Demonstrar a importância e a abrangência da
Teoria dos Grafos e mostrar as principais propriedades dos grafos.
Apresentação da Disciplina
•
OBJETIVOS ESPECÍFICOS
•
•
•
Identificar classes de grafos com propriedades específicas. Discutir algoritmos clássicos de grafos e suas aplicações. Mostrar que diferentes algoritmos de grafos podem resolver um mesmo problema e discutir sobre as vantagens e desvantagens de cada algoritmo e sobre suas limitações.
Apresentação da Disciplina
•
EMENTA
•
Definição e aplicação de grafos. Conceitos básicos de grafos. Representação de grafos em matrizes de adjacências e listas de adjacências. Caminhos de
Euler, grafos isomorfos e grafos planares.
Coloração de grafos e Teorema das quatro cores.
Problemas do caminho mínimo e da árvore geradora mínima.
Apresentação da Disciplina
•
CONTEÚDO PROGRAMÁTICO
1. Definição e Aplicações de Grafos
2. Terminologia da Teoria dos Grafos
3. Representação computacional de Grafos
3.1
3.2
Matriz de Adjacências
Lista de Adjacências
4. Caminho de Euler
5. Grafos Isomorfos
6. Grafos Planares
7. Coloração de Grafos e Teorema das quatro cores
Apresentação da Disciplina
•
CONTEÚDO PROGRAMÁTICO
8. Problema do Caminho Mínimo
8.1
8.2
Algoritmo de Dijkstra
Algoritmo de Floyd
9.