Liczba krawędzi, zbiór niezależny, dzielniki.

[msq93]

Witam!

Mam problem z zadaniami dot. teorii grafów. Potrzebuje pilnie naprowadzenia na jakieś wnioski.

1. Udowodnij, że maksymalna liczba krawędzi w prostym niespójnym grafie o n wierzchołkach wynosi
\(\displaystyle{ \frac{\left( n-1\right) \cdot \left( n-2\right)}{2}}\)

2. Ile dzielników ma liczba \(\displaystyle{ 13!}\) ?

3. Zbiorem niezależnym w grafie nazywamy podzbiór zbioru wierzchołków, w którym żadne dwa wierzchołki nie sąsiadują ze sobą. Niech \(\displaystyle{ P_n}\) oznacza graf w postaci prostej drogi o \(\displaystyle{ n}\) wierzchołkach. Wyznacz liczbę wszystkich podzbiorów
niezależnych w \(\displaystyle{ P_n}\).
(Podpowiedz: Najpierw zdefiniuj tę liczbę równaniem rekurencyjnym..)

Z góry serdecznie dziękuje!-- 9 cze 2014, o 20:12 --Dobra, drugie zadanie rozwiązałem

\(\displaystyle{ 13! = 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\)

Znamy wzór na określenie liczby dzielników tj. \(\displaystyle{ \left( k_{1} + 1\right) \cdot \left( k_{2} + 1\right) ... \left( k_{n} + 1\right)}\) oraz że liczby naturalne możemy zapisać w postaci iloczynu liczb pierwszych.

Tak więc otrzymujemy po wykonaniu rozkładu na czynniki następujący zapis:

\(\displaystyle{ 2^{9} \cdot 3^{5} \cdot 5^{2} \cdot 13^{1} \cdot 11^{1} \cdot 7^{1} = 13!}\)

Stąd, używając wzoru na dzielniki (używamy rzecz jasna wykładnika potęgi)

\(\displaystyle{ 10 \cdot 8 \cdot 6 \cdot 3 = 1440}\)

Odp: 13! ma 1440 dzielników.