Disciplina Discipline MAC5771
Teoria dos Grafos

Graph Theory

Área de Concentração: 45134

Concentration area: 45134

Criação: 25/06/2021

Creation: 25/06/2021

Ativação: 25/06/2021

Activation: 25/06/2021

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docente Responsável:

Professor:

Yoshiko Wakabayashi

Objetivos:

Estudar resultados estruturais e algorítmicos fundamentais da teoria dos grafos.

Objectives:

To study fundamental structural and algorithmic results in graph theory.

Justificativa:

A teoria dos grafos é uma disciplina fundamental da área de matemática discreta e algorítmica. Conhecer as técnicas e resultados desta disciplina é essencial para aqueles que desejam fazer pesquisa na área de combinatória, algoritmos e otimização combinatória.

Rationale:

Graph theory is a fundamental area in discrete and algorithmic mathematics. It is essential to know the techniques and results in this area in order to do research in combinatorics, algorithms, and combinatorial optimization.

Conteúdo:

1. Conexidade; estrutura de grafos 2-conexos e 3-conexos. Teorema de Menger. 2. Emparelhamento máximo; teorema de Tutte; algoritmo de Edmonds. 3. Coloração de vértices. Lista coloração. Grafos perfeitos. 4. Problemas extremos; teorema de Turán e o teorema de Erdös e Stone. 5. Teoria de Ramsey. 6. Grafos planares; teorema de Kuratowski. Dualidade planar. Espaços dos ciclos e dos cociclos. Outras caracterizações de planaridade. 7. Fluxos e dualidade fluxos-colorações. 8. Menores. O minor theorem para árvores. Decomposição arbórea.

Content:

1. Connectivity; the structure of 2- and 3-connected graphs. Menger's Theorem. 2. Maximum matchings; Tutte's Theorem; Edmonds' Algorithm. 3. Vertex and list colouring. Perfect graphs. 4. Extremal problems; Turán's Theorem and the Erdős-Stone Theorem. 5. Ramsey Theory. 6. Planar graphs; Kuratowski's Theorem. Plane duality. Cycle and cocycle spaces. Other planarity characterizations. 7. Flows and flow-colouring duality. 8. Minors. The minor theorem for trees. Tree decomposition.

Forma de Avaliação:

Média de provas e exercícios.

Bibliografia:

[1] B. Bollobás, Modern graph theory, Springer-Verlag, Berlin, 1998. [2] J. A. Bondy e U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, Springer-Verlag, 2008. [3] R. Diestel, Graph theory, Springer-Verlag, 1996 (1ª. ed.), 2000 (2ª. ed.), 2005 (3ª.ed.). [4] László Lovász, Combinatorial problems and exercises. Corrected reprint of the 1993 second edition. AMS Chelsea Publishing, Providence, RI, 2007.

Bibliography:

[1] B. Bollobás, Modern graph theory, Springer-Verlag, Berlin, 1998. [2] J. A. Bondy e U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, Springer-Verlag, 2008. [3] R. Diestel, Graph theory, Springer-Verlag, 1996 (1ª. ed.), 2000 (2ª. ed.), 2005 (3ª.ed.). [4] László Lovász, Combinatorial problems and exercises. Corrected reprint of the 1993 second edition. AMS Chelsea Publishing, Providence, RI, 2007.

Tipo de oferecimento da disciplina:

Presencial

Class type:

Presencial