Comp 7750/4060 Graph Algorithms

Assignment 1

Jan - Apr 2018 
assigned 31 Jan, 2018
due 14 Feb, 2018

Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.


Written Answers (90 points or 120 points)

1. Decide whether the following two graphs are isomorphic to each other. If they are isomorphic give an explicit isomorphism.

   P1   P2

2. A planar graph is self-dual if it is isomorphic to its dual.
(a) Show that if a planar graph G on n vertices and e edges is self-dual, then e = 2n-2.
(Hint: use Euler's formula, n + f - e = 2.)
(b) For each n ≥ 4, find a self-dual planar graph.
3. Show that if G is 2-connected, then for every three vertices a, b, and x, there is a path from a to b containing x. (Hint: add a new vertex y, joined to a and b.)
4. Let G have n vertices. Show that it is impossible for G to have n distinct degrees. Find all graphs with exactly n-1 distinct degrees. (No loops or multiple edges.)
5. Let G have degree sequence D = (d1, d2, ..., dn), where d1 ≥ d2 ≥ ... ≥ dn. Show that if dn ≥ (n-1)/2, then G is connected. Is this also true if dn ≥ (n-2)/2? Explain.
6. Let G be a bipartite simple graph on n vertices with bipartition (X,Y). Let dx be the minimum degree among the vertices of X, and dy be the minimum degree among the vertices of Y. Show that if dx + dy > n/2, then G is connected, where dx, dy > 0. If dx + dy = n/2, is the conclusion still true? Explain.
7. Find a TK3,3 and a TK5 in the graph shown.

8. Find a maximum flow by hand in the network shown. Prove your flow is maximum by illustrating a minimum edge-cut K such that the value of f = capacity of K.

    network1

9. A Hamilton cycle in G is a cycle that contains every vertex. A Hamilton path in G is a path that contains every vertex. We are given that HamCycle is NP-complete. Show that HamPath is also NP-complete.
(Hint: Given a graph G in which we want to find a Ham cycle. Show how to transform G into a graph H, such that a Ham path in H will give a Ham cycle in G.)

Questions 10, 11, 12 are for students in 7750 only

10. Let G be a graph with minimum degree at least 3, with a separating set {u,v}. Let H1, H2, ..., Hk be the connected components of G-{u,v}. Let Ki be the graph induced by V(Hi) U {u,v}. Show that G is planar iff each Ki is planar.
11. Consider the following network N with flow f indicated in square brackets. Edges with no flow indicated have zero flow. A breadth-first search of N will construct the sub-network of all shortest, unsaturated paths in N, if it is allowed to continue searching after t is first encountered. This sub-network is called the auxiliary network, Aux(N,f). A forward edge uv of N with positive residual capacity is replaced by a forward edge uv with capacity cap(uv)-f(uv) in the auxiliary network. A backward edge uv of N with positive flow is replaced by a forward edge uv with capacity f(uv) in Aux(N,f). Construct the auxiliary network for the graph shown. Find a max flow in Aux(N,f), and modify f in N accordingly. Finally, construct a new auxiliary network for N, based on the new flow.

    network3

12. Show that if G is connected on n vertices, and n>2δ, where δ is the minimum degree of G, then G contains a path of length at least 2δ.
(Hint: consider the endpoints of a longest path.)


Part II -- Programming (100 points)

1. Program the Hopcroft-Tarjan algorithm to find the blocks and cut-vertices of a graph. Print out a list
of cut-vertices, and for each block, print out the edges in the block. Be sure to start the DF-Search
sometimes from a cut-vertex, and sometimes not from a cut-vertex.

Text files containing the adjacency lists of the input graphs are available here: graph 1, graph 2 and graph 3.

    Cutpt1       Cutpt2


Input format

When inputting a graph in text format, with vertices 1..n, use the following format.

Graph1
16
-1 2 3 6
-2 4 7
...
0

This means that:

the name of the graph is "Graph1" (every graph has a name)
there are 16 vertices
1 is adjacent to:
2
3
6
2 is adjacent to:
4
7
etc.

The end of the lists is marked with 0.

Graphs in this format can be very easily input with a pair of nested loops.

read(n)
read(u)
while (u < 0) {
   u = -u
   read(v)
   while (v > 0) {
      create edge (u,v)
      read(v)
   }
   u = v
}

Notice that an edge uv occurs only once in the input file, either with u or v, but not with both.
However, the adjacency lists must be constructed so that uv appears twice, once for each endpoint.