Probleme

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$.