zadania, ISI UWM, Semestr II, Matematyka dyskretna
[ Pobierz całość w formacie PDF ]
//-->Zadanie 1Wykorzystując aparat funkcji tworzących rozwiąż równania rekurencyjne o podanych warunkach początkowych:a)an= 5an−1−6an−2b)bn= 3bn−1−2bn−2c)cn= 2cn−1+ 3cn−2d)dn=dn−1+ 2dn−2e)en= 5en−1−6en−2a= 2,a1= 5b= 2,b1= 3c= 1,c1= 3d= 1,d1= 3a=−1,a1= 1Zadanie 2Wykorzystując funkcje tworzące, oblicz na ile sposobów można rozmieścić:a)30identycznych kul w5(rozróżnialnych) szufladkach, jeżeli pierwsza szufladka może zawierać co najwyżej6kul, druga-4,a pozostałe mogą zawierać dowolną liczbe kulb)25identycznych kul w5(rozróżnialnych) szufladkach, jeżeli pierwsza szufladka może zawierać co najwyżej5kul, apozostałe mogą zawierać dowolną liczbe kulc)40identycznych kul w6(rozróżnialnych) szufladkach, jeżeli pierwsze dwie szufladki mogą zawierać co najwyżej10kul,a pozostałe mogą zawierać dowolną liczbe kuld)30identycznych kul w4(rozróżnialnych) szufladkach, jeżeli pierwsza szufladka może zawierać co najwyżej8kul, apozostałe mogą zawierać dowolną liczbe kule)20identycznych kul w5(rozróżnialnych) szufladkach, jeżeli pierwsza szufladka może zawierać co najwyżej8kul, apozostałe mogą zawierać dowolną liczbe kulZadanie 3Dla grafu zdefiniowanego przez zbiór wierzchołków i zbiór krawędzi, wyznacz liczbę wszystkich tras i wypisz te trasy:a) o długości3z wierzchołka2do4,V(G1) ={1,2, 3, 4, 5, 6},E(G1) ={16,12, 26, 25, 13, 24, 35, 23, 34}b) o długości4z wierzchołka1do2,V(G2) ={1,2, 3, 4, 5},E(G2) ={15,25, 14, 53, 54, 34}c) o długości4z wierzchołka2do3,V(G3) ={1,2, 3, 4, 5},E(G3) ={51,52, 13, 14, 43, 23, 23}d) o długości4z wierzchołka2do4,V(G4) ={1,2, 3, 4, 5},E(G4) ={12,15, 25, 36, 35, 56, 45}e) o długości3z wierzchołka4do5,V(G5) ={1,2, 3, 4, 5, 6},E(G5) ={12,25, 15, 14, 35, 34, 45, 24}Zadanie 4Wyznacz liczbę wszystkich drzew spinających dla grafu zdefiniowanego przez zbiór wierzchołków i krawędzi (zastosuj macie-rzowe twierdzenie o drzewach):a)V(G1) ={1,2, 3, 4, 5, 6},E(G1) ={13,14, 25, 26, 16, 24, 23}b)V(G2) ={1,2, 3, 4, 5, 6},E(G2) ={12,25, 16, 63, 14, 35, 15}c)V(G4) ={1,2, 3, 4, 5, 6},E(G3) ={13,63, 24, 15, 16, 65, 23, 34}d)V(G4) ={1,2, 3, 4, 5, 6, 7},E(G4) ={12,27, 13, 17, 16, 25, 54, 34, 65}e)V(G5) ={1,2, 3, 4, 5},E(G5) ={15,12, 13, 24, 23, 34}Zadanie 5Narysuj drzewo o podanym kodzie Pr¨fera:ua)8381183b)9787819c)8199243d)1238761e)2443215
[ Pobierz całość w formacie PDF ]