Przyjmujemy, że wierzchołkami grafu są permutacje zbioru n-elementowego, a dwie permutacje uznajemy za sąsiednie, gdy jedna z nich może być otrzymana przez pojedyńczą transpozycję z drugiej.
Czy graf jest eulerowski/hamiltonowski?
Czy graf jest eulerowski/hamiltonowski
-
erina
- Użytkownik
- Posty: 230
- Rejestracja: 29 mar 2010, o 20:14
- Płeć: Kobieta
- Lokalizacja: Pruszków
- Pomógł: 38 razy
Czy graf jest eulerowski/hamiltonowski
Każdy wierzchołek ma \(\displaystyle{ \left (^n_2\right )}\) sąsiadów. Czyli eulerowski jest dla \(\displaystyle{ n\equiv 0, 1 (mod \ 4)}\) (bo wtedy \(\displaystyle{ \left (^n_2\right )}\) jest parzyste).
Na hamiltonowskie niestety nie ma prostego kryterium. Przypuszczam, że jest hamiltonowski, ale za mało pamiętam z własności permutacji.
Na hamiltonowskie niestety nie ma prostego kryterium. Przypuszczam, że jest hamiltonowski, ale za mało pamiętam z własności permutacji.