szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 02: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ń.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 07:49 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
2^{ {n \choose 2} \cdot 2 }=2^{n^2-n}
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 11: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 12:34 
Użytkownik
Avatar użytkownika

Posty: 3232
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 12: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 13:01 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Czyli pętelki mogą być bo wtedy wierzchołek nie jest izolowany...
Góra
Mężczyzna Offline
PostNapisane: 12 mar 2018, o 13: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 13:08 
Użytkownik
Avatar użytkownika

Posty: 3232
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 
 Liczba szesnastkowa na binarną - dowód algorytmu  Lukassz  3
 Graf o parzystym stopniu wierzchołków a most  Alojzy Pompka  2
 liczba ciągów - zadanie 2  MikolajB  15
 Liczba całkowitoliczbowych rozwiązań równania  pinksaid  3
 ilość wierzchołków w drzewie - zadanie 2  Rastaman697  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl