6. Step 1: For each of the diagrams below, choose whether the wiggly edges are o
ID: 3120103 • Letter: 6
Question
6.Step 1:
For each of the diagrams below, choose whether the wiggly edges are or are not a spanning tree.
1. The edges create a spanning tree. 2. The edges do not create a spanning tree. Enter the number of the term that corresponds to each choice:
1.
2
3
4.
Step 2:
For each of the diagrams below, choose whether the wiggly edges are or are not a Hamiltonian circuit. 1. The edges create a Hamiltonian circuit. 2. The diagram do not create a Hamiltonian circuit. Enter the number of the term that corresponds to each choice:
1.
2.
3.
4.
Equation Editor eBookExplanation / Answer
Solution: - A spanning tree is a sub graph of a connected graph. The spanning trees have the maximum number of edges among all tree in G. Hence it is also known as maximal tree.
Graph 1: - The edges do not create a spanning tree because all vertices are not connected by the wiggly edges.
Graph 2: - The edges do not create a spanning tree because all vertices are not connected by the wiggly edges.
Graph 3: - The edges create a spanning tree because all vertices are connected by the wiggly edges.
Graph 4: - The edges do not create a spanning tree because all vertices are not connected by the wiggly edges.
Part B: - Hamiltonian circuit is defined to be a closed walk which traverses every vertex of G exactly once except the starting vertex
Graph 1: - The edges do not create a Hamiltonian circuit because all vertices are not traverses by the wiggly edges.
Graph 2: - The edges do not create a Hamiltonian circuit because all vertices are not traverses by the wiggly edges.
Graph 3: - The edges do not create a Hamiltonian circuit because all vertices are traversed by the wiggly edges but it is not connected at the ends.
Graph 4: - The edges do not create a Hamiltonian circuit because all vertices are not traverses by the wiggly edges.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.