Question

. Fie G = (V, E) un graf conex ¸si U = (U1, U2, . . . , Up) o partit¸ie de cardinal p a lui V , o U-muchie este o muchie uv ∈ E astfel ˆıncˆat u ∈ Ui
, v ∈ Uj ¸si i != j.
(a) Fie T un arbore part¸ial al lui G; ar˘atat¸i c˘a T cont¸ine cel put¸in (p − 1) U-muchii.
(b) Ar˘atat¸i c˘a dac˘a G are s arbori part¸iali disjunct¸i pe muchii, atunci exist˘a cel put¸in s(p − 1) U-muchii.

Answer 1

Răspuns:

Ok deci pe asta o stiu ca am fost si eu la facultate candva.

Explicație:

Deci pentru ca G sa fie un graf conex mai intai trebuia ca graful G sa fie conex. Partitiile U1 U2.....Up.lm stim ca apartin lui E.

a) T contine cel putin (p-1) U muchii

b) G are arbori partiali disjuncti pe muchii deci da

Vreau funda multumesc! pwp