Difference between revisions of "TADM2E 5.27"
GreatSalmon (talk | contribs) (Created page with "Proof by induction. A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa Suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now...") |
GreatSalmon (talk | contribs) |
||
| Line 1: | Line 1: | ||
Proof by induction. | Proof by induction. | ||
| + | |||
A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa | A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa | ||
| − | + | Now suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now add a vertex (n+1) that is connected to every other node. 3 cases may occur: | |
case1) If the first node of the n Hamiltonian path can be reached by vertex (n+1), add (n+1) to the beginning of the path. New Hamiltonian path: n+1,1,...,n | case1) If the first node of the n Hamiltonian path can be reached by vertex (n+1), add (n+1) to the beginning of the path. New Hamiltonian path: n+1,1,...,n | ||
case2) If the last node of the n Hamiltonian path can reach the vertex (n+1), add (n+1) to the end of the path. New Hamiltonian path: 1,...,n,n+1 | case2) If the last node of the n Hamiltonian path can reach the vertex (n+1), add (n+1) to the end of the path. New Hamiltonian path: 1,...,n,n+1 | ||
case3) Take the first node of the n Hamiltonian path that can be reached by (n+1). This must exist, because we are not in case 2. Call this node k. By definition of this node, (k-1) can reach (n+1). Form the new Hamiltonian path as: 1,...,k-1,n+1,k,...,n. | case3) Take the first node of the n Hamiltonian path that can be reached by (n+1). This must exist, because we are not in case 2. Call this node k. By definition of this node, (k-1) can reach (n+1). Form the new Hamiltonian path as: 1,...,k-1,n+1,k,...,n. | ||
Revision as of 15:13, 29 March 2016
Proof by induction.
A tournament with 2 vertices (1,2) has a Hamiltonian path. 1 -> 2 or vice versa
Now suppose our tournament with n vertices has a Hamiltonian path 1,..,n. Now add a vertex (n+1) that is connected to every other node. 3 cases may occur:
case1) If the first node of the n Hamiltonian path can be reached by vertex (n+1), add (n+1) to the beginning of the path. New Hamiltonian path: n+1,1,...,n case2) If the last node of the n Hamiltonian path can reach the vertex (n+1), add (n+1) to the end of the path. New Hamiltonian path: 1,...,n,n+1 case3) Take the first node of the n Hamiltonian path that can be reached by (n+1). This must exist, because we are not in case 2. Call this node k. By definition of this node, (k-1) can reach (n+1). Form the new Hamiltonian path as: 1,...,k-1,n+1,k,...,n.
