Grafy z liczbami pierwszymi oraz funkcje

[GypsyHatter]

Hej, mam trochę zadań i ogólnie staram się kombinować, ale nigdy nie jestem pewien odpowiedzi albo nawet od czego zacząć, może ktoś coś podpowie:

1. Niech p i q będą różnymi liczbami pierwszymi. Definiujemy graf G = (V, E), gdzie zbiór wierzchołków V jest zbiorem wszystkich dzielników liczby \(\displaystyle{ a = p^{2} q^{3}}\), które są większe od 1 i mniejsze od a. Dwie liczby u,w ze zbioru V łączy krawędź należąca do E wtedy i tylko wtedy, gdy \(\displaystyle{ NWD(u, w) > 1}\).
a)Wypisać wszystkie wierzchołki grafu.
b)Określić stopnie poszczególnych wierzchołków i korzystając z lematu o uścisku dłoni określić liczbę krawędzi grafu G.
c)Udowodnić, że graf jest spójny. Zbadać, czy jest grafem hamiltonowskim i eulerowskim.

Od czego w ogóle tutaj zacząć?

2. Wyznacz liczbę surjekcji ze zbioru \(\displaystyle{ X}\) na jego podzbiór \(\displaystyle{ \{1, 2, 3, 4, 5, 6, 7, 8, 9\}}\), które sa funkcjami niemalejącymi.

odp: 2?

3. Jakich podzbiorów zbioru \(\displaystyle{ \left\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\right\}}\) jest więcej: zawierających mniej niż połowę elementów tego zbioru czy zawierających więcej niż połowę elementów tego zbioru?

4. Wyznacz liczbę wszystkich funkcji ze zbioru \(\displaystyle{ \left\{1, 2, 3, 4, 5 \right\}}\) w zbiór \(\displaystyle{ \left\{ 1, 2, 3, 4, 5, 6\right\}}\), które nie są injekcjami.

[Premislav]

Ad. 2 A jak wygląda zbiór \(\displaystyle{ X}\)?

3. Zauważ, że \(\displaystyle{ {n \choose k}={n \choose n-k}}\) dla \(\displaystyle{ n,k \in \NN, \ 0\le k\le n}\), a liczba podzbiorów k-elementowych zbioru n-elementowego to \(\displaystyle{ {n \choose k}}\). Czyli
\(\displaystyle{ {10 \choose 0}={10 \choose 10}, {10\choose 1}={10\choose 9}, \ldots {10 \choose 4}={10 \choose 6}}\)
Odpowiedź: jest ich tyle samo.

4. Injekcji jest \(\displaystyle{ {6 \choose 5}\cdot 5!=6!}\), a wszystkich funkcji mamy \(\displaystyle{ 6^5}\) (dla każdego z pięciu argumentów mamy sześć możliwości przypisania wartości), od tej drugiej liczby odejmij pierwszą.

[GypsyHatter]

\(\displaystyle{ X = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}}\).

[Premislav]

Sorry, tam wyżej oczywiście miało być \(\displaystyle{ 6^5}\), a nie \(\displaystyle{ 5^6}\)… Poprawiłem, ale nie wiem, czy widziałeś.

To w takim razie co do zadania 2.
moim zdaniem jest ich trochę więcej. Dokładnie jedna wartość ma się powtarzać, bo argumentów (czyli elementów \(\displaystyle{ X}\)) jest \(\displaystyle{ 10}\), a oczywiście zbiór \(\displaystyle{ \left\{ 1,2,3,4,5,6,7,8,9\right\}}\) ma \(\displaystyle{ 9}\) elementów i skoro interesują nas surjekcje, to wszystkie one muszą być przyjmowane jako wartości.
Mnie wyszło, że jest \(\displaystyle{ 9}\) takich funkcji. Możliwości:
\(\displaystyle{ f(1)=1, f(k+1)=k \text{ dla }k=1, \ldots 9\\ f(1)=1, f(2)=2, f(k+1)=k \text{ dla } k=2, \ldots 9}\)
i tak dalej. Schemat: dokładnie jedna wartość ma się powtarzać, więc możemy patrzeć na to, w którym miejscu (tj. dla jakich argumentów) wypada ta wartość, która się powtarza.

A z pierwszym nie pomogę, bo nic nie pamiętam z teorii grafów.