Probleme

Considerăm $G$ un graf neorientat cu $2026$ de noduri și $2000$ de muchii. Fie $m$ numărul minim de componente conexe și $M$ numărul maxim de componente conexe pentru un graf cu proprietățile lui $G$. Ce valoare are $M-m$?

a) $1925$; b) nu se poate calcula; c) $63$; d) $1937$; e) $199$; f) $1999$.

Considerăm un graf neorientat complet cu nodurile $\{1,2,\dots,10\}$. Alegem exact $9$ muchii astfel încât subgraful format are următoarele proprietăți: (1) este conex; (2) nu conține niciun ciclu; și (3) nodurile $1$, $2$, $3$ și $4$ au gradul $1$ în subgraful format. Câte astfel de alegeri distincte putem face pentru ca subgraful rezultat să îndeplinească toate cele trei condiții?

a) $6^8$; b) $4!\cdot 6^4$; c) $10^8$; d) $7^8$; e) $10\cdot 6^7$; f) $6^7$.

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.

În câte moduri se poate colora următorul graf neorientat folosind 4 culori astfel încât 2 noduri adiacente să nu aibă aceeași culoare? [Figura: graf cu 8 noduri — patru noduri în colțurile unui pătrat exterior și patru noduri în colțurile unui pătrat interior. Muchii: cele 4 laturi ale pătratului exterior, cele 4 laturi ale pătratului interior, cele 4 muchii care leagă fiecare colț exterior de colțul interior corespunzător și cele 2 diagonale ale pătratului interior (X-ul din centru). În total 14 muchii.]

a) 288; b) 696; c) 625; d) 24!; e) 120; f) 24.

Un graf de tip scară are 2n noduri și este reprezentat ca în figură. [Figura: graf „scară" — nodurile x1,…,xn pe un rând, y1,…,yn pe rândul de jos; muchii: xi—x(i+1), yi—y(i+1) pentru 1≤i<n și xi—yi pentru 1≤i≤n.] Dacă n=11, în câte moduri putem alege n dintre muchiile acestuia, astfel încât oricare două dintre ele să nu aibă capete comune?

a) 377; b) 55; c) 75; d) 98; e) 144; f) 110.

Fie un arbore cu 10 noduri, numerotate de la 1 la 10 și vectorul său de tați v={0,1,1,2,2,3,3,x,y,z}. Câți vectori de tați valizi și distincți se pot forma dând valori lui x, y și z?

a) 700; b) 567; c) 720; d) 686; e) 729; f) 648.

Fie un graf neorientat cu $n$ noduri, numerotate de la $1$ la $n$. Există muchie între $i$ și $j$ dacă și numai dacă $j$ divide pe $i$ ($1\le i\le n$, $1<j<i$). Câte componente conexe are graful pentru $n=50$?

a) $8$; b) $6$; c) $5$; d) $7$; e) $2$; f) $1$.

Fie un graf neorientat cu $n$ vârfuri, pe care vrem să le împărțim în 3 mulțimi disjuncte nenule (dacă $V$ este mulțimea vârfurilor, fie $V_1, V_2, V_3$ cele trei mulțimi disjuncte, $V_1\subset V$, $V_2\subset V$, $V_3\subset V$, $V_1\cap V_2=\emptyset$, $V_1\cap V_3=\emptyset$, $V_2\cap V_3=\emptyset$). Știind că vârfurile din aceeași mulțime nu pot avea muchii între ele, care este numărul maxim de grafuri care se pot construi respectând aceste condiții pentru $n=2022$?

a) $2^{4088484}$; b) $2^{681414}$; c) $2^{2043231}$; d) $2^{1362828}$; e) $2^{4086462}$; f) $2^{2022}$.

Fie un graf neorientat oarecare și o submulțime de $k$ noduri ($k\ge 1$) ale acestuia. Nodurile acestei submulțimi au gradele $2^0, 2^1, \ldots, 2^{k-1}$. Toate celelalte noduri din graf sunt legate la cel puțin un nod din această submulțime. Care este numărul minim, respectiv maxim, de noduri pe care le poate avea graful, în funcție de $k$.

a) $\min=2^{k-1}+1$, $\max=2^k+k-1$; b) $\min=k$, $\max=2^k-1$; c) $\min=k+1$, $\max=2^k+k-1$; d) $\min=2^{k-1}+1$, $\max=2^{k-1}+1$; e) $\min=2^{k-1}$, $\max=2^k+k$; f) $\min=k+2$, $\max=2^{k+1}$.

Fie un arbore cu următoarele proprietăți. Fiecare nod intern (un nod intern este orice nod care nu este o frunză) are 3 copii. Toate nivelurile arborelui sunt pline cu noduri, mai puțin ultimul, unde frunzele completează nivelul de la stânga la dreapta. Care e numărul minim, respectiv maxim, de noduri pe care le poate avea un astfel de arbore dacă înălțimea acestuia este $h$, considerând că rădăcina are nivelul $0$ și $h\ge 2$?

a) $\frac{1}{2}(3^h-1)+3$, $\frac{1}{2}(3^{h+1}-1)$; b) $3^h+3$, $3^{h+1}-1$; c) $3^h+2$, $3^{h+1}-1$; d) $\frac{1}{2}(3^h-1)+2$, $\frac{1}{2}(3^{h+1}-1)$; e) $\frac{1}{2}(3^h-1)+1$, $\frac{1}{2}(3^{h+1}-1)$; f) $3^h+1$, $3^{h+1}-1$.