1. Fie G = (S,T;E) un graf bipartit. G se numeşte o-bipartit dacă dc(x) = a\;(y) pentru orice doua noduri :r şi y din aceeaşi clasă a bipartiţiei.

(a) Arătaţi că într-un graf a-bipartit exisă un cuplaj care saturează una din cele două clase ale bipartiţiei.

(b) Doi prieteni interpretează următorul joc de cărţi: primul dintre ei alege la întâmplare şase cărţi dintr-un pachet (de 52) de cărţi, se uită la ele. păstrează una dintre ele iar pe celelalte cinci le aşează cu faţa în sus ordonate de la stânga la dreapta; al doilea prieten ghiceşte corect cartea păstrată de primul. Arătaţi că cei doi prieteni se pot înţelege asupra unui sistem care să funcţioneze întotdeauna şi determinaţi un astfel de sistem.

(2 + 2 = 4 points)

2. lntr-o reţea de computere există doua tipuri de noduri; clienţi şi servere. Fiecare client este ■otiectat direct (folosind cabluri) la cel puţin un server dar nu există conexiuni direcţii' intre clienţi, 'rcsupsuiem ca fiecare server poate ruta (trimite) mesaje către serverele eu care este direct: conectat i ci reţeaua este conexa (oricare doua noduri pot comunica). Pentru a face reţeaua iutii fiabilă sunt uaie m considerare doua scenarii: