kombinatoryka, grafy - zadania

[gelusia]

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ę \(\displaystyle{ y= \frac{E}{V}}\). Wykaż, że dla grafu spójnego zachodzi \(\displaystyle{ 1- \frac{1}{V} \le y \le \frac{V}{2}}\).

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

5) Graf taki, że \(\displaystyle{ \left| V\right| \ge 2}\). Uzasadnić, że graf ten zawiera dwa wierzchołki o tym samym stopniu.

[porfirion]

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 \(\displaystyle{ n}\) wierzchołkach to, wg. tw. Cayleya, \(\displaystyle{ n^{n-2}}\). Jeżeli agent \(\displaystyle{ X}\) jest nowy, to liczba grafów, które będą spełniać warunki zadania to liczba wszystkich drzew oznaczonych o \(\displaystyle{ 19}\) wierzchołkach, przemnożona przez \(\displaystyle{ 19}\) - tego nowego agenta można zaznajomić z dowolnym starym.

[Mruczek]

5) Rozumiem, że graf jest prosty (tzn. nie ma pętli i krawędzi wielokrotnych). Nie wprost. Mamy \(\displaystyle{ 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 \(\displaystyle{ n-1}\). Tak więc wierzchołki mają stopnie \(\displaystyle{ 0}\), \(\displaystyle{ 1}\), \(\displaystyle{ 2}\), ..., \(\displaystyle{ n-1}\), czyli istnieją dwa wierzchołki o stopniach \(\displaystyle{ 0}\) i \(\displaystyle{ 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.

[brzoskwinka1]

3) Wystarczy pokazać, że \(\displaystyle{ 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 \(\displaystyle{ k}\) wierzchołkach gdzie \(\displaystyle{ k \le n.}\) Wybierzmy teraz spośród wszystkich spójnych grafów o \(\displaystyle{ n+1}\) dowolny ale taki który ma najmniejszą liczbę krawędzi i oznaczmy go przez \(\displaystyle{ G.}\) Wybierzmy dowolną krawędź grafu \(\displaystyle{ G}\) i usuńmy ją. Graf \(\displaystyle{ G}\) się rozspójni przy czym otrzymamy dokładnie dwie składowe spójności. Oznaczmy je przez \(\displaystyle{ (V_1 , E_1 ) , (V_2 , E_2 )}\) stosując założenie indukcyjne do każdej ze składowych mamy \(\displaystyle{ E_1 \ge V_1 -1 ,E_2 \ge V_2 -1}\) skąd \(\displaystyle{ E(G) -1 =E_1 +E_2 \ge V_1 -1 +V_2 -1 =V(G) -2 .}\)

[Mruczek]

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 \(\displaystyle{ 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 \(\displaystyle{ {p + 1 \choose q}}\) sposobów.

4) Prosta indukcja.