Fie G = (V, E) un digraf aciclic; dou˘a noduri u ¸si v din V sunt numite adversare dac˘a nu
exist˘a niciun drum direct ˆın G care s˘a cont¸in˘a ambele noduri u ¸si v. O mult¸ime W ⊆ V se nume¸ste
adversitate dac˘a orice dou˘a noduri distincte din W sunt adversare.
Acoperirea prieteneasc˘a a lui G este un digraf G0 astfel ca V (G0
) = V ¸si pentru orice dou˘a
noduri distincte x ¸si y din V , xy ∈ E(G0
) dac˘a exist˘a ˆın G un drum direct de la x la y.
(a) Demonstrat¸i c˘a acoperirea prieteneasc˘a a unui digraf aciclic este tot un digraf aciclic.
(b) Ar˘atat¸i c˘a o submult¸ime de noduri S ⊆ V este stabil˘a ˆın G0 dac˘a ¸si numai dac˘a este o adversitate
ˆın G.
(c) Ar˘atat¸i c˘a un ¸sir de noduri x1, x2, . . . , xp din V formeaz˘a un drum direct simplu ˆın G0 dac˘a ¸si
numai dac˘a nodurile se reg˘asesc (ˆın aceast˘a ordine, dar nu neap˘arat consecutive) pe un drum
direct simplu din G.
(d) Demonstrat¸i c˘a G0 poate fi partit¸ionat ˆın cel mult s drumuri disjuncte pe noduri dac˘a ¸si numai
dac˘a G poate fi acoperit cu cel mult s drumuri.
(