Shahada ya kwanza (juu)Discrete MathematicsImepangwa
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
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 18 (hadi chini kabisa)
Utajifunza
- 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.
Fasili
- 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.
Nadharia
- 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.
Mawazo potofu ya kawaida
- 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.
Inaelekea kwa
Ugunduzi wa hiari
- Computational complexity Deciding whether a graph is 3-colourable is NP-complete.
- ← Algorithm design and analysis
Njia za kujifunza
Usomaji zaidi
- Reinhard Diestel, Graph Theory
- J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)