drzewa spinające, grafy, rekurencja

[mwmkh]

Witam,

mam problem z następującymi zadaniami, czy ktoś mógłby mi je wytłumaczyć? Byłbym bardzo wdzięczny.

1. Ile drzew spinających ma graf etykietowany:

AU

Ygot7Me.jpg (4.48 KiB) Przejrzano 117 razy

2. Narysuj 3 grafy proste (nieizomorficzne) o 5 wierzchołkach, 6 krawędziach.

3. Znajdź funkcję tworzącą ciągu zadanego rekurencyjnie.

\(\displaystyle{ a_{o}=2, a_{n+1}=3a_{n}+2}\)

4. Wypisz podane funkcje w kolejności od najniższego rzędu do najwyższego:

\(\displaystyle{ n^{2}logn}\), \(\displaystyle{ log^{2}n}\), \(\displaystyle{ \sqrt{n}}\)oraz \(\displaystyle{ n!}\)

Raz jeszcze bardzo proszę o pomoc:)

[gardner]

1.A jaka jest definicja drzewa spinającego? To taki podgraf który zawiera wszystkie wierzchołki i jest drzewem.Najprościej takie konstruować wyrzucając krawędzie należące do cyklu.

2.Masz gdzieś błąd w zapisie. Rozwiązanie jest proste. Wyznaczasz funkcję charakterystyczną i rozwiązujesz równanie rekurencyjne. Poszukaj w internecie.