47  Homework II: Directed Graphs

Figure 47.1: A directed graph.

Consider the graph shown in Figure 47.1:

  1. Write down the edge set of the graph:




47.1 Directed Graph Neighborhoods

  1. Who are the out-neighbors of node A?


  2. Who are the in-neighbors of node E?


  3. What is the intersection of the out-neighborhoods of nodes A and I?


  4. What is the intersection of the in-neighborhoods of nodes H and E?


  5. What is the union of the out-neighborhoods of nodes G and K?


  6. What is the union of the in-neighborhoods of nodes B and I?


47.2 Directed Graph Degrees

  1. What is the out-degree of node H?


  2. What is the in-degree of node E?


  3. What is(are) the node(s) with the largest out-degree?


  4. What is(are) the node(s) with the largest in-degree?


  5. What is(are) the node(s) with the smallest out-degree?


  6. What is(are) the node(s) with the smallest in-degree?


47.3 Directed Graph Node Types

  1. Which is(are) the receiver node(s) in the graph?


  2. Which is(are) the transmitter node(s) in the graph?


47.4 Directed Graph Metrics

  1. What is the graph’s in-degree sequence?


  2. What is the graph’s out-degree range?


  3. What is the graph’s in-degree range?

    c

  4. What is the graph’s sum of degrees?


  5. What is the size of the graph?


  6. What is the graph’s maximum size?


  7. Compute the density of the graph:







47.5 From Graph to Matrix

  • In the matrix below, write down the cell entries for the adjacency matrix corresponding to the graph shown in Figure 47.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 ----