CCT-UFCA/Ciência da Computação/Teoria dos Grafos

Programa do Componente Curricular

Código:	CC0060
Componente Curricular:	Teoria dos Grafos
Semestre de Oferta:	-		Tipo:	Disciplina	Caráter:	Optativa
Unidade Acadêmica Responsável:	Centro de Ciências e Tecnologia - CCT
Área:	Matemática
Créditos:	4	Carga horária:	64	Teórica:	64	Prática:	-	Extensão:	-
Pré-requisito:	CC0005 - Fundamentos de Matemática Discreta
Co-requisito:	-
Equivalência:	-

Objetivos

A teoria dos grafos é usada na modelagem de muitos problemas computacionais. Esta disciplina tem o objetivo de introduzir o aluno à linguagem e aos problemas básicos da teoria. A disciplina complementa Algoritmos em Grafos, que trata dos aspectos mais algorítmicos da teoria.

Ementa

Grafos. Isomorfismo. Caminhos e circuitos. Subgrafos. Cortes e pontes. Grafos conexos. Árvores. Grafos aresta-biconexos. Grafos bipartidos. Grafos eulerianos. Grafos hamiltonianos. Emparelhamentos em grafos bipartidos. Conjuntos estáveis e cliques. Coloração de arestas. Coloração de vértices. Noções de planaridade.

Conteúdo

• Grafos:
  • Definição e tipos de grafos (simples, direcionados, ponderados)
  • Representação de grafos (matriz de adjacência, lista de adjacência)
• Isomorfismo:
  • Conceito de isomorfismo de grafos
  • Métodos para determinar se dois grafos são isomorfos
• Caminhos e Circuitos:
  • Definição de caminho e circuito
  • Tipos de caminhos (simples, euleriano, hamiltoniano)
  • Algoritmos para encontrar caminhos e circuitos
• Subgrafos:
  • Conceito de subgrafo
  • Tipos de subgrafos (induzidos, próprios)
• Cortes e Pontes:
  • Definição de cortes e pontes
  • Identificação de cortes e pontes em grafos
• Grafos Conexos:
  • Conceito de grafos conexos
  • Componentes conexas
• Árvores:
  • Definição de árvore
  • Propriedades das árvores
  • Algoritmos para árvores geradoras mínimas (Kruskal, Prim)
• Grafos Aresta-Biconexos:
  • Definição e propriedades
  • Identificação de grafos aresta-biconexos
• Grafos Bipartidos:
  • Definição de grafos bipartidos
  • Características e exemplos
• Grafos Eulerianos:
  • Definição de grafos eulerianos
  • Condições para a existência de circuitos eulerianos
  • Algoritmo de Fleury
• Grafos Hamiltonianos:
  • Definição de grafos hamiltonianos
  • Critérios para a existência de circuitos hamiltonianos
• Emparelhamentos em Grafos Bipartidos:
  • Conceito de emparelhamento
  • Algoritmos para encontrar emparelhamentos máximos
• Conjuntos Estáveis e Cliques:
  • Definição de conjuntos estáveis e cliques
  • Métodos para encontrar conjuntos estáveis e cliques
• Coloração de Arestas:
  • Conceito de coloração de arestas
  • Algoritmos de coloração
• Coloração de Vértices:
  • Conceito de coloração de vértices
  • Algoritmos de coloração (algoritmo de coloração gulosa)
• Noções de Planaridade:
  • Definição de grafos planares
  • Critérios de planaridade (Teorema de Kuratowski)
  • Algoritmos para testar a planaridade

Metodologia

A metodologia adotada na disciplina inclui aulas teóricas, onde são explicados detalhadamente os conceitos de álgebra vetorial e geometria analítica. Além das aulas teóricas, os alunos realizam a resolução de exercícios, que são propostos para aplicar os conhecimentos adquiridos e reforçar o entendimento dos conteúdos abordados.

Avaliação

A avaliação dos alunos pode ser composta por diferentes métodos, incluindo provas teóricas que abrangem os conteúdos teóricos estudados ao longo do curso. Alternativamente, a avaliação pode incluir tanto provas teóricas quanto trabalhos, que podem ser individuais ou em grupo. Além disso, a participação dos alunos nas aulas e a realização dos exercícios propostos podem ser considerados como parte da avaliação contínua. A participação nas aulas pode ou não ser um critério de avaliação, dependendo dos critérios estabelecidos pelo professor.

Bibliografia Básica

1. WEST, D. Introduction to Graph Theory, 2nd ed., Pearson, 2000, 608p. ISBN-10: 9780131437371, ISBN-13: 978-0130144003.
2. BONDY, J.; MURTY, U. Graph Theory, 1st Corrected ed., Springer, 2008, 668p. ISBN-10: 1846289696, ISBN-13: 978-1846289699.
3. DIESTEL, R. Graph Theory. 5th ed., Springer, 2018, 448p. ISBN-10: 3662575604 , ISBN-13: 978-3662575604.

Bibliografia Complementar

1. NETTO, P. Grafos. Teoria, Modelos, Algoritmos. 5a ed., Edgard Blucher, 2012, 314p. ISBN-10: 8521206801, ISBN-13: 978-8521206804.
2. TRUDEAU, R. Introduction to Graph Theory, 2nd Revised ed., Dover Publications, 1994. 224p. ISBN-10: 0486678709, ISBN-13: 978-0486678702.
3. CHARTRAND, G.; ZHANG, P. A First Course in Graph Theory. Dover Publications, 2012, 450p. ISBN-10: 0486483681, ISBN-13: 978-0486483689.
4. BOLLOBAS, B. Modern Graph Theory, Corrected edition (October 4, 2002), Springer, 394p. ISBN-10: 0387984887, ISBN-13: 978-0387984889.
5. GOULD, R. Graph Theory, Dover Publications; Reprint edition (November 21, 2012), 352p. ISBN-10: 0486498069, ISBN-13: 978-0486498065.