Sbírka matematických úloh

Grafy řetězců

Úloha číslo: 4427

• Varianta

  \(p=1\) (řetězce se liší v právě jednom znaku)

• Řešení

  • Graf má \(z^n\) vrcholů.
  • Hrany z jednoho vrcholu odpovídají tomu, že si zvolíme jednu z \(n\) pozic a znak na ní změníme na jeden ze \(z-1\) odlišných. Stupeň každého vrcholu tedy je \(n\cdot (z-1)\).
  • Počet hran získáme jako součet stupňů dělený dvěma.
  • Graf je souvislý, jelikož pro každé dva vrcholy můžeme zkonstruovat cestu tak, že znaky jednoho řetězce postupně přepisujeme na znaky druhého řetězce.
  • Aby byl graf eulerovský, musí kromě souvislosti mít sudé stupně. To nastane, pokud je \(n\) sudé nebo \(z\) liché.

• Varianta

  \(z=2\), \(p=2\) (binární abeceda, rozdíl ve dvou znacích)

• Řešení

  • Graf má \(2^n\) vrcholů.
  • Z každého vrcholu vede \(n\choose 2\) hran (vybíráme 2 pozice, na kterých změníme bit na opačný).
  • Počet hran (polovina součtu stupňů) je tedy \({n\choose 2}\cdot 2^{n-1}\).
  • Graf není souvislý, protože znegování dvou bitů zachová paritu počtu jedniček. Tím pádem mezi vrcholem se sudým počtem 1 a vrcholem s lichým počtem 1 nemůže vést cesta. (Podrobnější rozbor odhalí, že graf má právě dvě komponenty.)
  • Nesouvislý graf nemůže být eulerovský.

• Varianta

  \(z=3\) a \(p=2\) (trojková abeceda, rozdíl ve dvou znacích)

• Řešení

  • Pro \(n=1\) graf obsahuje 3 izolované vrcholy. Dále budeme předpokládat \(n>1\).
  • Vrcholů je \(3^n\).
  • Hrany z vrcholu odpovídají tomu, že vybereme 2 z \(n\) pozic, které budeme měnit, a na každé z nich vybereme jeden ze 2 znaků odlišných od aktuálního. Stupeň vrcholů tedy je \({n\choose 2}\cdot 2{\cdot} 2=2n(n-1)\).
  • Počet hran získáme jako součet stupňů dělený dvěma.
  • Graf je souvislý. Pro libovolné dva vrcholy \(u\) a \(v\) sestrojíme cestu následovně: Dokud je vzdálenost \(u\) od \(v\) aspoň 2, změníme dva znaky z \(u\) na odpovídající znaky z \(v\). Tím jsme prošli po jedné hraně a snížili vzdálenost o 2. Pokud je vzdálenost rovna 1, existují pozice \(i\) a \(j\) takové, že \(u_i\ne v_i\) a \(u_j=v_j\). Použijeme dvě hrany: první hranou změníme \(u_i\) na (jednoznačně určený) znak různý od \(u_i\) i \(v_i\) a \(u_j\) na libovolný jiný znak. Druhou hranou už můžeme změnit \(u_i\) na \(v_i\) a na pozici \(j\) dostat zpět \(u_j=v_j\).
  • Graf je souvislý a má všechny stupně sudé, takže je eulerovský.