Liczba grafów skierowanych bez wierzchołków izolowanych

[k1npatsu]

Obliczyć liczbę różnych grafów prostych skierowanych o n wierzchołkach bez wierzchołków izolowanych. Dwa grafy są różne, jeśli istnieją dwa wierzchołki, które w jednym grafie są połączone krawędzią, a w drugim nie.

Wiem tyle, że muszę skorzystać z zasady włączeń i wyłączeń.

[arek1357]

\(\displaystyle{ 2^{ {n \choose 2} \cdot 2 }=2^{n^2-n}}\)

[k1npatsu]

\(\displaystyle{ 2^{ {n \choose 2} \cdot 2 }}\)

Skąd taka odpowiedź? W jaki sposób eliminuje ona wyłącznie wierzchołki izolowane?

[arek1357]

Biorę z macierzy sąsiedztwa, nie bardzo kumam o co chodzi z twoimi wierzchołkami izolowanymi...,
tzn,że nie może być pętelek czy mogą być...

Macierz sąsiedztwa grafów skierowanych nie musi być symetryczna...

[k1npatsu]

Biorę z macierzy sąsiedztwa, nie bardzo kumam o co chodzi z twoimi wierzchołkami izolowanymi...,
tzn,że nie może być pętelek czy mogą być...

Macierz sąsiedztwa grafów skierowanych nie musi być symetryczna...

Wierzchołek izolowany to taki, który nie jest końcem żadnej krawędzi. Gdyby nie było tego warunku to odpowiedzią byłoby:
\(\displaystyle{ 4^{n \choose 2}}\).

[arek1357]

Czyli pętelki mogą być bo wtedy wierzchołek nie jest izolowany...

[k1npatsu]

Czyli pętelki mogą być bo wtedy wierzchołek nie jest izolowany...

Nie jestem pewien czy to masz na myśli, ale przypadku kiedy wierzchołek ma krawędź z samym sobą nie uwzględniamy.

[arek1357]

A to w takim razie zmienia postać rzeczy


Powinno być tak, patrząc na macierz sąsiedztwa:

Wiadomo, że w macierzy sąsiedztwa występują jedynki, a na głównej przekątnej zera.

\(\displaystyle{ a_{ij}=1}\) oznacza że wierzchołek 1 i 2 jest połączony strzałką,

\(\displaystyle{ a_{ji}=1}\) oznacza że wierzchołek 2 i 1 jest połączony strzałką,

\(\displaystyle{ a_{ji}=1 \wedge a_{ji}=1}\) oznacza że wierzchołek\(\displaystyle{ (1 i 2) \wedge (2 i 1)}\) jest połączony strzałką,

I teraz z obserwacji, żeby nie było wierzchołków izolowanych ani pętelek, zawsze przynajmniej jedna wartość:

\(\displaystyle{ a_{ij} \vee a_{ji}, i \neq j}\)

musi być różna od zera, co po przyjrzeniu się macierzy sąsiedztwa daje nam możliwości:

\(\displaystyle{ \sum_{s=0}^{ \frac{n^2-n}{2} } { \frac{n^2-n}{2} \choose s} \cdot \sum_{i=0}^{\frac{n^2-n}{2}-s} { \frac{n^2-n}{2}-s \choose i}=}\)

\(\displaystyle{ =2^{ \frac{n^2-n}{2}} \sum_{s=0}^{ \frac{n^2-n}{2}} { \frac{n^2-n}{2} \choose s} \cdot \frac{1}{2^s}}\)