211L3Solutions

Exercises

1. Consider the graphs in Figure 3.

• (a) Write down their adjacency list and adjacency matrix representations.

(a)

1: 2
2: 3
3: 1, 5
4: 5, 6
5: 6
6:

0 1 0 0 0 0
0 0 1 0 0 0
1 0 0 0 1 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 0

(b)

a: b
b: a, c
c: d, e
d: e
e: f
f: d

0 1 0 0 0 0
1 0 1 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 1 0 0

(c)

1: 10
2: 9
3: 4, 6, 8
4: 3, 8
5: 6
6: 3, 5
7: 9
8: 3, 4
9: 2, 7
10: 1

0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 1 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0

• (b) Find all (strongly) connected components of each of these graphs.

(a)

• (1,2,3)

(b)

• (a,b)
• (d,e,f)

(c)

• (1,10)
• (2,9,7)
• (3,4,5,6,8)

2. Prove that the brute-force algorithm for solving the path problem is correct.

The brute-force algorithm works by iterating through every possible path and returning true if it finds a path from the source to the target. This is correct because all the paths could be thought of as a set P. If a path exists it will be in the set P. The algorithm goes through every path in P. If it does not return true, there can not be an existing path from the source to the target. It will return true if and only if a path is in P.

3. Consider the PathExistence(G, s, t) algorithm. Assume that determining if a vertex is marked takes a constant time unit. Call the max among the number of vertices and number of edges the size of the graph. If the size of graph G is n, then how much time in terms of time units is needed for Path(G, s, t) to determine if there is a path from s to t? Discuss efficiency of the algorithm.

In a worst case, it would take O(n^2) time to determine if there is a path from s to t. This can be where the height of the tree is one with many nodes off the root. This has the same worst case as the brute force algorithm, although for the general case it would increase performance over the brute force case. This algorithm is fairly efficient and, considering lack of useful heuristic information, should produce a reasonable runtime.

4. We say that a graph is k-regular, where k is a positive integer, if every vertex v in the graph has exactly k neighbors. For every positive even integer n > 2 construct a 3-regular graph with n vertices. (Hint: First construct 3-regular graphs with 4, 6, and 8 vertices, and then make a generalization).

• For every positive even integer greater than 2, a graph can be constructed to be 3-regular by connecting adjacent vertices and opposite verticies with each other i.e. G=(V,E) and n=2k. V={1,2...2n} E={{1,2},{2,3}..{2n+1},{1,k+1},{2,k+2}..,{k,2k}}.
• Graphs with an odd number of vertices's can not be 3-regular.

5. Prove Theorem 2.

• By definition, every vertex v in a graph is connected to itself.
• If a vertex v is connected to u, a path exists from v to u. As such it is possible to go u from v. By arriving at u from v, there must be a path connecting v to u.
• If v is connected to u, it is possible to follow a path from v to u. If it is then possible to travel to w from u, there must be a path from u to w. Arriving at w, and yet origonaly starting at v, there must be a path from v to w.

6. Let G be an undirected graph. The degree of a vertex v, denoted by deg(v), in graph G is the number of neighbors of v. Prove that the sum of the degrees of the vertices of G is always an even number. (Hint: Discuss the contribution of each edge to the sum).

In any graph, the sum for degree of all the verticies will always be an even number. This is because every edge has two ends, each end belonging to a different vertex. It is not possible to have half an edge. As such, any vertex with an odd number of neighbors will be balanced out with another vertex with an odd number of neighbors. This also shows that in any graph which contains verticies of odd degrees, will always have an even number of verticies with odd degrees.

7. Prove that the number of vertices of odd degree in any graph G is even.

In any graph, the sum for degree of all the verticies will always be an even number. This is because every edge has two ends, each end belonging to a different vertex. As such every vertex of an odd degree has to be balanced by another vertex of odd degree. Thus there is always an even number of odd degreed veritices to ensure a total overall even number of degrees.

8. Let G = (V,E) be a directed graph. For each v E V , we define the in-degree of v be the number of ingoing edges to v, and out-degree of v be the number of outgoing edges from v. Prove that the sum of all in-degrees equals to the sum of all out-degrees.

There is always a whole number of edges in a graph i.e. It is impossible to have half an edge. Each edge has a part which contributes to an in-degree of a vertex and an out-degree of another vertex. As such the amount on in-degree edges equals the number of out-degree. For every in-degree edge allocated to a vertex, there is a corresponding out-degree edge allocated to another vertex.

Programming Exercises

1. Write a program that, given an undirected graph as an input, outputs the sum of the degrees of all the vertices.

2. Implement the PathExistence(G, s, t) algorithm.

3. Consider the following problem. Given a graph G, vertices s and t, determine if there exists a path from s to t. If such a path exists then output one. Clearly this problem can be solved using the brute-force method. Find an algorithm that solves this problem without brute-force and then implement it.