Question

Va rog doar cine stie

Answer 1

1. Prin ce tip de graf va fi reprezentat un grup de persoane intre care s-au stabilit relatii de vecinatate ?

Printr-un graf neorientat.

2.  In G1

a) Cu ce noduri este adiacent nodul 1 ?

Nodul 1 este adiacent cu nodurile 2,3,4.

b) cu ce muchii este incident nodul 1 ?

Nodul 1 este incident cu muchiile {1,2}, {1,3}, {1,4}

c) Dati exemple de doua noduri adiacente si de doua noduri care nu sunt adiacente.

Noduri adicente: 2 si 5

Noduri care nu sunt adiacente: 3 si 6

d) Dati exemple de două muchii incidente și două muchii care nu sunt

Muchii adiacente: {1,3} si {3,5}

Muchii care nu sunt adiacente: {4,3} si {6,7}

3. Fiind date n persoane și m relații de prietenie între ele de forma: persoana i este prietenă cu persoana j, se cere să se stabilească corespondența între afirmațiile din stânga și cele din dreapta.

1. În grupul celor n persoane, fiecare persoană are cel puțin un prieten.

d) Graful asociat nu are noduri izolate.

2. Fiecare persoană este prietenă cu oricare alta din grup.

c) Graful asociat este complet.

3. Există persoane care nu au decât un singur prieten.

a) Graful asociat are noduri terminale

4. Exista k persoane din grup astfel încât oricare dintre ele este prietenă cu toate celelalte k-1.

b) Graful asociat contine un subgraf complet cu k noduri.

4. Numarul de grafuri neorientate cu n vârfuri este: c) $2^{\frac{n(n-1)}{2} }$

Teorie:

Se numeşte graf(G) o pereche ordonată de mulţimi (X,U), unde X este o mulţime finită şi nevidă iar U o mulţime de perechi formate cu elemente distincte din mulţimea X(familie de submulţumi cu două elemente din mulţimea X.

Graf neorientat: Un graf G=(X,U) este neorientat dacă mulţimea U este formată din perechi neordonate {xi,xj}.

Noduri adiacente: Orice pereche de noduri care formează o muchie-{xi,xj} є U. Fiecare nod al muchiei este incident  cu muchia [xi,xj].

Nodurile vecine unui nod xi sunt toate nodurile xj care sunt adiacente cu el.

Muchiile incidente- două muchii Ui şi Uj care au o extremitate comună.

Nodul terminal –are gradul=1 ; d(xk)=1.

Subgraful: Fie graful G=(X,U).Graful Gs=(Y,V) se numeşte subgraf al grafului G dacă Y   X şi V conţine toate muchiile din U care au ambele extremităţi în mulţimea de noduri  Y.  Un subgraf se obţine chiar din graful însuşi sau prin eminarea de noduri şi a tuturor muchiilor(arcelor) incidente cu aceste noduri.

Graful complet este un graf în care oricare ar fi două noduri ale grafului ele sunt adiacente.El se notează cu Kn.

Nodul izolat are d(xk)=0.

Acestea sunt exercitiile rezolvate. Am atasat si teoria, ar fi bine sa o stii; sunt niste informatii usor de retinut si vei reusi sa faci repede astfel de exercitii.