text: ## 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.
explanation: The document is a set of exercises for a course in computer science, specifically focusing on graph theory. It contains multiple questions related to a directed weighted graph, including questions about the maximum and minimum possible sizes of the edge set, space requirements for different graph representations, and various graph traversal and optimization algorithms. There are no provided answers to these questions.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: ## 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.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a set of exercises for a course in computer science, specifically focusing on graph theory. It contains multiple questions related to a directed weighted graph, including questions about the maximum and minimum possible sizes of the edge set, space requirements for different graph representations, and various graph traversal and optimization algorithms. There are no provided answers to these questions.
  
  Label: multiple-question