Graph Questions

Question 1

[EX 15.1 mod] Draw the undirected graph that is represented as follows:

Vertices: 1, 2, 3, 4, 5, 6, 7
Edges: (5, 6), (4, 6), (3, 7), (6, 7), (5, 7), (1, 4), (2, 4), (2, 3), (4, 7)

Question 2

[EX 15.2 mod] Is the graph from Exercise 15.1 connected? Is it complete? If it isn't, give a counter example to explain.

Question 3

[EX 15.5 mod] Using the data in Exercise 15.1, draw the resulting directed graph.

Question 4

[EX 15.6 mod] Is the directed graph of Exercise 15.5 connected? Is it complete? If it isn't, give a counter example to explain.

Question 5

If you were to follow the connections indicated by which vertices were explored to find new vertices, and add them to the queue, what are the vertices on the path from vertex 1 to vertex 2?

Question 6

Is the path you gave in the previous question a shortest path (in terms of edges) between 1 and 2? Explain in terms of the algorithm, not in terms of the specific example.

Question 7

Trace the BFS algorithm on this undirected graph to traverse it starting from vertex 1, and figure out which vertices lead to which other vertices. For reference, the BFS algorithm is shown. Use the adjacency list above for the order of the nodes explored and follow the trace format started below. see image.

0 [1, 2, 3]
1 [0, 4, 5]
2 [0, 3]
3 [0, 2, 4]
4 [1, 3, 5, 6]
5 [1, 4, 6, 7]
6 [4, 5]

Algorithm

"Breadth-first traversal algorithm overview

• enqueue the starting vertex, and mark it as visited
• loop until queue is empty
  • dequeue first vertex and add it to iterator
  • enqueue each unmarked vertex adjacent to the dequeued vertex
  • mark each vertex enqueued as visited" (Lewis and Chase)

Trace

Initially:
queue = [1]
visited_vertices = [1]
node_container = []

After loop 1:
queue = [0, 4, 5] //front is on left
visited_vertices = {0, 1, 4, 5} //will be kept sorted for convenience.
node_container = [1] //iterable object to record nodes traversed, first item is on left.

Complete the remaining loop iterations.