48  Homework III: Indirect Connections and Matrices

48.1 Undirected Paths

Consider the graph shown in Figure 51.1:

Figure 48.1: An undirected graph.

  1. Write down all the paths of length four (\(l = 4\)) connecting node B and node E:








  2. Write down all the paths of length two (\(l = 2\)) featuring node D as the inner node:








  3. Write down all the shortest paths connecting nodes A and D:








  4. Write down all the cycles of length three that start and end with node H:








48.2 Directed Paths

Consider the graph shown in Figure 51.2:

Figure 48.2: A directed graph.

  1. Write down all the directed path(s) of any length going from node F to node A:





  2. What is the length of the shortest directed path(s) going from node I to node H?


  3. If B wanted to send a message to C in the most efficient way, how many intermediaries would B have to use?


48.3 Matrices

  • In the matrix below, write down the cell entries geodesic distance matrix corresponding to the graph shown in Figure 51.1:
A B C D E F G H I J K L
A ----
B ----
C ----
D ----
E ----
F ----
G ----
H ----
I ----
J ----
K ----
L ----

  • What is the diameter of the graph shown in Figure 51.1?


  • What is the eccentricity of each node graph shown in Figure 51.1?

A B C D E F G H I J K L
  • In the matrix below, write down the cell entries for the reachability matrix corresponding to the graph shown in Figure 51.2:
A B C D E F G H I J
A ----
B ----
C ----
D ----
E ----
F ----
G ----
H ----
I ----
J ----