soc2

Soc 2

== include(page="template/taskheader" task_id="soc2") ==
Un grup de $N$ oameni de afaceri s-au antalnit cu ocazia unei conferinte. Unii dintre ei sunt dusmani, altii nu (de prietenie nu se prea pune problema cand este vorba de afaceri). Fiecare dintre ei are un cont in banca ce contine o anumita suma exprimata in euro. De fiecare data cand se intalnesc, se gandesc cum sa initieze o noua afacere. De data aceasta s-au decis sa infiinteze o societate, la care actionarii sa fie o parte dintre ei, astfel incat oricare doi oameni de afaceri care sunt actionari ai societatii sa nu fie dusmani, iar capitalul societatii (egal cu totalul sumelor din conturile actionarilor) sa fie maxim. Pentru a determina actionarii acestei societati, v-au angajat pe dumneavoastra si, daca le veti da raspunsul in timp util, veti fi recompensat cu o suma frumoasa.

Inainte de a va apuca de treaba, cei $N$ oameni de afaceri v-au pus la dispozitie informatii referitoare la conturile lor din banca si la relatiile de dusmanie dintre ei. Analizand problema, ati ajuns la concluzia ca relatiile de dusmanie pot fi reprezentate sub forma unui graf neorientat cu $N$ varfuri (corespunzatoare celor $N$ oameni de afaceri); intre doua varfuri diferite exista o muchie, daca cei doi oameni de afaceri corespunzatori celor doua varfuri din graf sunt dusmani (dusmania este reciproca). Graful are o structura speciala, mai exact el este un $graf cordal$. Un graf se numeste $graf cordal$ daca indeplineste una dintre urmatoarele $2$ conditii:

1.	Este un graf cu un singur nod.
2.	Se obtine inserand un nod nou $X$ intr-un graf cordal $G$, astfel: se alege o submultime de noduri din $G$, cu proprietatea ca exista muchie intre oricare doua noduri din submultime (submultimea poate contine si doar un singur nod), si se introduce cate o muchie intre nodul nou inserat $X$ si fiecare nod din submultime.

 
# Este un graf cu un singur nod.
# Se obtine inserand un nod nou $X$ intr-un graf cordal $G$, astfel: se alege o submultime de noduri din $G$, cu proprietatea ca exista muchie intre oricare doua noduri din submultime (submultimea poate contine si doar un singur nod), si se introduce cate o muchie intre nodul nou inserat $X$ si fiecare nod din submultime.

!problema/soc2?1.bmp!

== include(page="template/taskfooter" task_id="soc2") ==

1610