Probleme

Fie următoarea afirmație: „Orice graf pentru care 2 este numărul minim de culori este un graf bipartit sau este un graf eulerian.”; unde numărul minim de culori al unui graf reprezintă numărul cel mai mic de culori necesare pentru a colora vârfurile grafului astfel încât două vârfuri adiacente să nu aibă aceeași culoare. Câte dintre următoarele grafuri reprezintă un contra-exemplu pentru această afirmație?

[Graf 1: noduri D, A, B, C; muchii D—A, D—B, D—C, A—B, A—C, B—C.]

[Graf 2: noduri A, B, C, D, E, F; muchii A—B, A—D, B—C, C—D, D—E, C—E; nodul F este izolat (fără muchii).]

[Graf 3: noduri A, B, C; muchii A—B, A—C, B—C.]

[Graf 4: noduri A, B, C, D, E, F; muchii A—D, A—E, B—D, B—E, B—F, C—E, C—F.]

[Graf 5: noduri A, B, C, F, G; muchii A—B, A—C, C—F, C—G.]

a) 5; b) 0; c) 3; d) 2; e) 4; f) 1.

Considerăm șirul lui Fibonacci unde $fib(0)=0$, $fib(1)=1$ și $fib(k)=fib(k-1)+fib(k-2)$, pentru orice $k>1$, natural. Se construiește un arbore definit în funcție de numărul de nivele, rădăcina se află pe nivelul 1, și fiecare nod de pe nivelul $h$ are $fib(h+2)$ copii. Calculăm $N$ ca fiind numărul de noduri pentru un astfel de arbore cu 10 nivele. Pentru că numărul $N$ este destul de mare, se cere $N \bmod 13$ (restul împărțirii lui $N$ la 13).

a) 7; b) 3; c) 8; d) 4; e) 11; f) 6.