X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5..30a7ec2b1746fb3abfe8780a43625bb768842228:/generating.tex diff --git a/generating.tex b/generating.tex index 377c811..b4839db 100644 --- a/generating.tex +++ b/generating.tex @@ -21,7 +21,7 @@ $000,100,101,001,011,111,$ $110,010,000$ has been removed. \end{xpl} -We first have proven the following result, which +We have first proven the following result, which states that the ${\mathsf{N}}$-cube without one Hamiltonian cycle has the awaited property with regard to the connectivity. @@ -32,7 +32,7 @@ the ${\mathsf{N}}$-cube where an Hamiltonian cycle is removed, is strongly connected. \end{thrm} -Moreover, if all the transitions have the same probability ($\frac{1}{n}$), +Moreover, when all the transitions have the same probability ($\frac{1}{n}$), we have proven the following results: \begin{thrm} The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in @@ -43,11 +43,11 @@ cycle is removed, is doubly stochastic. Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian cycle is removed. Let $f$ be the corresponding function. -The question which remains to solve is: +The question which remains to be solved is: \emph{can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected?} -The answer is indeed positive. We furthermore have the following strongest -result. +The answer is indeed positive. Furthermore, we have the following results which are stronger +than previous ones. \begin{thrm} There exists $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete. \end{thrm} @@ -65,10 +65,10 @@ In such a context, the Hamiltonian cycle is equivalent to a Gray code. Many approaches have been proposed as a way to build such codes, for instance the Reflected Binary Code. In this one and for a $\mathsf{N}$-length cycle, one of the bits is exactly switched -$2^{\mathsf{N}-1}$ times whereas the others bits are modified at most +$2^{\mathsf{N}-1}$ times whereas the other bits are modified at most $\left\lfloor \dfrac{2^{\mathsf{N-1}}}{\mathsf{N}-1} \right\rfloor$ times. It is clear that the function that is built from such a code would -not provide an uniform output. +not provide a uniform output. The next section presents how to build balanced Hamiltonian cycles in the $\mathsf{N}$-cube with the objective to embed them into the