# CPTS553 Assignment 4 Solved

30.00 \$ 15.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

Rate this product

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

𝐴𝑖,𝑗 = {1      𝑣𝑖 is adjacent to 𝑣𝑗

0             otherwise

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

{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5,𝑣6, 𝑣7} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and 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?

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

{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5,𝑣6, 𝑣7} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and only if (𝑖 ≤ 3 and 𝑗 ≥ 4) or  (𝑖 ≥ 4 and 𝑗 ≤ 3).  What does the adjacency matrix 𝐴 look like in this case?

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

This is the length of “longest among all shortest paths with 𝑣 as an endpoint.”

1. Let 𝐺 be the graph drawn below. Label each vertex with its eccentricity.

1. 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?
2. A central vertex is a vertex 𝑣 such that ecc(𝑣) = radius(𝐺). Which of the vertices in the graph 𝐺 are central vertices?
3. A peripheral vertex is a vertex 𝑣 such that ecc(𝑣) = diameter(𝐺). Which of the vertices in graph 𝐺 are peripheral vertices?
4. Explain why it is important for these definitions that 𝐺 be a connected graph.

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

1. 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.”

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

1. If you delete all of the bridges, how many components remain?