نظریه گراف: یک دوره NPTEL

1 Preliminaries (5 - 10 lectures) 1.1 Introduction: Discovery of graphs . . . . . . . . . . . . . . . . . . . . 2 1.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 • Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 • Pictorial representation of a graph . . . . . . . . . . . . . . . . 4 • Isomorphic graphs . . . . . . . . . . . . . . . . . . . . . . . . 6 • Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 • Matrix representations of graphs . . . . . . . . . . . . . . . . 9 • Degree of a vertex . . . . . . . . . . . . . . . . . . . . . . . . 11 • Special graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 • Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 • Larger graphs from smaller graphs . . . . . . . . . . . . . . . 16 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Cartesian Product . . . . . . . . . . . . . . . . . . . . . . . 17 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Graphic sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 • Graph theoretic model of the LAN problem . . . . . . . . . . 20 • Havel-Hakimi criterion . . . . . . . . . . . . . . . . . . . . . . 21 • Realization of a graphic sequence . . . . . . . . . . . . . . . . 22 • Erd ̈s-Gallai criterion . . . . . . . . . . . . . . . . . . . . . . . 25 o Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2 Connected graphs and shortest paths (4-8 lectures) 33 2.1 Walks, trails, paths, cycles . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 • Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 • Cut-vertices and cut-edges . . . . . . . . . . . . . . . . . . . . 44 • Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.4 Weighted graphs and shortest paths . . . . . . . . . . . . . . . . . . . 55 • Weighted graphs . . . . . . . . . . . . . . . . . . . . . . . . . 56 • Dijkstra’s shortest path algorithm . . . . . . . . . . . . . . . . 57 • Floyd-Warshall shortest path algorithm . . . . . . . . . . . . . 61 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3 Trees (5 - 10 lectures) 71 3.1 Definitions and characterizations . . . . . . . . . . . . . . . . . . . . 72 3.2 Number of trees (Optional) . . . . . . . . . . . . . . . . . . . . . . . 75 • Cayley’s formula . . . . . . . . . . . . . . . . . . . . . . . . . 77 • Kircho↵-matrix-tree theorem . . . . . . . . . . . . . . . . . . . 79 Minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . 83 • Kruskal’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . 84 • Prim’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 88 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.3 4 Special classes of graphs(6 - 12 lectures) 97 4.1 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.2 Line Graphs (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 Chordal Graphs (Optional) . . . . . . . . . . . . . . . . . . . . . . . . 107 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5 Eulerian Graphs (2 - 4 lectures) 119 5.1 Motivation and origin . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.2 Fleury’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.3 Chinese Postman problem (Optional) . . . . . . . . . . . . . . . . . . 128 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6 Hamilton Graphs (4 - 8 lectures) 135 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 6.2 Necessary conditions and su cient conditions . . . . . . . . . . . . . 137 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 7 Independent sets, coverings and matchings(8-16lectures) 151 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 7.2 Independent sets and coverings: basic equations . . . . . . . . . . . . 152 7.3 Matchings in bipartite graphs . . . . . . . . . . . . . . . . . . . . . . 159 • Hall’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 160 • K ̈nig’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 163 o 7.4 Perfect matchings in graphs . . . . . . . . . . . . . . . . . . . . . . . 167 7.5 Greedy and approximation algorithms (Optional) . . . . . . . . . . . 172 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 8 Vertex Colorings (4 - 8 lectures) 179 8.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.2 Cliques and chromatic number . . . . . . . . . . . . . . . . . . . . . . 182 • 8.3 Mycielski’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 182 Greedy coloring algorithm . . . . . . . . . . . . . . . . . . . . . . . . 184 • Coloring of chordal graphs (Optional) . . . . . . . . . . . . . . 187 • Brooks theorem (Optional) . . . . . . . . . . . . . . . . . . . . 188 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 9 Edge Colorings (8 - 16 lectures) 195 9.1 Introduction and Basics . . . . . . . . . . . . . . . . . . . . . . . . . 196 9.2 Gupta-Vizing theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 198 9.3 Class-1 and Class-2 graphs . . . . . . . . . . . . . . . . . . . . . . . . 201 • • Class-2 graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 • 9.4 Edge-coloring of bipartite graphs . . . . . . . . . . . . . . . . 202 Hajos union and Class-2 graphs (Optional) . . . . . . . . . . . 208 A scheduling problem and equitable edge-coloring (Optional) . . . . . 210 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 10 Planar Graphs (10 - 20 lectures) 217 10.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 10.2 Euler’s formula and its consequences . . . . . . . . . . . . . . . . . . 223 10.3 Polyhedrons and planar graphs (Optional) . . . . . . . . . . . . . . . 226 MODULES v 10.4 Characterizations of planar graphs . . . . . . . . . . . . . . . . . . . 231 • Subdivisions and Kuratowski’s characterization . . . . . . . . 231 • Minors and Wagner’s theorem . . . . . . . . . . . . . . . . . . 241 10.5 Planarity testing (Optional) . . . . . . . . . . . . . . . . . . . . . . . 242 • D-M-P-planarity algorithm . . . . . . . . . . . . . . . . . . . . 243 10.6 5-Color-theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 11 Directed Graphs (8 - 16 lectures) 255 11.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 • Underlying graph of a digraph . . . . . . . . . . . . . . . . . . 257 • Out-degrees and in-degrees . . . . . . . . . . . . . . . . . . . . 258 • Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 11.2 Directed walks, paths and cycles . . . . . . . . . . . . . . . . . . . . . 259 • Connectivity in digraphs . . . . . . . . . . . . . . . . . . . . . 261 11.3 Orientation of a graph . . . . . . . . . . . . . . . . . . . . . . . . . . 265 11.4 Eulerian and Hamilton digraphs . . . . . . . . . . . . . . . . . . . . . 268 • Eulerian digraphs . . . . . . . . . . . . . . . . . . . . . . . . . 268 • Hamilton digraphs . . . . . . . . . . . . . . . . . . . . . . . . 269 11.5 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278