szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 maja 2015, o 21:57 
Użytkownik

Posty: 87
Lokalizacja: Starogard
Cześć!
Mam takie zadanie:

Zbuduj graf mający zbiór wierzchołków postaci B \times B \times B, gdzie 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?
Góra
Kobieta Offline
PostNapisane: 3 maja 2015, o 22:19 
Użytkownik
Avatar użytkownika

Posty: 2505
Weź wierzchołki sześcianu [0,1] \times [0,1] \times [0,1] i połącz tak, jak Ci kazali.
Góra
Mężczyzna Offline
PostNapisane: 3 maja 2015, o 22:40 
Użytkownik

Posty: 87
Lokalizacja: Starogard
Ok mam a co z tymi składowymi? :)
Góra
Kobieta Offline
PostNapisane: 3 maja 2015, o 22:42 
Użytkownik
Avatar użytkownika

Posty: 2505
Narysuj sobie to. Z czym połączony jest wierzchołek (0,0,0)?
Góra
Mężczyzna Offline
PostNapisane: 3 maja 2015, o 22:49 
Użytkownik

Posty: 87
Lokalizacja: Starogard
Z \left( 0,1,1\right), \left( 1,1,0\right) i \left( 1,0,1\right)
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2015, o 19:08 
Użytkownik

Posty: 68
Lokalizacja: Opole
Ponawiam pytanie o składowe grafu, jak je pokazać?
Góra
Kobieta Offline
PostNapisane: 5 maja 2015, o 19:13 
Użytkownik
Avatar użytkownika

Posty: 2505
Palcem? tonyhouk, wskazał już jedną składową, można się domyślać, że niewymienione wierzchołki utworzą drugą.
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2015, o 19:48 
Użytkownik

Posty: 68
Lokalizacja: Opole
Czyli teraz patrze na to z czym jest połączone \left( 0,0,1\right)?
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2015, o 20:33 
Użytkownik

Posty: 87
Lokalizacja: Starogard
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?
Góra
Kobieta Offline
PostNapisane: 5 maja 2015, o 20:42 
Użytkownik
Avatar użytkownika

Posty: 2505
Jak na dwóch lub trzech, to mamy problem: wiemy, że składowe będą co najwyżej dwie. W jednej będzie (0,0,0), w drugiej (1,1,1)... chwila, one są w jednej składowej (dostaniecie spójny graf).
Góra
Mężczyzna Offline
PostNapisane: 5 maja 2015, o 21:21 
Użytkownik

Posty: 87
Lokalizacja: Starogard
Czy tak wygląda ten graf?
Obrazek
Góra
Kobieta Offline
PostNapisane: 5 maja 2015, o 22:28 
Użytkownik
Avatar użytkownika

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

Kod:
1
2
3
4
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:

Obrazek
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf hamiltonowski - zadanie 2  placky  4
 Ile drzew spinających ma graf  De Moon  3
 graf k-refularny a istnienie cyklu hamiltona  karl153  2
 dla jakich n istnieje graf n-wierzochołkowy o st.3wierzchołk  bastek91  5
 Graf niekrytyczny na 7 wierzchołkach - zadanie 17  moncq  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl