szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 28 sie 2013, o 15:39 
Użytkownik

Posty: 36
Lokalizacja: Kraśnik
Witam, proszę o pomoc w rozwiązaniu paru zadań:
1) Mamy p kul białych i q kul czarnych, wkładamy je jedna za drugą. Ile jest sposobów takiego ułożenia jeżeli dwie kule czarne nie mogę leżeć obok siebie?

2) Należy zorganizować plan kontaktów w siadce składającej się z 20 agentów. Plan należy zorganizować tak, aby było możliwe przekazanie wiadomości między dowolnymi agentami, ale liczbe kontaktów nalezy ograniczyć do minimum. Ile jest mozliwości ułozenia takiego planu? A jeżeli agent X jest nowy i może się kontaktować z tylko jednym agentem??

3) Srednim stopniem wierzchołka nazywamy liczbę y= \frac{E}{V}. Wykaż, że dla grafu spójnego zachodzi 1- \frac{1}{V} \le y \le  \frac{V}{2}.

4) Ciąg zdefiniowany rekurencyjnie a_{1}=  a_{2}= a_{3}=1,  a_{n}= a_{n-1}+a _{n-3}, n \ge 3. Udowodnić, że a _{n} \le \left(  \frac{3}{2} \right) ^{n-1}, n \ge 0.

5) Graf taki, że \left| V\right|  \ge 2. Uzasadnić, że graf ten zawiera dwa wierzchołki o tym samym stopniu.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2013, o 19:44 
Użytkownik

Posty: 320
Lokalizacja: Warszawa
2) Jeśli wiadomość ma być przekazana pomiędzy dwoma dowolnymi agentami, to graf kontaktów musi być spójny. Skoro ma być to najmniejszy graf możliwy, to musi być drzewem. Jak rozumiem, każdy agent jakoś się nazywa, więc to drzewo jest oznaczone. Liczba drzew oznaczonych o n wierzchołkach to, wg. tw. Cayleya, n^{n-2}. Jeżeli agent X jest nowy, to liczba grafów, które będą spełniać warunki zadania to liczba wszystkich drzew oznaczonych o 19 wierzchołkach, przemnożona przez 19 - tego nowego agenta można zaznajomić z dowolnym starym.
Góra
Mężczyzna Offline
PostNapisane: 29 sie 2013, o 19:59 
Użytkownik

Posty: 1070
Lokalizacja: Lublin/Warszawa
5) Rozumiem, że graf jest prosty (tzn. nie ma pętli i krawędzi wielokrotnych). Nie wprost. Mamy n wierzchołków. Załóżmy, że każdy wierzchołek ma inny stopień. Ponieważ wierzchołek nie może być połączony z samym sobą to każdy z wierzchołków może mieć stopień co najwyżej n-1. Tak więc wierzchołki mają stopnie 0, 1, 2, ..., n-1, czyli istnieją dwa wierzchołki o stopniach 0 i n-1, ale oznacza to że jeden wierzchołek jest połączony ze wszystkimi pozostałymi, a inny z żadnym z pozostałych - sprzeczność, czyli teza jest prawdziwa.
Góra
PostNapisane: 30 sie 2013, o 01:21 
Użytkownik
3) Wystarczy pokazać, że E \ge V-1 , gdyż druga nierówność jest oczywista.
Dowód przeprowadzimy przez indukcję względem liczby wierzchołków. Dla grafu o jednym wierzchołku nierówność jest oczywista. Niech więc twierdzenie będzie prawdziwe dla wszystkich spójnych grafów o k wierzchołkach gdzie k \le n. Wybierzmy teraz spośród wszystkich spójnych grafów o n+1 dowolny ale taki który ma najmniejszą liczbę krawędzi i oznaczmy go przez G. Wybierzmy dowolną krawędź grafu G i usuńmy ją. Graf G się rozspójni przy czym otrzymamy dokładnie dwie składowe spójności. Oznaczmy je przez (V_1 , E_1 ) , (V_2 , E_2 ) stosując założenie indukcyjne do każdej ze składowych mamy E_1  \ge V_1 -1 ,E_2  \ge V_2 -1 skąd E(G) -1 =E_1 +E_2  \ge V_1 -1 +V_2 -1 =V(G) -2 .
Góra
Mężczyzna Offline
PostNapisane: 3 wrz 2016, o 15:45 
Użytkownik

Posty: 1070
Lokalizacja: Lublin/Warszawa
1) Ustawiamy wszystkie kule białe obok siebie. Teraz musimy umieścić między kulami białymi (lub na brzegach) kule czarne tak, aby żadne dwie kule czarne nie były obok siebie, czyli w każdą z p + 1 luk możemy wstawić co najwyżej jedną kulę czarną.
Wybieramy w które luki wstawiamy czarne kule - możemy to zrobić na {p + 1 \choose q} sposobów.

4) Prosta indukcja.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 Zbiór zadań - KOMBINATORYKA  Arek  0
 Pięć pań i pięciu panów - kombinatoryka  Anonymous  1
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl