Graf o pewnej postaci

[tonyhouk]

Cześć!
Mam takie zadanie:

Zbuduj graf mający zbiór wierzchołków postaci \(\displaystyle{ B \times B \times B}\), gdzie \(\displaystyle{ B=\left\{ 0,1\right\}}\),w którym wierzchołki v i w są połączone krawędzią, gdy v i w różnią się na dokładnie dwóch współrzędnych. Ile składowych ma ten graf?

Czy mógłby ktoś wyjaśnić jak powinny wyglądać te wierzchołki nie bardzo rozumiem o co chodzi z tą postacią? Co oznacza pojęcie składowej grafu?

[Medea 2]

Weź wierzchołki sześcianu \(\displaystyle{ [0,1] \times [0,1] \times [0,1]}\) i połącz tak, jak Ci kazali.

[tonyhouk]

Ok mam a co z tymi składowymi?

[Medea 2]

Narysuj sobie to. Z czym połączony jest wierzchołek \(\displaystyle{ (0,0,0)}\)?

[tonyhouk]

Z \(\displaystyle{ \left( 0,1,1\right), \left( 1,1,0\right) i \left( 1,0,1\right)}\)

[lgamon]

Ponawiam pytanie o składowe grafu, jak je pokazać?

[Medea 2]

Palcem? tonyhouk, wskazał już jedną składową, można się domyślać, że niewymienione wierzchołki utworzą drugą.

[lgamon]

Czyli teraz patrze na to z czym jest połączone \(\displaystyle{ \left( 0,0,1\right)}\)?

[tonyhouk]

Chyba tak A jak to będzie z grafem w przypadku gdy, wierzchołki v i w są połączone krawędzią, gdy v i w różnią się na dwóch lub trzech współrzędnych, tzn. czy da się go jakoś rozbić na kilka tak smao jak w pierwszym przypadku?

[Medea 2]

Jak na dwóch lub trzech, to mamy problem: wiemy, że składowe będą co najwyżej dwie. W jednej będzie \(\displaystyle{ (0,0,0)}\), w drugiej \(\displaystyle{ (1,1,1)}\)... chwila, one są w jednej składowej (dostaniecie spójny graf).

[tonyhouk]

Czy tak wygląda ten graf?

[Medea 2]

Mathematica jest cudna, przysięgam Zmieniając dokładnie jeden znak można dostać rozwiązanie pierwotnego problemu.

Kod: Zaznacz cały

fun[n_] := PadLeft[IntegerDigits[n, 2], 3]
AdjacencyGraph[
 Table[If[Total[Map[Mod[#, 2] &, fun[i] + fun[j]]] >= 2, 1, 0], {i, 0,
    7}, {j, 0, 7}]]

Daje to:

AU

lzsRDLU.jpg (7.51 KiB) Przejrzano 123 razy