Grafuri

Definitie:Fie G =(V, M) un graf bipartit. Graful G se numeşte graf bipartit complet, dacă pentru orice x din V1 şi orice y din V2 exista in G muchia [x,y]. Exemplu de graf neorientat bipartit:G=(V, M) unde: V={ 1,2,3,4} si M={[1,3], [1,4], [2,3], [2,4]}Reprezentarea sa grafică este: Observatie 1:A demonstra că un graf este bipartit … Read more

Definitie:Fie G =(V, M) un graf neorientat. Graful G se numeşte graf bipartit, dacă există două multiminevide Vl şi V2 cu proprietătile: V1 reunit V2 = VV1 intersectat V2 = multimea vida orice muchie a lui G are o extremitate în V1 şi pe cealaltă în V2. Exemplu de graf neorientat bipartit:G=(V, M) unde: V={ … Read more

Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet. Date de intrare Fişierul de intrare graf_complet.in conţine pe prima linie numărul de grafuri G. Pentru fiecare dintre cele G grafuri se dă n și apoi matricea de adiacență, formată din n linii și n coloane. … Read more

Definitie:Fie G=(V, M) un graf neorientat. Graful G se numeşte graf complet, dacă oricare două vârfuri distincte ale sale sunt adiacente. Exemplu de graf neorientat complet:G=(V, M) unde: V={ 1,2,3,4} si M={[1,2], [1,3], [l,4], [2,3], [2,4], [3,4]}Reprezentarea sa grafică este: Observatii: Într-un graf complet cu n vârfuri gradul fiecărui vârf este n-1, deoarece fiecare vârf … Read more

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate vârfurile etichetate cu valori prime. Să se determine câte muchii va avea subgraful obținut. Date de intrare Fişierul de intrare subgraf.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. … Read more

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu proprietatea că ambele extremități au aceeași paritate. Să se determine câte muchii va avea graful parțial obținut. Date de intrare Fişierul de intrare graf_partial.in conţine pe prima linie numărul n, reprezentând … Read more

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim. Date de intrare Fişierul de intrare gradmax.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Date … Read more

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile izolate ale grafului. Date de intrare Fişierul de intrare izolate.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Date … Read more

Se dă lista muchiilor unui graf neorientat. Să se afișeze gradul fiecărui vârf. Date de intrare Fişierul de intrare grade.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Date de … Read more

Pentru fiecare nod i , cu i{1,2,…,n}, formăm lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremităţi ale muchiilor ce trec prin nodul i. Avem pentru graful considerat : X = { 1,2,3,4,5,6,7 } → multimea vârfurilor (nodurilor) U= { u1,u2,u3,u4,u5 }→ multimea muchiilor (arcelor) Muchiile sunt : u1 = (1,2) ; u2 … Read more