CS453 Assignment 4 Solved

 

Questions with a (⋆) are each worth 1 bonus point for 453 students.

1. Recall that the adjacency matrix of a simple graph 𝐺 with vertex set {𝑣1, 𝑣2, … , 𝑣𝑛} is the 𝑛 × 𝑛 matrix 𝐴 with entries

𝐴𝑖,𝑗 = { 0

1

𝑣 𝑖

is adjacent to 𝑣 𝑗

otherwise

A. Let 𝐾 be the complete bipartite graph with vertices 3,4

{𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 } and where vertices 𝑣 and 𝑣 are adjacent if and 1234567 𝑖 𝑗

only if 𝑖 and 𝑗 have different parity (one of 𝑖 or 𝑗 is odd and the other is

even.) What does the adjacency matrix 𝐴 look like in this case? B. Let 𝐾 be the complete bipartite graph with vertices

{𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 ,𝑣 } and where vertices 𝑣 and 𝑣 are adjacent if and 1234567 𝑖 𝑗

only if (𝑖 ≤ 3 and 𝑗 ≥ 4) or (𝑖 ≥ 4 and 𝑗 ≤ 3). What does the adjacency matrix 𝐴 look like in this case?

3,4

2. We let 𝐺 be a connected graph. For any vertex 𝑣 ∈ 𝑉, define its eccentricity by the formula

ecc(𝑣) = max{𝐷(𝑢, 𝑣): 𝑢 ∈ 𝑉}.
This is the length of “longest among all shortest paths with 𝑣 as an

endpoint.”
a. Let 𝐺 be the graph drawn below. Label each vertex with its

eccentricity.

2. The diameter of a graph is the maximum among the eccentricities of its vertices and the radius of a graph is the minimum among the eccentricities of its vertices. For the graph 𝐺 drawn in part a, what is its diameter and radius?
3. A central vertex is a vertex 𝑣 such that ecc(𝑣) = radius(𝐺). Which of the vertices in the graph 𝐺 are central vertices?
4. A peripheral vertex is a vertex 𝑣 such that ecc(𝑣) = diameter(𝐺). Which of the vertices in graph 𝐺 are peripheral vertices?
5. Explain why it is important for these definitions that 𝐺 be a connected graph.
6. Show that for any connected graph 𝐻,
   radius(𝐻) ≤ diameter(𝐻) ≤ 2 radius(𝐻).

   One inequality is quite easy and the second can be handled using a central vertex and the triangle inequality.

3. Recall that a bridge is an edge whose deletion increases the number of components of a graph. Also, a link is another term for “non-bridge.”

a. In the graph 𝐺 (same as in problem 2a) below, which edges are bridges and which edges are links?

b. If you delete all of the bridges, how many components remain? c. Suppose, instead, you deleted links one at a time until the

remaining graph had no links. How many links could you delete in this process?

4. Let 𝐺 be a graph and 𝑥 be a vertex of 𝐺. We say that 𝑢~𝑤 if
𝐷(𝑢, 𝑥) = 𝐷(𝑤, 𝑥). When we discuss trees, the equivalence classes will be the levels of a tree.

1. Show that this relation is reflexive.
2. Show that this relation is symmetric.
3. Show that this relation is transitive.
4. Suppose 𝑥 has no loops and suppose 𝑢𝑥 is an edge. Briefly

   describe the equivalence class [𝑢].