Diskretna matematika

pismeni deo ispita

08.09.2004.

1. Na koliko se načina 4n vojnika (različitih po visini) može rasporediti u četiri vrste, tako da su u svakoj koloni vojnici poređani po visini od najnižeg ka najvišem?
2. Korišćenjem metoda zmijskog ulja izračunati .
3. Dokazati da su sledeći grafovi međusobno izomorfni.

4. Dokazati da graf čiji su svi čvorovi parnog stepena ne sadrži most.
5. Pretpostavimo da je G povezan graf koji ne sadrži indukovani podgraf sa četiri čvora izomorfan sa putem ili ciklusom. Dokazati da G sadrži čvor susedan sa svim ostalim čvorovima.