szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 07:50 
Użytkownik

Posty: 97
Lokalizacja: Wrc
Witam natknąłem się z następującymi pytaniami:

1) Ile jest grafów etykietowanych o n-1 krawędziach.
2) Ile jest grafów nie etykietowanych o n-1krawędziach.

Proszę o pomoc.

Moje przemyślenia:

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

\frac{n \cdot (n-1)}{2} grafów
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 09:34 
Użytkownik
Avatar użytkownika

Posty: 1229
Nie prawda, że ten graf powinien mieć n wierzchołków. Ty podałeś liczbę grafów o n wierzchołkach, które są pełne - źle.
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 10:26 
Użytkownik

Posty: 97
Lokalizacja: Wrc
To może jakaś podpowiedź?
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 11:15 
Użytkownik
Avatar użytkownika

Posty: 1229
Mamy 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 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? :)
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 13:34 
Użytkownik

Posty: 269
Lokalizacja: o-o
n?
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 14:34 
Użytkownik
Avatar użytkownika

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

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

Wskazówka: może przydatna będzie wiedza o rozmieszczeniach?...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość odpowiednich krawędzi w n-kącie  novy154  4
 ilość minorów  PiTek93  1
 Ilość możliwości - zadanie 2  piotrek20008  1
 ilość sposobów wyboru  robsel  1
 Ilość oznakowanych grafów prostych  Adam51015  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl