Ilość grafów etykietowanych.

[akermann1]

Witam natknąłem się z następującymi pytaniami:

1) Ile jest grafów etykietowanych o \(\displaystyle{ n-1}\) krawędziach.
2) Ile jest grafów nie etykietowanych o \(\displaystyle{ n-1}\)krawędziach.

Proszę o pomoc.

Moje przemyślenia:

Skoro mamy \(\displaystyle{ n-1}\) krawędzi i każda krawędź łączy \(\displaystyle{ 2}\) wierzchołki i ten graf myślę, że powinien mieć \(\displaystyle{ n}\) wierzchołków zatem na myśl w podpunkcie tym pierwszym przychodzi mi:

\(\displaystyle{ \frac{n \cdot (n-1)}{2}}\) grafów

[jutrvy]

Nie prawda, że ten graf powinien mieć \(\displaystyle{ n}\) wierzchołków. Ty podałeś liczbę grafów o \(\displaystyle{ n}\) wierzchołkach, które są pełne - źle.

[akermann1]

To może jakaś podpowiedź?

[jutrvy]

Mamy \(\displaystyle{ n-1}\) odcinków, każdy z tych odcinków ma dwa końce. Jeśli chcesz rozważać grafy etykietowane, to możesz sobie te końce jakoś ponumerować. Tych końców będzie \(\displaystyle{ 2(n-1)}\). Teraz pytamy się, na ile sposobów można te odcinki pozlepiać ze sobą końcami (dwa odcinki można zlepić co najwyżej jednym końcem - nie można zlepić z sobą dwóch odcinków dwoma końcami, bo nam się zlepi krawędź - przyjąłem, że nie liczysz krawędzi wielokrotnych i pętelek). Ile jest takich możliwości?

[nowik1991]

\(\displaystyle{ n}\)?

[jutrvy]

Nie. Może inaczej. Zastanów się nad tym, jak można rozmieścić stopnie między wierzchołki (zakładamy, że dla dowolnego \(\displaystyle{ v\in V}\) zachodzi \(\displaystyle{ \hbox{deg}(v) > 0}\)). Zauważ, że

\(\displaystyle{ \sum_{v\in V}\hbox{deg}(v) = 2(n-1)}\).

Wskazówka: może przydatna będzie wiedza o rozmieszczeniach?...