Ma poate ajuta cineva la niste probleme cu grafuri?

UNA DIN ELE AR FI ASTA:

Problema 3. Fie F = {F1, . . . , Fn} o multime de submultimi nevide ale
unei multimi finite S ( ∀i = j Fi = Fj). Notam cu G∩(F) graful cu multimea
de varfuri F si ın care FiFj este muchie daca ¸si numai daca Fi ∩ Fj = ∅.

a) Demonstrati ca pentru orice graf G de ordin n exista S ¸si F o multime de
n submultimi ale lui S astfel ıncat G = G∩(F).
Aratati ca numarul minim de elemente ale unei multimi S, din care se pot
extrage 16 submultimi F = {F1, . . . , F16} astfel ca G∩(F) = K16, este 5.

SI CEALALTA:

Problema 2. Pentru un graf oarecare G = (V,E) definim gradul mediu
ca fiind δmed(G) = 1
|V |
v∈V dG(v) ¸si dorim sa calculam
Δmed(G) =max∅=S⊆V δmed([S]G).
Consideram urmatoarea euristica pentru determinarea lui Δmed(G):

1. D← δmed(G);
2. for i = 1 to |V | − 2 do {
fie v varful de grad minim din G
G ← G − v
if D <δmed(G) then D ← δmed(G);
} 3. return D

a) Demonstrati ca valoarea returnata, D, satisface: D ≥ 1
2Δmed(G).
Indicati structurile de date ¸si modul de folosire a acestora pentru o implementare
a algoritmului de mai sus ın timpul O(n + m), unde n = |V | ¸si
m = |E|.

Edited by sacalu007, 27 October 2006 - 11:19.