Witam
Mam problem z nastepujacym zadaniem.
Ile jest tras o długości 2 z wierzchołka \(\displaystyle{ (1101)}\) w \(\displaystyle{ Q_{4}}\)
Graf Q4
-
Rycerz_Milosci
- Użytkownik
- Posty: 1
- Rejestracja: 28 wrz 2009, o 20:08
- Płeć: Mężczyzna
- Lokalizacja: olsztyn
-
mostostalek
- Użytkownik
- Posty: 1384
- Rejestracja: 26 lis 2006, o 21:34
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 33 razy
- Pomógł: 268 razy
Graf Q4
hmmm nie znam zbytnio definicji trasy szczerze mówiąc.. ale to wygląda tak:
zgodnie z definicją k-kostki wierzchołek jest połączony krawędzią z innym wierzchołkiem gdy współrzędne drugiego wierzchołka różnią się dokładnie na jednym miejscu od współrzędnych pierwszego wierzchołka.. Wiadomo również, że k-kostka jest grafem k-regularnym czyli z każdego wierzchołka wychodzi dokładnie k krawędzi. Łatwo udowodnić, że długość każdej z nich wynosi 1.
Tak więc w Twoim przypadku wybieramy jeden z 4 wierzchołków na pierwszy ruch i dla każdego wierzchołka jeden z kolejnych 4.. Mamy więc 4x4=16 takich tras.
Nie wiem czy trasą możemy nazwać przejście z pierwszego wierzchołka do drugiego i później wrócenie do tego pierwszego. Jeśli nie to odpadną 4 z tych 16 przypadków tras. Pozdrawiam
zgodnie z definicją k-kostki wierzchołek jest połączony krawędzią z innym wierzchołkiem gdy współrzędne drugiego wierzchołka różnią się dokładnie na jednym miejscu od współrzędnych pierwszego wierzchołka.. Wiadomo również, że k-kostka jest grafem k-regularnym czyli z każdego wierzchołka wychodzi dokładnie k krawędzi. Łatwo udowodnić, że długość każdej z nich wynosi 1.
Tak więc w Twoim przypadku wybieramy jeden z 4 wierzchołków na pierwszy ruch i dla każdego wierzchołka jeden z kolejnych 4.. Mamy więc 4x4=16 takich tras.
Nie wiem czy trasą możemy nazwać przejście z pierwszego wierzchołka do drugiego i później wrócenie do tego pierwszego. Jeśli nie to odpadną 4 z tych 16 przypadków tras. Pozdrawiam