Matematyka.pl

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:

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: \(\displaystyle{ deg(v_{i}) = n-1}\), więc w tym zadaniu ten stopień równa się \(\displaystyle{ n = 7 -1 = 6}\). Z kolei ze wzoru na sumę stopni wierzchołków: \(\displaystyle{ \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ć \(\displaystyle{ 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:


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:


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:
\(\displaystyle{ \sum_{i=1}^{n} deg(v_{i}) = 2|E|}\)
mamy:
\(\displaystyle{ \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.

Up, też mam podobny problem.
Dodatkowo jaki jest algorytm wyznaczania różnych grafów ( nieizomorficznych ) o danych np. wierzchołkach?