Clicker Questions - 14-Graph-Basic
An undirected graph is defined as follows:
$V = \{ \; i \; \vert \; 0 \leq i < 10 \}$
$E = \{ (0,1), \; (0,3), \; (1,9), \; (3,5), \; (3,7), \; (4,6), \; (5,9), \; (6,8) \}$
Question 1: How many connected components are in the graph?
Answer
The easiest way to answer this is to draw the graph:0 ------- 1 ---------9 | | | | 3 ------------------ 5 | | 2 | 7 4---6---8The answer is three.
Question 2: Which nodes are in the one cycle in this graph (just list the node numbers with spaces between them).
Answer
Look at the graph above: 0, 1, 3, 5, 9 (not in that order)Question 3: Is this graph bipartite?
Answer
No -- it has an odd cycle, and if you think about it, an odd cycle cannot be in a bitpartite graph.Question 4: Which of the following is an adjacency matrix for the graph?
|
A
| 0 1 2 3 4 5 6 7 8 9 - - - - - - - - - - - 0 | 0 1 0 1 0 0 0 0 0 0 1 | 0 0 0 0 0 0 0 0 0 1 2 | 0 0 0 0 0 0 0 0 0 0 3 | 0 0 0 0 0 1 0 1 0 0 4 | 0 0 0 0 0 0 1 0 0 0 5 | 0 0 0 0 0 0 0 0 0 1 6 | 0 0 0 0 0 0 0 0 1 0 7 | 0 0 0 0 0 0 0 0 0 0 8 | 0 0 0 0 0 0 0 0 0 0 9 | 0 0 0 0 0 0 0 0 0 0 |
B
| 0 1 2 3 4 5 6 7 8 9 - - - - - - - - - - - 0 | 1 1 0 1 0 0 0 0 0 0 1 | 1 1 0 0 0 0 0 0 0 1 2 | 0 0 1 0 0 0 0 0 0 0 3 | 1 0 0 1 0 1 0 1 0 0 4 | 0 0 0 0 1 0 1 0 0 0 5 | 0 0 0 1 0 1 0 0 0 1 6 | 0 0 0 0 1 0 1 0 1 0 7 | 0 0 0 1 0 0 0 1 0 0 8 | 0 0 0 0 0 0 1 0 1 0 9 | 0 0 0 0 0 1 0 0 0 1 |
C
| 0 1 2 3 4 5 6 7 8 9 - - - - - - - - - - - 0 | 0 1 0 1 0 0 0 0 0 0 1 | 1 0 0 0 0 0 0 0 0 1 2 | 0 0 0 0 0 0 0 0 0 0 3 | 1 0 0 0 0 1 0 1 0 0 4 | 0 0 0 0 0 0 1 0 0 0 5 | 0 0 0 1 0 0 0 0 0 1 6 | 0 0 0 0 1 0 0 0 1 0 7 | 0 0 0 1 0 0 0 0 0 0 8 | 0 0 0 0 0 0 1 0 0 0 9 | 0 1 0 0 0 1 0 0 0 0 |
Answer
You can use process of elimination - Matrix A doesn't have $(1,0), (3,0), \text{etc}$. Since the graph is undirected, you need to have entries $(i,j)$ and $(j,i)$. That rules out matrix A.Matrix B has self-edges: $(0,0), (1,1), \text{etc}$, which the given graph doesn't have.
Matrix C is good.