Graf mający zbiór wierzchołków

Cabalerio · Post autor: **Cabalerio** » 9 cze 2011, o 15:52

Spotkałem się w treści zadania z czymś takim: "zbuduj graf mający zbiór wierzchołków {0,1}x{0,1}x{0,1}, w którym wierzchołki v i w są połączone krawędzią, jeśli ciągi v i w różnią się na dokładnie dwóch współrzędnych". Mógłby ktoś ze 2 takie narysować bo nie wiem jak to rozumieć.

xiikzodz · Post autor: **xiikzodz** » 9 cze 2011, o 16:01

Jest dokładnie jeden taki graf.

Ma on 8 wierzchłków postaci i na przykład pomiędzy wierzchołkiem \(\displaystyle{ (0,1,0)}\) a wierzchołkiem \(\displaystyle{ (1,0,0)}\) jest krawędź, a pomiędzy wierzchołkiem \(\displaystyle{ (0,1,0)}\) a wierzchołkiem \(\displaystyle{ (1,0,1)}\) nie ma krawędzi.

Nietrudno zauważyć, że ten graf jest izomorficzny z grafem wierzchołków i krawędzi sześcianu.

Cabalerio · Post autor: **Cabalerio** » 9 cze 2011, o 16:07

8 wierzchołków bo jest 8 sposobów na zrobienie 3 cyfrowych ciągów z 0 i 1 tak ?

jak wywnioskowałeś ze pomiędzy wierzchołkami są krawędzie albo ich nie ma ?

xiikzodz · Post autor: **xiikzodz** » 9 cze 2011, o 16:14

8 - dokładnie dlatego.

Krawędzie powinny być inaczej. U mnie była gdy różniły się dokładnie na jednej współrzędnej. A powinno być, gdy mają dokładnie jedną taką samą współrzędną.

Jest to więc graf, którego wierzchołkami są wierzchołki sześcianu o wierzchołkach w tych punktach, zaś krawędziami przekątne jego ścian. Mimo wszystko jest to jednak wciąż ten sam graf z dokładnością do izomorfizmu.