Zad. 3 Zasada włączania i wyłączania Dla zbiorów skończonych {A1, …, An} zachodzi|A₁ υ … υ A_n| = ∑_{I ε {1, … , n}} (-1)^|I|+1 |∩_{i ε I} A_i|= |A₁| + … + |A_n| - |A₁ ∩ A₂| - |A₁ ∩ A₃| - … - |A_n-2 ∩ A_n| - |A_n-1 ∩ A_n|+ |A₁ ∩ A₂ ∩ A₃| + …+ |A_n-2 ∩ A_n-1 ∩ A_n| - |A₁ ∩ A₂ ∩ A₃ ∩ A₄| - … - |A_n-3 ∩ A_n-2 ∩ A_n-1 ∩ A_n|+ …(-1) ⁿ⁺¹ |A₁ ∩ … ∩ A_n|

Zad 10 : Chyba z tego :

Zbiór potęgowy (czyli zbiór podzbiorów) zbioru X oznaczamy przez P(X).

Przykład. P(pusty_zbiór) = {pusty zbiór} i |P(pusty_zbiór)|= 1

P({pusty_zbiór})={ pusty_zbiór, { pusty_zbiór} i |P({pusty_zbiór})|=2

P({a,b}) = {pusty_zbiór, {a}, {b}, {a,b}}

P({a,b,c}) = {pusty_zbiór, {a}, {b}, {c}, {a,b}, {a,c},{b,c},{a,b,c}}

Ogólna sytuacja Niech p_n oznacza liczbę podzbiorów zbioru n-elementowego.

Wówczas p_n =2ⁿ. Uzasadnienie. Znamy liczbę p_n i chcemy policzyć p_{n +1.}

Niech zbiór Z ma n+1 elementów. Jeżeli a ε Z, to Z'=Z\{a}.

Podzbiory zbioru Z można podzielic na dwa elementy: (a) mające w sobie element a (b) nie mające w sobie element a W drugim przypadku są to podzbiory zbioru Z'. Jest więc ich dokładnie p_n

Każdy zaś podzbiór pierwszego typu (czyli A zawarte w Z, takie, że a ε A) jest jednoznacznie wyznaczony przez swoje pozostałe elementy (tzn. elementy różne od a). A zatem każdy taki zbiór A (że a ε A zawartego w Z) jest postaci A' υ {a} dla pewnego A' zawartego w Z'. A zatem podzbiorów zbioru Z, w których jest element a, jest też tyle ile podzbiorów zbioru Z', tzn. p_n.

Łacznie więc zbiór Z ma p_n + p_n podzbiorów czyli p_n+1= 2* pn. Teraz już można stwierdzić, że to wraz z warunkiem p_n=1 jest spełnione przez p_n =2ⁿ.

Dla dowolnego skończonego zbioru X mamy |P(X)|= 2^|X|.

Zad 11. Chyba o to chodzi : (G = < V, E >, G1 = < V1, E1 >, G2 = < V2, E2 > )

• suma grafów: G1 υ G2 = < V1 υ V2, E1 υ E2 >

• przecięcie grafów: G1 ∩ G2 = < V1 ∩ V2, E1 ∩ E2 >

• różnica grafów: G1 \ G2 = < V1 \ V2, E1 \ E2 >

• podgraf grafu G to graf H taki, że V(H) zawiera się w V(G) i E(H) zawiera się w E(G)

• restrykcja grafu G do podzbioru X zawartego w V, to G|X =< X, {{v,w}: v,w ε X }>

• podgraf indukowany grafu G to graf będący restrykcją grafu G

Zad. 12 TW.Graf G jest eulerowski wtw gdy jest spójny i stopień każdego wierzchołka jest parzysty

Zad. 13 a,b,c wszystkie poprawne (chyba) bo :

Podstawowe operacje na kolejkach

(q = (e₁,e₂,...,e_n))

• first(q) = e₁ – pobieranie pierwszego elementu z kolejki

• in(q,e) = (e₁,e₂,...,e_n,e)- wprowadzenie elementu na koniec kolejki

• out(q) = (e₂,...,e_n) gdy n>0 - usuniecie elementu z czoła kolejki

• empty(q) wtw n=0– służy do sprawdzania czy kolejka jest pusta

Czy prawda:

not empty(q) → in(e,out(q))=out(in(e,q)) ? (+)

first(q)=e → out(in(e,q))=q ?

(not empty(q) and first(q)=e → in(e,out(q))=q ?