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

Posty: 94
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
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 09:34 
Użytkownik
Avatar użytkownika

Posty: 1202
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: 94
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: 1202
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: 268
Lokalizacja: o-o
n?
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2015, o 14:34 
Użytkownik
Avatar użytkownika

Posty: 1202
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ść kombinacji Warcaby  Toxic  6
 Teoria grafów - zadanie 3  flake  1
 Teoria grafów - zadanie 9  kiler69  2
 Ilość drzew o maksymalnym stopniu wierzchołka  Fray  0
 Ilosc sposobow,podloga- nx3 plytki- 2x1  dejwid13_93  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl