Homework 6: Graphs

1. (2 points) A simple graph may...

a. contain loops

b. have multiple edges between nodes

*c. have at most a single edge between nodes

d. all of the above

2. (2 points) A complete graph with 6 vertices will have ___ edges?

*a. 15

b. 5

c. 12

d. 36

3. (2 points) The neighborhood of a vertex is?

a. All of the edges connected to it.

b. All of the vertices reachable from it by an Eulerian walk.

c. Any node reachable in fewer than four or five edges.

*d. All of the vertices joined to it by a single edge.

4. (2 points) For one of the Cycle graphs to be bipartite, its number of sides must be?

a. less than ten

b. odd and greater than three

*c. even and greater than two

d. greater than seven

5. (2 points) If my code represents a graph by {a: (b, c, d), b: (a), c: (a, d), d: (a, c)} then I am using a ______ to represent it?

*a. adjacency list

b. adjacency matrix

c. incidence matrix

d. adjacency incident

6. (2 points) Is K4 a bipartite graph? [DOUBLE CHECK ANSWER]

a. Yes

*b. No

c. It depends on how it is drawn.

d. Indeterminate

7. (2 points) Consider the following adjacency matrix:

    a   b   c   d   e   f   g

a  0   0   1   0   1   0   1

b  0   1   0   0   0   1   0

c  1   0   0   0   0   1   1

d  0   0   0   0   1   0   0

e  1   0   0   1   0   0   0

f   0   1   1   0   0   0   1

g  1   0   1   0   0   1   0

In the graph so described, there is a loop at vertex ___?

a. a

*b. b

c. d

d. f

8. (2 points) In the above adjacency matrix, there is an edge from?

a. a to b

b. a to d

c. d to g

*d. f to g

9. (2 points) For an Eulerian path through a graph to exist, there must be _____.

a. an even number of nodes of odd degree

b. 0 or 2 nodes of even degree

*c. 0 or 2 nodes of odd degree

d. an odd number of nodes of even degree

10. (2 points) The difference between a path and a circuit is that ____.

*a. a circuit starts and ends at the same vertex, while a path need not

b. a circuit contains more nodes than a path

c. a path moves along edges, while a circuit jumps from node to node

d. a circuit applies to electronics, while paths are used for geographical graphs

11. (2 points) Consider the following incidence matrix:

      e1 e2 e3 e4 e5 e6

v1  0   0   1   0   1   0

v2  0   1   0   0   0   1

v3  1   0   0   0   0   0

v4  0   0   0   1   1   0

v5  1   0   0   1   0   0

v6  0   1   1   0   0   1

Is this a simple graph?

a. Yes

*b. No

12. (2 points) In the above incidence matrix, the degree of v6 is?

*a. 3

b. 6

c. 1

d. 2

13. (2 points) Consider the graph with following adjacency matrix:

    a   b   c   d  

a  0   1   1   0  

b  1   0   0   1  

c  1   0   0   1  

d  0   1   1   0  

Which of the following is an Eulerian circuit through that graph?

a. a-c, c-b, b-d, d-a

b. a-d, d-b, b-c, c-a

*c. a-b, b-d, d-c, c-a

d. a-b, b-c, c-d, d-a

14. (2 points) Consider the graph described by the adjacency list {a: (b, c), b: (a, e), c: (b), d: (f, g) f: (d), g: (d)}. What are the connected components of that graph?

a. a-b-c-d and e-f-g

*b. a-b-c-e and d-f-g

c. a-b-c-g and d-f-g

d. the whole graph is connected

15. (2 points) Consider the graph described by the adjacency list {a: (b, c, d), b: (a, c), c: (a, b, d), d: (a, c)}. Does it contain an Eulerian path?

*a. Yes

b. No

c. Not enough information

16. (2 points) Consider the graph from Q-15. Does it contain an Eulerian circuit?

a. Yes

*b. No

c. Not enough information

d. All of the above

17. (2 points) Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are _____ .

a. Break vertices

b. Disconnecting vertices

c. Full vertices

*d. Cut vertices

18. (2 points) An graph is called a ________ if there is not a path between every pair of distinct vertices in the graph.

*a. Disconnected graph

b. Connected graph

c. Distinct graph

d. Cut graph