szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 01:44 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
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ń.
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 06:49 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
2^{ {n \choose 2} \cdot 2 }=2^{n^2-n}
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 10:05 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
arek1357 napisał(a):
2^{ {n \choose 2} \cdot 2 }

Skąd taka odpowiedź? W jaki sposób eliminuje ona wyłącznie wierzchołki izolowane?
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 11:34 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
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...
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 11:55 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
arek1357 napisał(a):
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:
4^{n \choose 2}.
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 12:01 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
Czyli pętelki mogą być bo wtedy wierzchołek nie jest izolowany...
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 12:05 
Użytkownik

Posty: 4
Lokalizacja: Wrocław
arek1357 napisał(a):
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.
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 12:08 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
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.

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

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

a_{ji}=1  \wedge a_{ji}=1 oznacza że wierzchołek(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ść:

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:

\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}=

=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}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 możliwa liczba słów ze słowa 'matematyka' (wytłumaczenie)  exculibrus  4
 Liczba elementów  Neox  2
 Udowodnić, że liczba podziałów  matinf  1
 Parzysta liczba wierzchołków o stopniach nieparzystych  Nitr0Skay  8
 Liczba sposobów na przejście z jednego pkt do drugiego.  Valiors  11
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl