Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.
1. Decide whether the following two graphs are isomorphic to each other.
If they are isomorphic give an explicit isomorphism.
|
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.
|
9. 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.
|
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. Let κ(G) denote the connectivity of G, and κ'(G) the edge-connectivity. Let G be 3-regular. Show that if κ(G) = 1, then κ'(G) = 1, and that if κ(G) = 2, then κ'(G) = 2. Conclude that κ(G) = κ'(G) when G is 3-regular.
|
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.) |
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.
This means that:
The end of the lists is marked with 0.
Graphs in this format can be very easily input with a pair of nested loops.
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.