Preparation
Lectures: Thursday, Friday, week 6.
Read: Book 10.1, 10.2, 10.4, 10.5. And 12.1, 12.7, 12.8 ("connected"), 12.9 ("trees"). Notes on graphs in general (pdf), Notes on topological sorting (pdf).
Basic Exercises
Chapter 10: Problem 10.7 (Euler tours for directed graphs).
Exercises
(1.) Take a look the following two directed graphs: Figure 10.3 (page 382), and the graph on page 417. Which of these has a topological ordering and which doesn't?
For the graph that has a topological ordering, construct one.
(2.) Given a directed ("riktad") graph G with n nodes and n+1 edges (arrows).
Check whether or not these statements are true or false, and give an argument why.
(a) G must have a cycle.
(b) G must have at least one node with indegree 2.
(3.) Take a look at the graph in the above figure. How many topological orderings are there for this graph?
(4.) Given a directed graph G.
Define the relation R(u,v) between nodes u and v of G as follows:
R(u,v) = "there is a directed path from u to v in G"
What properties does or doesn't R have: reflexivity, symmetry, transitivity?
(5.) Take a look at the following graphs: Figure 12.3 and 12.5 (page 466 in the book), and the graph on page 485. Which of these graphs have an Euler tour and which ones don't?
For the ones that have an Euler tour, construct the tour.
(6.) Take a look at the graph in the picture, taken from the game Dragon Age 3. Can you find an Euler walk in the graph? An Euler walk is a walk that uses every edge in the graph exactly once.
Hint: Is there an Euler tour? Why not? Can you add one more edge to the graph that would let you find an Euler tour? How does this help you find the Euler tour?
(7.) Given a connected ("sammanhängande") graph G.
(a.) Remove one edge from G. What are the possible different number of components the resulting graph can have? Can you give examples of each of the possibilities?
(b.) (Put back the edge you removed.) Remove one node from G, and also all edges involving that node. What are the possible different number of components the resulting graph can have? Can you give examples of each of the possibilities?
(8.) Given a simple graph G. Define the relation R(u,v) between nodes u and v of G as follows:
R(u,v) = "there is a path from u to v in G"
Show that R is an equivalence relation.
(9.) Prove: A tree with n nodes must have exactly n-1 edges.
Hint: Perform (strong) induction over the number of nodes n.
(10.) Given a simple graph G. Show that if there exists a walk ("väg") from u till v, there also exists a path ("enkel väg") from u till v.
(11.) Given a simple graph G. Show that if there exists two different paths ("enkla vägar") from u till v, there is a cycle in the graph.
Starred Exercises
These exercises are for students who are looking for a challenge.
(1*.) Prove: A simple connected graph with n nodes and n-1 edges must be a tree.
Hint: You can perform (simple) induction over the number of nodes n.
The following lemma may be helpful: A simple connected graph with n>=2 nodes and n-1 edges has a leaf. A leaf is a node v with deg(v)=1, so it has exactly one edge connected to it.
Follow-up question: Are all graphs with n nodes and n-1 edges connected?
(2*.) Given a simple graph G with 6 nodes.
Show that, regardless of which edges do or do not exist, at least one of the following must always be true:
- there exist 3 nodes in G without any edges between them, OR
- there exist 3 nodes in G with edges between each of them.
Start by drawing a few graphs with 6 nodes and check that the theorem is actually true.
Is the theorem true for graphs with 5 nodes?
Hint for the proof for 6 nodes: Pick any node, and look at whether or not there exist edges to the other 5 nodes.