Ilość grafów prostych (oznakowanych)

[martin_bar]

Witam.
Jak udowodnić, że istnieje dokładnie \(\displaystyle{ 2 ^{n(n-1)/2}}\)

Wiem że dla grafów pełnych oznakowanych jest \(\displaystyle{ {n \choose 2}}\)

[brzoskwinka1]

Jeśli mamy \(\displaystyle{ n}\) wierzchołków , to wszystkich możliwych krawędzi jest \(\displaystyle{ n\choose 2}\). Oznaczmy ich zbiór przez \(\displaystyle{ A=\{e_1 , ...,e_l\} ,}\) gdzie \(\displaystyle{ l= {n\choose 2}}\). Wszystkich więc grafów będzie tyle ile jest wszystkich podzbiorów zbioru \(\displaystyle{ A,}\) czyli \(\displaystyle{ 2^l =2^{n\choose 2} =2^{\frac{n(n-1)}{2}} .}\)

[yorgin]

Stara (?) dyskusja na ten temat: 322596.htm

Można na to zadanie popatrzeć przez pryzmat macierzy przejścia - każda taka macierz jest jednoznacznie wyznaczona przez zera i jedynki nad albo pod przekątną (na przekątnej są same zera). Łatwo sprawdzić, że dla \(\displaystyle{ n}\) wierzchołków mamy do uzupełnienia \(\displaystyle{ {n\choose 2}}\) pól, każde zero-jedynkowe.