Chapter 13: Problem 9
Prove that a tournament is strongly connected if and only if it has a directed Hamilton cycle.
Short Answer
Step by step solution
Key Concepts
These are the key concepts you need to understand to accurately answer the question.
/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none}
Learning Materials
Features
Discover
Chapter 13: Problem 9
Prove that a tournament is strongly connected if and only if it has a directed Hamilton cycle.
These are the key concepts you need to understand to accurately answer the question.
All the tools & learning materials you need for study success - in one app.
Get started for free
Prove the following generalization of Theorem 13.1.6: Let \(G\) be a connecterl graph. Then, after replacing each bridge \(\\{a, b\\}\) by the two arcs \((a, b)\) and \((b, a)\). one in each direction, it is possible to give the remaining edges of \(G\) an orientation so that the resulting digraph is strongly connected.
\(*\) Devise an algorithm for constructing a directed Hamilton cycle in a strongly connected tournament.
Prove that an orientation of \(K_{n}\) is a transitive tournament if and only if it does not have any directed cycles of length \(3 .\)
Consider the set \(A\) of the \(2^{n}\). binary sequences of length \(n\). This exercise concerns the existence of a circular arrangement \(\gamma_{n}\) of \(2^{n} 0\) s and \(1 s\), so that the \(2^{n}\) sequences of \(n\) consecutive bits of \(\gamma\) give all of \(A\); that is, are all distinct. Such a circular arrangement is called a de Bruijn cycle. For example, if \(n=2\), the circular arrangement \(0,0,1,1\). (regarding the first 0 as following the last 1 ) gives 0,\(0 ; 0,1 ; 1,1 ;\) and \(1,0 .\) For \(n=3,0,0,0,1,0,1,1,1\) (regarded cyclically) is a de Bruijn cycle. Define a digraph \(\Gamma_{n}\) whose vertices are the \(2^{n-1}\) binary sequences of length \(n-1\). Given two such binary sequences \(x\) and \(y\), we put an arc \(e\) from \(x\) to \(y\), provided that the last \(n-2\) bits of \(x\) agree with the first \(n-2\) bits of \(y_{1}\) and then we label the arc \(e\) with the first. bit of \(x\). (a) Prove that every vertex of \(\Gamma_{n}\) has indegree and outdegree equal to 2 . Thus, \(\Gamma_{n}\) has a total of \(2 \cdot 2^{n-1}=2^{n}\) arcs. (b) Prove that \(\Gamma_{n}\) is strongly connected, and hence \(\Gamma_{n}\) has a closed Eulerian directed trail (of length \(\left.2^{n}\right)\). (c) Let \(b_{1}, b_{2}, \ldots, b_{2^{n}}\) be the labels of the arcs (considered as a circular arrangement) as we traverse an Eulerian directed trail of \(\Gamma_{n}\). Prove that \(b_{1}, b_{2}, \ldots, b_{2^{n}}\) is a de Bruijn cycle. (d) Prove that, given any two vertices \(x\) and \(y\) of the digraph \(\Gamma_{n}\), there is a path from \(x\) to \(y\) of length at most \(n-1\).
Give an example of a digraph that does not have a closed Eulerian directed trail but whose underlying general graph has a closed Eulerian trail.
What do you think about this solution?
We value your feedback to improve our textbook solutions.