Outline

• Connections and searching through a graph
  principles of the depth-first search and breadth-first search algorithms,
  walks and paths in a graph, connected components
• Minimum spanning tree (MST) problem
  definition of MST, Jarník's algorithm (later known as Prim's algorithm)
• Higher levels of connectivity
  k-connected and k-edge connected graphs, characterization of 2-connected graphs ("ear addition"), Menger's theorem (see also Lecture 4)
• Connectivity variants for digraphs
  weak and strong connectivity of digraphs, reachability, strong components
• ~optional~  Eulerian tours and trails
  tours (closed) and trails (not closed) in a graph - no repetition of edges, Eulerian graphs ("seven bridges") and the even degree condition

Goals

The lecture continues on Lecture 1, reviewing how to systematically handle a graph — so called graph search routines (algorithms). The related theoretical notions are those of connectivity and of spanning trees which are traditional and very common in applications of graphs. More advanced content includes dealing with higher levels of connectivity (i.e., with "redundance" of connections in the graph) and with the notion of graph minors (generalizing subgraphs).

                   

Study materials

Course book [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]

Study the beginning of Section 4.2 (Subgraphs, components, adjacency matrix), and Sections 4.6 (2-connectivity) and 5.4 (The minimum spanning tree problem) – 5.5 (Jarnı́k’s algorithm and Borůvka’s algorithm).

Go to [Diestel] below for further study of higher graph connectivity and of the notion of graph minors.

Advanced course book [Graph theory (by Reinhard Diestel)]

Study Sections 1.4 and 1.7-1.8, for more advanced also Sections 3.1-3.3

.

Algorithmic aspects of the lecture

The presented (and rather simple) algorithmic part of Lecture 2 - searching through a graph (DFS, BFS, etc...), is not primarily covered by the course books. Nevertheless, students should know this topic from undergraduate algorithms courses. We also refer to some great online resources below.

 

Remark
Some other literature and online resources use terms "path", "circuit", or "cycle" in a context where repetition of vertices (not edges, though) is allowed. This is WRONG, and we shall always use the correct terms "trail" or "closed tour" there - see also the course books.

Interactive tutorials

IS Questionnaires