Universidad avanzadaDiscrete MathematicsPlanificado
Graph theory
Connectivity, matchings and Hall's theorem, colouring, planarity and Euler's formula, extremal results such as Turán's theorem, and Ramsey theory.
math.discrete.graph-theory
La lección de este tema todavía no se ha escrito. El esquema siguiente forma parte del mapa del plan de estudios y no ha sido revisado.
Se basa en
Requisitos previos obligatorios, hasta el fondo: 18
Aprenderás a
- Prove Hall's marriage theorem and apply it.
- Prove Euler's formula V − E + F = 2 for connected plane graphs and deduce that K₅ and K₃,₃ are not planar.
- Prove that R(3, 3) = 6 and establish upper bounds for Ramsey numbers.
Definición
- A matching is a set of edges no two of which share a vertex.
- A proper k-colouring assigns one of k colours to each vertex so that adjacent vertices receive different colours.
- The Ramsey number R(s, t) is the least n such that every red–blue colouring of the edges of Kₙ contains a red K_s or a blue K_t.
Teorema
- Hall: a bipartite graph with parts A and B has a matching covering A if and only if |N(S)| ≥ |S| for every S ⊆ A.
- Four colour theorem (Appel and Haken, 1976): every planar graph is 4-colourable; the proof relies on computer verification.
- Kuratowski: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.
- R(3, 3) = 6.
Errores frecuentes
- Thinking a graph is planar only if a given drawing has no crossings; it is planar if some drawing has none.
- Assuming the four colour theorem has a short proof checkable by hand; known proofs use computers, and one has been formally verified in Coq.
Conduce a
Descubrimientos opcionales
- Computational complexity Deciding whether a graph is 3-colourable is NP-complete.
- ← Algorithm design and analysis
Itinerarios de aprendizaje
Lecturas complementarias
- Reinhard Diestel, Graph Theory
- J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)