Problema 4

Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60],[60,20], [2,30] şi [4,30]. Numărul componentelor conexe ale grafului este egal cu:

a. 24 b.26  c . 54 d. 0

Raspuns : b.26

Problema 3

     Un graf neorientat este complet dacă oricare două noduri distincte ale sale sunt adiacente.Care este numărul de muchii care trebuie eliminate dintr-un graf neorientat, complet, cu 7 oduri, astfel încât graful parţial obţinut să fie arbore? 
 

a.      15 b. 1 c. 6 d. 21

Raspuns : a.15

Problema 2

 Se consideră un graf neorientat cu 5 noduri, etichetate cu câte o literă distinctă din

mulţimea {a, b, c, d, e}, în care orice nod etichetat cu o vocală este adiacent cu toate

nodurile etichetate cu consoane şi numai cu acestea, iar orice nod etichetat cu o consoană

este adiacent numai cu nodurile etichetate cu vocale. 

Câte muchii are acest graf?  

a.12 ; b. 6 ;  c. 4 ; d. 3

Raspuns : b.6

Problema 1

Se consideră graful neorientat definit prin mulţimea vârfurilor {1,2,3,4,5,6} şi mulţimea

muchiilor {[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]}.

Care este numărul minim de muchii ce pot fi eliminate şi care sunt aceste muchii astfel

încât graful parţial obţinut să nu mai fie conex?

Numarul minim de muchii ce pot fi eliminate sunt : 2

Notiuni

Definiţie. Gradul unui vârf x este numărul muchiilor incidente cu x.
Gradul vârfului x se notează cu d(x).
Ex. în Fig.1 d(1)=3, d(4)=2, d(8)=0, d(6)=1
Un vârf care are gradul 0 se numeşte vârf izolat.
Un vârf care are gradul 1 se numeşte vârf terminal.
Propoziţia 1. Dacă un graf G=(X,U) are m muchii şi n vârfuri iar X={x1,x2,..,xn}, atunci d(x1)+d(x2)+...+d(xn)=2m.
Corolar. În orice graf G există un număr par de vârfuri de grad impar.
Definiţie. Se numeşte graf complet cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.
Propoziţia 2. Un graf complet Kn are n(n-1)/2 muchii.
Definiţie. Un graf G=(X,U) se numeşte bipartit dacă există două mulţimi nevide A, B astfel încât X=A U B, A Ç B =F şi orice muchie u a lui G are o extremitate în A iar cealaltă în B.
Definiţie. Un graf bipartit se numeşte complet dacă pentru orice x din A şi orice y din B, există în G muchia [x,y].

Definiţie. Se numeşte lanţ în G succesiunea de vârfuri L={xi1, xi2,..., xik} cu proprietatea că orice două noduri consecutive din L sunt adiacente, adică [xi1, xi2], [xi2, xi3],..., [xik-1, xik] Î U.
Dacă vârfurile xi1, xi2,..., xik sunt diferite două câte două atunci lanţul se numeşte elementar. În caz contrar, lanţul este neelementar.

Definitie subgraf

Definiţie : Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.

Definitie graf partial

Definiţie :  Un graf parţial al grafului G=(V,U) este un graf G1=(V,U1) astfel încât U1este inclus in U, adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii U1 este chiar U sau o submulţime a acesteia (un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii).

Definitie Grafuri neorientate

Definiţie  : Se numeşte graf neorientat o pereche ordonată de mulţimi (V,U), V fiind o mulţime finită şi nevidă de elemente numite noduri sau vâfuri, iar U o mulţime de perechi neordonate (submulţimi de două elemente) din V numite muchii.