Homework III: Indirect Connections and Matrices

Undirected Paths

Consider the graph shown in Figure 1:

Figure 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:








Directed Paths

Consider the graph shown in Figure 2:

Figure 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?


Matrices

  • In the matrix below, write down the cell entries geodesic distance matrix corresponding to the graph shown in Figure 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 1?


  • What is the eccentricity of each node graph shown in Figure 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 2:
A B C D E F G H I J
A ----
B ----
C ----
D ----
E ----
F ----
G ----
H ----
I ----
J ----
  • What flavor of connectivity is the graph in Figure 2?