4 zadania

[Feniks]

zadanie 1
Niech G będzie grafem dwudzielnym (V _{1}, E, V _{1}), w którym każdy wierzchołek w V _{1} ma stopień co najmiej d(>0) a każdy wierzcholek w V _{2} ma stopień co najwyżej d. Pokazać, że G zawiera skojarzenie z V _{1} do V _{2}. Wywnioskować, że jeżeli każdy wierzchołek w G ma stopień d, to zbiór krawędzi E może być wyrażony przez sumę d rozłącznych skojarzeń z V _{1} do V _{2}.


zadanie 2
Mając do dyspozycji n klatek ustawionych szeregowo, chcemy rozmieścić k nierozróżnialnych lwów tak, by w każdej klatce był co najwyżej jeden lew i by żadne lwy nie sąsiadowały ze sobą. Niech g(n,k) bedzie liczbą sposobów rozmieszczania lwów zgodnie z podanymi warunkami. Udowodnic ze
(1) g(2k - 1,k) = 1
(2) g(n,k) = 0 gdy n < 2k - 1
(3) g(n,1) = n
(4) g(n,k) = g(n - 2,k - 1) + g(n - 1,k), dla k qslant 2
(5) g(6,3) = 4
(6) g(2k,k) = k + 1


zadanie 3
Niech G będzie grafem i niech n będzie dodatnią liczbą całkowitą . Pokazać że (x - n) jest czynnikiem wielomianu p _{G}(x) wtedy i tylko wtedy gdy n < X(G).


zadanie 4
Jeżeli narysujemy na płaszczyźnie n prostych z których żadne 2 nie są równoległe oraz żadne 3 nie przecinają sie w jednym punkcie to ile będzie wszystkich punktów przecięcia?


z góry dziękuje za pomoc w zadaniach, pozdrawiam

[UNIX_admin]

Ad. 1.
Rozumiem, ze chodzi tu o grafowa wersje tw. Halla. dowod latwiej przeprowadzic dla wersji malzenskiej. zbiory wierzcholkow to odpowiednio zbiory dziewczat i chlopcow, krawedzie oznaczaja znajomosci, do skojarzenia bierzemy znajomosci(krawedzie) zakonczone malzenstwem.
udowodnimy, ze kazda dziewczyna moze wyjsc za maz za chlopca, ktorego zna jesli gdy dowolny zbior (np. d) dziewczat zna lacznie przynajmniej d chlopcow
DOWOD:
=> kazda dziewczyna zna przynajmniej swojego meza