3545336453

b.    a„ = (1 +n)(5)"⁺¹ dla n > 0;

c.    a„ = (1 + 2n)2ⁿ + 3 dla n > 0;

d.    a_n = —Zn² + 8ra + 4 dla n > 0.

7.1.    (uwaga dodane podpunkty) nieizomorficzne: a,b,c,d; izomorficzne: e,f.

7.2.    a) 5040 b) 360 c) 9!/2 d) 3360

7.5.

(i)    (3^ft + (—l)^ft+1)/4

(ii)    3^fc_1 dla k parzystych, 0 dla pozostałych k

(iii)    3^fc_1 dla k nieparzystych, 0 dla pozostałych k

7.6.    a) u(G) = 1 b) 2 < w(G^c) < 8

w przypadku dodatkowego pytania odpowiedź się nie zmieni.

7.7.    a)14 b)2 cykle i jedna ścieżka c)jest ich 6 d) Cs z przekątną e) 42

7.8.    wsk: zasada szufladkowa

8.2.    Jest ich 5.

8.3.    a) (uwaga - zmiana rysunku) 7⁵5³ b) 81

8.4.    a) (uwaga - zmiana ciągu) (“)(?) sife b) (\²) (Y) ('f) ₄i₂iili\iiii

8.5.    250

9.3.    NIE. Nie zapomnij o uzasadnieniu.

9.4.    NIE. Nie zapomnij o kontrprzykładzie.

10.1. .

W WP

BFS    DFS

10.2. wierzchołki: kwadraty,

krawędzie między kwadratami między którymi można „przejść”.

zastosuj DFS na wyżej opisanym grafie, zaczynając od wierzchołka (kwadratu) z literką X.

10.4.    ścieżka z a do b: agcb, waga: 17, w(a,g) = 7,w(g,c) = 8,w(6,c) = 2 ścieżka z a do d: aid, waga: 3, w(a,i)=2, w(i,d)=l

10.6. ścieżka: adebc, waga: 23

11.1.    a) 3 b) 3 c) 2 d) 4 e) 3 f) 3 g) 3

11.2.    a) nie - izomorficzny z

b)    tak

c)    nie - zawiera podział K$

d)    tak

e)    nie - zawiera podział Kz$

f)    nie - zawiera podgraf izomorficzny z K^,?,

g)    nie - zawiera podział #3,3

h)    tak

11.4.    6

11.5.    12

najmniej 3 wierzchołkach bez cykly długości 3 powinien spełniać

11.6.    NIE - spójny prosty graf planarny nierówność e < 2v — 4.