CSCI 3104 Spring 2022
quiz代做 | assignment代写 | math代写 – 这个项目是quiz的sample
Xingran Tian
109308991
quiz 7 Safe and useless edges
1 Instructions 1
2 Standard 6- Safe and Useless Edges 2 2.1 Problem 1………………………………………….. 2
1 Instructions
- The solutions should be typed , using proper mathematical notation. We cannot accept hand-written solutions.Heres a short intro to LATEX.
- You should submit your work through the class Canvas page only. Please submit one PDF file, compiled using this LATEX template.
- You may not need a full page for your solutions; pagebreaks are there to help Gradescope automatically find where each problem is. Even if you do not attempt every problem, please submit this document with no fewer pages than the blank template (or Gradescope has issues with it).
- You may not collaborate with other students. Copying from any source is an Honor Code viola- tion. Furthermore, all submissions must be in your own words and reflect your understanding of the material. If there is any confusion about this policy, it is your responsibility to clarify before the due date.
- Posting to any service including, but not limited to Chegg, Discord, Reddit, StackExchange, etc., for help on an assignment is a violation of the Honor Code.
2 Standard 6- Safe and Useless Edges
2.1 Problem 1
Problem 1. Consider the following graphG(V,E,w). Suppose we have the intermediate spanning forestF (indicated using thick edges) consisting of the edges{A,B},{A,C}, and{D,E}. Clearly identify the safe, useless, and undecided edges. Justify your reasoning.
A
B
C
D
E
F
2
5
8
5
4
2
7
5
Answer. A safe edge is an edge that can be added to an intermediate spanning forest in such a way that we can still find a minimum-weight spanning tree of G. {C,E} and {E,F} are safe edges.Because after adding them we can still find a minimum-weight spanning tree of G. {B,C} is a useless edge because adding it will create a cycle. {B,D},{D,F} are undecided edges.