1. Co to jest permutacja? Ile jest permutacji zbioru n-elemntowego. Wygeneruj wszystkie permutacje zbioru 4-elementowego.

Permutacja - jest to ustawienie w ciągu h-wyrazowym zbioru n-elementowego

P=n! , P₄=4! = 1ּ2ּ3ּ4=24

P₄{1,2,3,4} {1 3 4 2} {1 4 3 2} {2 1 3 4}...

2. Co to jest kombinacja? Ile jest k-elem kombinacji zbioru n-elem. Wygeneruj wszystkie 2-elem kombinacje zbioru 5-elem.

Kombinacją - nazywamy każdy k-elem. zbiór n-elem.

3. Co to jest wariancja ? Ile jest k-elem. Wariancji bez powtórzeń zbioru n-elem a ile jest z powtórzeniami?

Wariancją k-elem z powtórzeniami zbioru n-elem nazywamy każdy ciąg k-wyrazowy tego zbioru

4. Algorytm generowania wszystkich podzbiorów zbioru. Zastosuj dla dowolnego zbioru 4-elem.

G (n ; k) = G (n _-1, k) , G( n _-1, k _-1)∪{n}

[n-1] = {1,2,............n-₁}

[n] = {1,2,............n-₁, n}

[n-1] + [n]

Zastosowanie;

n=4 k=2

G (4,2)= G(3,2) , G(3,1)∪{4}

G (3,1)= {1}; {2}; {3}

G (3,2)= G(2,2) , G(2,1)∪{3}

G (2,2)= {1,2}

G (2,1)= {1}; {2}

G (2,1)∪(4)= {1,3}; {2,3}

G (4,2)= {1,2} {1,3} {2,3} {1,4} {2,4} {3,4}

5. Podział zbioru 5-elem na 2 bloki.

Podziałem zbioru X na K-bloków nazywamy rodzinę zbiorów B_1, B₂....B_n taką, że

• 
  Ø X={1,2,3,4,5}

{12} {3 4 5} {34} {1 2 5}

• B_i∪B_j=Ř {13} {2 4 5} {35} {1 2 4}

• 
  =Ř {14} {2 3 5} {45} {1 2 3}

zbiory B_i....B_n nazywamy blokami {15} {2 3 4}

{23} {1 4 5} {2} {1 3 4 5}

{24} {1 3 5} {3} {1 2 4 5}

{25} {1 3 4} {4} {1 2 3 5}

6. Co to jest liczba STERLINGA drugiego rodzaju. Ile wynosi S{4.1}

X-Zbiór

Π(x)-zbiór wszystkich podziałów zbioru X

Π K(x)-zbiór wszystkich podzbiorów na K bloków zbioru X

Liczba wszystkich podziałów zbioru na K-elementów przy podziale zbioru nie elementowego

S(n,1)=1

S (n,k) = ‌ Π K([n])‌ nazywamy liczbą Stelinga VI rodzaju S(n,0)=0

S(n,n)+1

n(n,n)=0 k>n

Wzór rekurencyjny; S(n,k) = S(n _-1, k _-1) + kS(n _-1, k) S(1,0)=0

S(4,1)=1

S(5,2)=3(4,1) = 2S(4,2)= 1+2·7=15

S(4,2)=3(3,1) = 2S(3,2)= 1+2·3=7

S(3,2)=3(2,1) = 2S(2,2)= 1+2·1=3

7. Co to jest liczba BELLA? Znajdź wszystkie podziały zbioru 4-elementowego.

Bn-liczba wszystkich podziałów zbioru n-elem dla n≥1

Tw; liczba Bella

n+1= 4

B₁=B₃₊₁=

n= 3

B₃=B₂₊₁=

n= 2

B₃=B₁₊₁=

8. Co to jest funkcja tworząca dla ciągu a_n=n dla n≥0

-funkcja tworząca

Załóżmy, że szereg formalny
określa pewną funkcję zwaną funkcją ciągu

Znajdowanie funkcji tworzących dla ciągu:

1. 
   
   

2. 
   
   

3. 
   ,
   

4. m-ustalona liczba naturalna

9. Podaj definicję ciągu FIBONACCIEGO.

Fn-ciąg Fibonacciego

F₀=0 F_n=F_{n -1}+F_{n -2}

10. Jak rozwiązujemy równanie rekurencyjne przy pomocy funkcji tworzących? Ile wynosi n-ta liczba w ciągu danym równaniem
    dla n≥1
    

1. Piszemy równanie rekurencyjne ciągu
   

2. Tworzymy szereg potęgowy
   i wyznaczamy tworzącą A(x) dla ciągu
   z równania otrzymanego przez wstawienie w miejsce
   funkcji n A(x)=H(x)

3. Rozwijamy A(x) w szereg potęgowy. Współczynnik przy xⁿ w tym szeregu równy
   

11. Jak rozwiązujemy równanie rekurencyjne postaci a _n =A a _n+ B a _{n -1} dla n ≥2 przy danych a₀ , a₁ dla dowolnych stałych A, B. Ile wynosi n -ta liczba w ciągu danym równaniem a _n= a _{n -1}+2 a _{n -2} dla n ≥2 oraz a₀=1 , a₁=2

12. Zasada włączania i wyłączania dla 3 zbiorów. Wśród 100 studentów 15 lubi matematykę dyskretną, 90 lubi metody numeryczne a 80 spośród nich nie lubi matematyki dyskretnej. Ilu jest studentów którzy lubią matematykę dyskretną lub metody numeryczne

│A∪B∪C│=│A│+│B│+│C│-│A∩B│-│A∩C│-│B∩C│+│A∩B∩C│

13. Co to jest nieporządek? W przybliżeniu co która permutacja jest nieporządkiem?

Permutacją f:
nazywamy nieporządkiem jeśli

Ze zbioru n-elem przyporządkowujemy liczbę drugiego zbioru n element, ale musi to być inna liczba

Przykład;

B[1, 2, 3] [1, 2, 3]

[3, 2, 1] [2, 3, 1] S _n = n!

^{nie jest jest}

^{nieporządkiem nieporządkiem}

14. Co to jest graf; Kiedy dwa grafy nazywamy izomorficznymi

Grafem prostym nie skierowanym (nie zorientowanym) nazywamy parę uporządkowaną G∈(V,E), gdzie V jest zbiorem wierzchołków a E ≤ P _z (v) jest zbiorem krawędzi (nieuporządkowanych par wierzchołków)

↑_{rodzina wszystkich podziałów 2-elementowych zbioru V}

Grafem prostym skierowanym nazywamy parę G(V,E), gdzie V jest zbiorem wierzchołków, a E ≤ V x V jest zbiorem krawędzi (łuków) uporządkowanych par wierzchołków.

Grafy G₁ i G₂ są izomorficzne (G₁ ≅ G₂), jeśli istnieje funkcja φ;V(G₁)
V(G₂) taka, że krawędź UVE E(G₁)<=>d(n) ø (V)∈ E(G₂)

Dwa grafy G₁ G₂można nazywać izomorficznymi jeśli

• można je narysować w ten sam sposób,

• mają identyczne zbiory rysunków.

15. Jakie znasz rodzaje podgrafów grafów? Omów je na przykładzie.

Graf H jest podgrafem grafu G, jeśli V(H) ≤ V(G) oraz E(H) ≤ (G)

Niech G=(V,E)- graf V'≤V

Podgraf H=(V', E∩P _z ( V ^z ) ) nazywamy podgrafem indukowanym przez zbiór wierzchołków V

Podgraf H grafu G, którego zbiorem krawędzi jest E, a zbiór wierzchołków jest zbiorem końców krawędzi z E' nazywamy podgrafem indukowanym w G przez zbiór krawędzi E.

V'={a, b, g, h} E'={ab, cd, bc, dh}

Paragraf indukowany grafem V' podgraf indukowany E'

16. Droga i cykl w grafie. Czy droga i cykl są grafami spójnymi?

Graf o wierzchołkach V₀, V₁......V_n parami różnych krawędziach (dla i=2....n) E= V_{i -1}-V_i nazywamy drogą o n-wierzchołkach i oznaczamy przez P_n

Graf powstały z drogi V o wierzchołkach V₀, V₁......V_n i krawędziach E _i = V_{i -1}-V_i lecz dodatniej krawędzi V_nV₁ nazywamy cyklem o n-wierzchołkach i nazywamy C _n

Graf jest spójny jeśli dla każdej pary wierzchołków V∈V(G) istnieje droga miedzy nimi.

17. Co to jest stopień wierzchołka? Czy suma wierzchołków może wynosić 13. Odpowiedz uzasadnij:

Stopniem wierzchołka V w grafie G V€V(G) nazywamy liczbę krawędzi wychodzących z V (=l. sąsiadów wierzchołka V) przy założeniu że jest co najwyżej jedna krawędź miedzy parą wierzchołków. Oznaczamy

18. jaki graf nazywamy spójnym? Narysuj przykład grafu spójnego i przykład grafu niespójnego. Co to jest składowa spójności?

Graf spójny: jeśli dla każdej pary wierzchołków x,y€V(G) istnieje droga xy w G

Składowe spójności grafu G Nazywamy

maksymalny podgraf wspólny grafu G.

19. Jaki graf nazywamy drzewem? Czy droga jest drzewem? Czy cykl jest drzewem? Jaki Graf nazywamy lasem?

Lasem nazywamy graf, który nie zawiera cyklu. (acykliczny)

Drzewem nazywamy spójny graf, który nie zawiera cyklu

Każdy graf acykliczny i spójny nazywamy drzewem

Czy droga jest drzewem? Tak droga nie zawiera cyklu.

Czy cykl jest drzewem? NIE drzewo jest grafem acyklicznym.

20. Jakie znasz właściwości grafów nazywanych drzewami? Co to jest liść? Czy drzewo może mieć jeden liśc? Co to jest most w grafie?

1. Dla dowolnych dwóch wierzchołków UV w drzewie T istnieje dokładnie jedna droga łącząca je!

2. Graf T jest drzewem każda krawędź w T jest mostem

3. Jeżeli T jest drzewem
   gdzie T= moc; g(T) l. krawędzi.

4. Każdy graf spójny G ma podgraf rozpierający będący drzewem ( drzewo rozpierające grafu G)

5) Jeśli T jest drzewem rozpierającym grafu G oraz E jest krawędzią grafu G spoza T +o T+E zawiera cykl

Liściem w drzewie nazywamy każdy wierzchołek stopnia 1

21. Problem ……. Drzewa rozpinającego> podaj przykłady zastosowania.

G=(V,E) - graf niekierowany.

w E (0,+∞) - funkcja wag krawędzi.

Szukane: podgraf rozpinający, spójny o minimalnej sumie wag krawędzi.( minimalne drzewo rozpierające)

Niech F będzie drzewem rozpinającym Grafu G, zaś o krawędzi należącej do „e” lecz nie należącej do T. Wtedy T+e ma dokładnie 1 cykl.

Przykład: Sieć połączeń kolejowych pomiędzy danymi miastami w taki sposób, aby można było odbyć podróz pomiędzy dowolną para miast.

22. Algorytm Kruskala. Omów na przykładznie!

1. Wybierz krawędź o minimalnej wadze.

2. Jeśli wybrano już krawędzie e1, e2,… ei to wybierz krawędź ei+1 spośród pozostałych krawędzi (tzn. ze zbioru E(G)\{e1,..ei} tak aby:

*Graf G ({e1,… ei, ei+1}) nie zawierał cykli

** ei+1 jest krawędzią o najmniejszej wadze spośród tych, które spełniają *

3. stop jeśli krok 2 jest niewykonalny

TW. Algorytm Kruskala znajduje normalne drzewko rozpinające dowolnego grafu G

23 Algorytm przeszukiwania grafu w szerz. Omów na przykładzie!

k- kolejka

Dany jest Graf G V(G)={V1,…Vn)

1. pomaluj na biało wszystkie wierzchołki

2. dla i= 1…n wykonaj pkt. 3

3. Vi jest biały?

Jeśli tak to pomaluj na czarno i połóż na koniec kolejki wykonaj 4-5

1. Czy któryś z sąsiadów wierzchołka z początku kolejki jest biały.?

Jeśli TAK to pomaluj na czarno i połóż na koniec kolejki i wróć do pkt. 4

Jeśli NIE, to usuń wierzchołek z początku kolejki

2. Czy kolejka Z jest pusta?

Jeśli Nie to wróć do 4

Kolejność odwiedzania:

• Algorytm przeszukania grafu w głąb omów na przykładzie:

1. pomaluj na biało wszystkie wierzchołki

2. dla i=1…,n wykonaj pkt. 3

3. Jeśli Vi jest biały?

Jeśli Tak to połóż go na szczyt stosu s i wykonaj 4, 5

4. czy któryś z sąsiadów wierzchołka ze szczytu stosu s jest biały?

Jeśli TAK, to pomaluj go na czarno i połóż na szczyt i wróc do 4

Jeśli NIE to usuń wierzchołek ze szczytu stosu s

5. Jeśli stos s jest pusty?

Jeśli NIE to wróć do 4

Kolejnośc odwiedzania: V1, V2, V3, V4, V9, V8, V7, V6, V5, V10

• Co to jest cykl Eklera w grafie i kiedy istnieje? Podaj przykład grafu, który nie posiada cyklu Eulera!

Cyklem Eulera w Grafie nazywamy ścieżkę
taką ze każda krawędzi grafu występuje na tej ścieżce dokładnie raz. Jeśli Vo=Vn to taką ścieżkę nazywamy ścieżką eulera.

Tw. Eulera: Graf spójny G ma ma cykl eulera gdy wszystkie wierzchołki grafu G Są parzystego stopnia

PRZYKŁAD

26. ???/

Dany jest Graf G z wagami krawędzi (tzn. W:E(G) (0; +∞)

Problem:

Znaleźć linię zamkniętą przechodzącą przez każdą krawędź co najmniej raz o możliwie najmniejszej sumie wag krawędzi.

Jeśli graf ma cykl eklera to dowolny cykl Eklera jest rozwiązaniem tego problemu.

Jeśli G nie zawiera cykle Eklera to tworzymy multigraf zawierający cykl Eklera (wszystkie wierzchołki parzystego stopnia)

27. Algorytm Fleury'ego.

Graf G posiadający cykl Eklera:

1. wybierz dowolny wierzchołek (Vo)

i niech Wo=Vo

2) Przypuśćmy, że ściana
jest już skonstruowana wybieramy krawędź
spośród dotąd nie wybranych tak aby:

*
była incydentalna z

** jeśli tylko jest wybór to wybierz
, która nie jest mostem w grafie. G\{
}

3. Stop jeśli krok 2 nie da się wykonać

PRZYKŁAD

28) Co to jest cykl Hamiltona. Warunek konieczny istnienia cyklu Hamiltona

Tw. Cykl, który zawiera wszystkie wierzchołki grafu nazywamy cyklem Hamiltona.

Drogę, która zawiera wszystkie wierzchołki Grafu nazywamy drogą Hamiltona.

Posiada cykl i drogę Hamiltona

posiada drogę Haliltona

nie posiada cyklu

Nie posiada drogi i cyklu Hamiltona

Warunek konieczny istnienia cylku Hamiltona

Jeśli G ma cykl Hamiltona to dla każdego

gdzie
liczba składowych grafów G\S

MATEMATYKA DYSKRETNA -PYTANIA I ODPOWIEDZI 2005

1

Graf nie wspólny

Graf wspólny

G

Drzewo rozpierające grafu G

4

2

3

1

5

6

1

2

3

4

5

6

7

8

9

10

V10

V9

V8

V7

V6

V5

V4

V3

V2

V1

V10

V9

V8

V7

V6

V5

V4

V3

V2

V1

150

100

200

100

500

450

400

---