szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 lut 2012, o 00:05 
Użytkownik

Posty: 41
Lokalizacja: Wrocław
Witam,
mam kilka zadań do rozwiązania, głównie dotyczą izomorfizmu grafów:

zad.1: "Narysować wszystkie nieizomorficzne grafy proste o pięciu wierzchołkach i czterech krawędziach."

Jeśli grafy są takie same, to są izomorficzne.
Wymyśliłem coś takiego:
Obrazek
Pytanie: czy to są wszystkie grafy, które spełniają warunek z zadania? Jeśli nie, to jak można wyznaczyć, ile takich grafów istnieje? Są jakieś wzory pozwalające to wyznaczyć?

zad.2: "Dla jakich n istnieją grafy proste o n wierzchołkach, w których każdy wierzchołek ma stopień r = 3? Narysować wszystkie nieizomorficzne takie grafy dla n = 6."

nie mam pomysłu, jak się za to wziąć

zad.3: "Graf prosty ma 7 wierzchołków, a każdy jego wierzchołek ma taki sam stopień r > 0. Jakie wartości może przyjąć liczba r? Podać realizacje."

Maksymalny stopień wierzchołka, aby graf był prosty możemy wyliczyć ze wzoru: deg(v_{i}) = n-1, więc w tym zadaniu ten stopień równa się n = 7 -1 = 6. Z kolei ze wzoru na sumę stopni wierzchołków: \sum_{i=1}^{n} deg(v_{i}) = 2|E| (gdzie E oznacza liczbę krawędzi) wynika, że liczba wierzchołków razy stopień musi być liczbą parzystą (bo jeśli będzie np. stopień r=3, to musiałoby być 7 \cdot 3 = 21 krawędzi, a 21 nie dzieli się przez 2, więc graf nie istniałby). W związku z tym moim zdaniemr musiałoby być równe 2 lub 4 lub 6.
Grafy wyglądałyby następująco:
Obrazek

zad.4: "Multigraf bez pętli ma 4 wierzchołki i każdy wierzchołek jest stopnia r = 3. Narysować wszystkie nieizomorficzne multigrafy o podanych parametrach."

Problem właściwie ten sam, co w zadaniu 1, w jaki sposób sprawdzić, ile istnieje takich grafów?
Wymyśliłem tylko taki:
Obrazek

zad.5: "Każdy z jedenastu uczestników konferencji znał dokładnie trzech albo pięciu uczestników tej konferencji. Czy mogła odbyć się taka konferencja? Zakładamy, że jeśli osoba A zna B, to B zna również A. Przyjmujemy też, że nie uwzględniamy pętli."

Moim zdaniem sytuację z zadania można opisać grafem: n = 11 (uczestnicy konferencji, czyli liczba wierzchołków), r = 3 lub r = 5 (liczba znajomych, czyli stopień wierzchołka).
Ponownie korzystając ze wzoru:
\sum_{i=1}^{n} deg(v_{i}) = 2|E|
mamy:
\sum_{i=1}^{11} deg(v_{i}) = 11 \cdot 3 = 33, czyli suma stopni wynosi 33, więc jako że 33 nie dzieli się przez 2 czyli nie da się wyznaczyć liczby krawędzi, zatem graf nie istnieje, więc konferencja się nie odbyła. Dokładnie tak samo dla 5. Czy dobrze rozumuję?

Proszę o zweryfikowanie poprawności rozwiązań, które przedstawiłem i o pomoc w rozwiązaniu tego, czego nie rozwiązałem.
Z górzy dziękuję,
pozdrawiam.
Góra
Mężczyzna Offline
PostNapisane: 27 lut 2015, o 19:58 
Użytkownik

Posty: 157
Lokalizacja: Bagdad
Up, też mam podobny problem.
Dodatkowo jaki jest algorytm wyznaczania różnych grafów ( nieizomorficznych ) o danych np. wierzchołkach?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kojarzenie grafów dwudzielnych  tukanik  2
 Liczba grafow o podanych stopniach wierzcholkow  pcchack  0
 [Teoria grafów] Ilość krawędzi w grafie planarnym  matinf  4
 Zadania z grafów, dyskretna  Student_matmy  1
 Zadanie z teorii mnogości.  Finarfin  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl