this is for holding javascript data
Jeremy Ting edited q2.tex
almost 10 years ago
Commit id: 95fa13667f69686be44503ee9a4f83192ad04273
deletions | additions
diff --git a/q2.tex b/q2.tex
index 51cd36a..eeea1f6 100644
--- a/q2.tex
+++ b/q2.tex
...
This will give us solution of Traveling Salesman Problem so you get the lowest cost tour of this graph. So all we have to do is delete the most expensive edge in the tour. That will give us the minimum spanning tree with degree 2.
Showing that it is NP-Complete:
If there are at most 2 connections for each node in a spanning tree in $G$ then $G$ must also have a Rudrata Path. The Rudrata path will be exactly the graph of $G$ because a spanning tree hits all the nodes so if we follow this path we find the Rudrata path.
If you can’t find a graph with at most 2 connections per node and is a spanning tree in $G$ then a Rudrata path does not exist in $G$. Assume that there is not a spanning tree in $G$ with at most 2 connections per node but there is a Rudrata path in $G$. A Rudrata Path visits all the nodes in $G$ and has no cycles. Thus the degree of each node in the Rudrata path is at most 2 which would also be a spanning tree with at most 2 connections per node which is a contradiction.