## CPSC 220 Graph Exercises

SHOW ALL WORK!!!

Consider the directed weighted graph G with vertex and edge sets below:

V = {A,B,C,D,E,F,G}

E = {(A,B,10),
(A,D,20),
(B,C,2),
(B,D,6),
(B,F,6),
(B,G,8),
(C,E,8),
(D,F,5),
(D,G,1)
(G,E,1)
(G,F,3)}

1. Suppose we are considering adding edges to or removing edges from G.
1. For the given size of V, what is the maximum possible size of E (assuming no self-loops)?
2. For the given size of V, what is the minimum possible size of E?

2. Assume that an integer takes one cell and a pointer takes two cells, and it is not necessary to store the actual label on each vertex,
1. How much space would it take to store G using
1. an adjacency list?
2. an adjacency matrix?
2. Develop a general formula in terms of |V| and |E| for the space required for each representation under these assumptions. Then evaluate the space tradeoffs when
1. |E| = |V|
2. |E| = |V|2

For questions 3-7, assume that "for each adjacent vertex" in any relevant algorithm takes the vertices in alphabetical order.

3. Show the order in which the vertices will be visited in a breadth-first search from A.

4. Show the order in which the vertices will be visited in a depth-first search from A.

5. Find a topological sort of the vertices using
1. a post-visit depth-first search.
2. the queue-based method.

6. Viewing this as an undirected graph, find a minimum spanning tree using
1. Prim's algorithm
2. Kruskal's algorithm

7. Use Dijkstra's algorithm to find the shortest route and distance from A to every other vertex.
The text passage contains a series of graph theory exercises with multiple questions, some of which involve mathematical calculations and problem-solving.
multiple_questions
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
## CPSC 220 Graph Exercises

SHOW ALL WORK!!!

Consider the directed weighted graph G with vertex and edge sets below:

V = {A,B,C,D,E,F,G}

E = {(A,B,10),
(A,D,20),
(B,C,2),
(B,D,6),
(B,F,6),
(B,G,8),
(C,E,8),
(D,F,5),
(D,G,1)
(G,E,1)
(G,F,3)}

1. Suppose we are considering adding edges to or removing edges from G.
1. For the given size of V, what is the maximum possible size of E (assuming no self-loops)?
2. For the given size of V, what is the minimum possible size of E?

2. Assume that an integer takes one cell and a pointer takes two cells, and it is not necessary to store the actual label on each vertex,
1. How much space would it take to store G using
1. an adjacency list?
2. an adjacency matrix?
2. Develop a general formula in terms of |V| and |E| for the space required for each representation under these assumptions. Then evaluate the space tradeoffs when
1. |E| = |V|
2. |E| = |V|2

For questions 3-7, assume that "for each adjacent vertex" in any relevant algorithm takes the vertices in alphabetical order.

3. Show the order in which the vertices will be visited in a breadth-first search from A.

4. Show the order in which the vertices will be visited in a depth-first search from A.

5. Find a topological sort of the vertices using
1. a post-visit depth-first search.
2. the queue-based method.

6. Viewing this as an undirected graph, find a minimum spanning tree using
1. Prim's algorithm
2. Kruskal's algorithm

7. Use Dijkstra's algorithm to find the shortest route and distance from A to every other vertex.
user
The text passage contains a series of graph theory exercises with multiple questions, some of which involve mathematical calculations and problem-solving.

TYPE: MULTIPLE_QUESTIONS