Recitation 8 3 Rules: Teams take questions in cyclic order. Each team has 15 seconds to answer. A correct answer is worth 1 point. If a team can not answer a question correctly, the question goes to the next team. If no team can answer, the ta gets a point and provides the answer This test is open book. Between problems, the game may stop for questions. The TA can change the rules in any way he or she sees fit at any time Here is a picture of a graph G=(V,E) E (The edge E-D is absent initially, but will be added later. 1. What are the elements of v called? vertices 2. What are the elements of E called? Edges 3. What are the elements of V in this case? A, B, C, D, E, Fl 4. What are the elements of E in this case?(A-B, A-C, B-C, B-D,C-D,E-FI 5. Is this graph connected? No 6. What is the definition of connected, anyway? a graph is connected if there is a path between every pair of vertices 7. What is a connected component of a graph? A maximal, connected subgraph. Here, maximal means that including any more vertices would yield a disconnected sub- graph 8. What are the connected components of this graph? The subgraph consisting of vertices E and F and the edge between them The subgraph consisting of vertices A, B, C, and D and the edges between them 9. Now suppose we add the edge E-D Is the graph connected now? Yes 10. What is the distance between a and D? 2Recitation 8 3 Rules: Teams take questions in cyclic order. Each team has 15 seconds to answer. A correct answer is worth 1 point. If a team can not answer a question correctly, the question goes to the next team. If no team can answer, the TA gets a point and provides the answer. This test is open book. Between problems, the game may stop for questions. The TA can change the rules in any way he or she sees fit at any time. Here is a picture of a graph G = (V,E). A B C D E F (The edge E—D is absent initially, but will be added later.) 1. What are the elements of V called? Vertices. 2. What are the elements of E called? Edges. 3. What are the elements of V in this case? {A, B, C, D, E, F} 4. What are the elements of E in this case? {A—B,A—C, B—C, B—D, C—D, E—F} 5. Is this graph connected? No. 6. What is the definition of connected, anyway? A graph is connected if there is a path between every pair of vertices. 7. What is a connected component of a graph? A maximal, connected subgraph. Here, maximal means that including any more vertices would yield a disconnected sub￾graph. 8. What are the connected components of this graph? • The subgraph consisting of vertices E and F and the edge between them. • The subgraph consisting of vertices A, B, C, and D and the edges between them. 9. Now suppose we add the edge E—D. Is the graph connected now? Yes. 10. What is the distance between A and D?2