Probleme rezolvate

1.

Matricea lanturilor - algoritmul Roy-Warshall Se citeste un graf neorientat cu n noduri si m muchii dat prin vectorul muchiilor. Sa se construiasca o matricea existentei lanturilor(a[i][j] este 1 daca exista lant de la i la j si 0 in caz contrar). Ex: Pentru graful din imagine se obtine matricea lanturilor urmatoare: 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0

#include<fstream.h>
int k,m,n,x[100],a[100][100],p[100];

fstream f("graf.in",ios::in);
fstream g("graf.out",ios::out);

void citire()
 {int x,y;
  f>>n>>m;
  for(int i=1;i<=m;i++)
   {f>>x>>y;
    a[x][y]=1;
    a[y][x]=1;
   }
 }
void rw()
 {int i, j, k;
  for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
   if(i!=j)
   if(a[i][j]==0)
   a[i][j]=a[i][k]*a[k][j];
 }
 void afis()
  {for(int i=1;i<=n;i++)
    {g<<endl;
     for(int
     j=1;j<=n;j++)
      g<<a[i][j]<<" ";
   }
  }

 void main()
  {citire();
   rw();
   afis();
  }

2.

Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze pe linii separate componentele sale conexe. 
Ex: Pentru graful alaturat se vor afisa urmatoarele componente conexe: 
1 2 4 5 
3 7 
6

#include<fstream.h>

int a[100][100],n,m,x[100],p[100];

void citire()
{ int i,l,c;
  ifstream f("g.in");
  f>>n>>m;
  for(i=1;i<=m;i++)
  { f>>l>>c;
    a[l][c]=1;
    a[c][l]=1;
  }
}

void bf(int k)
{ int i,s,d;
  x[1]=k;
  p[k]=1;
  s=d=1;
  while(s<=d)
  { for(i=1;i<=n;i++)
     if(a[x[s]][i]==1 && !p[i])
 { d++;
   x[d]=i;
   p[i]=1;
 }
    s++;
  }
  for(i=1;i<=d;i++) cout<<x[i]<<" ";
  cout<<endl;
}

void main()
{ citire();
  int i;
  for(i=1;i<=n;i++)
    if(!p[i]) bf(i);
}



Varianta 31: Se considera graful neorientat cu 7 noduri, numerotate de la 1 la 7, si muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre urmatoarele succesiuni de noduri reprezinta un lant care trece o singura data prin toate nodurile grafului? (4p.)
   
a. (1, 2, 3, 4, 5, 6, 7)                

b. (4, 5, 3, 6, 7)



c. (7, 6, 3, 5, 4, 2, 1)               

d. (1, 3, 5, 4, 2, 3, 6)
  

Raspuns :  c ,deoarece este singura succesiune de noduri  care trece o singura data prin toate varfurile.







Varianta 32. Graful neorientat cu 8 noduri, numerotate de la 1 la 8, este

reprezentat cu ajutorul matricei de adiacenta alaturate.  Pentru acest graf este adevarata afirmatia: (4p.)



a. Graful este hamiltonian               



b. Graful nu are noduri de grad 0



c. Gradul maxim al unui nod este 3



d. Graful are trei componente conexe







Raspuns:d ,deoarece  graful nu contine toate nodurile conditie necesara pentru un graf hamiltonian, are graduri de nodul 0 iar gradul maxim al unui nod este 4. Dupa cum se poate observa pe desenul corespunzator matricei de adiacenta graful are 3 componente conexe.






Varianta 34. Graful neorientat cu 60 de noduri, numerotate de la 1 la 60, are numai muchiile [1,60], [60,20], [2,30] si [4,30]. Numarul componentelor conexe ale grafului este egal cu:



(4p.)



a. 3

b. 56

c. 54 

d. 0



 Raspuns b. deoarece din 60 de noduri scadem 6 noduri si adaugam 2(cele 2 componente conexe) rezultand 56.







Varianta 35. Un graf neorientat cu 10 noduri, numerotate de la 1 la 10,este reprezentat cu ajutorul listelor de adiacenta alaturate.Câte componente conexe are graful si care este numarul    minim de muchii ce trebuie adaugate pentru ca graful sa fie



conex? (6p.)



1:3,5



2:4



3:1,5



4:2,8



5:1,3



6:



7:10



8:4



9:



10:7







Raspuns :5 componente conexe  ,                                           trebuie adaugate 4  muchii astfel  incat graful sa fie conex.











Varianta 36. Se considera un graf neorientat cu 7 noduri       numerotate de la 1 la 7 si muchiile [1,2],[1,3],[2,3],[2,4],[2,5],[2,6],[4,6],[5,7],[6,7]. Care este numarul minim de muchii care trebuie adaugate pentru ca acest graf sa devina eulerian? (4p.)







Raspuns : minim 8 muchii(muchiile albastre) (fiecare nod trebuie sa aiba grad par si trebuie sa existe toate muchiile )









Varianta 38. Urmatorii doi itemi se refera la un graf neorientat cu 7 noduri,nume-rotate de la 1 la 7 si muchiile [1,5], [2,3], [2,4], [2,5], [3,4], [4,5], [4,7], [5,6], [5,7].







1. Care este numarul minim de muchii care trebuie eliminate astfel încât graful sa aiba 3 componente conexe? (6p.)



Raspuns:eliminam [1,5] [5,6] (2 muchii ) si avem 1 si 6 doua componenta conexe   {2,3,4,5,7} formeaza a treia componenata conexa .







2. Câte cicluri elementare distincte exista în graf? Doua cicluri sunt distincte daca difera prin cel putin o muchie.



Raspuns: 5 cicluri elementare



Rezolvare :

(2,5,7,4,3,2)  



(2,3,4,2)



(3,4,5,2,3)



(3,2,5,7,4,3)



(3,2,4,7,5,3)







Varianta 39. Se considera un graf neorientat cu 8 noduri, numerotate de la 1 la 8, si muchiile [1,5], [1,6], [2,6], [3,4], [3,6], [3,7], [4,6], [6,8], [7,8]. Daca se elimina nodul 6 si toate muchiile incidente cu acesta câte componente conexe va avea subgraful rezultat?








                                                                                         
 Rezolvare:





















Raspuns : 3 componenete conexe 

Variante Bac 51-59 P.B                                                       Varianta 51




2) Se consideră un graf neorientat cu 5 noduri şi 9 muchii. Care dintre următoarele şiruri de

numere pot fi gradele nodurilor grafului?

a) 4, 2, 6, 4, 2                  b) 2, 2, 1, 2, 2

c) 1, 1, 1, 1, 1                  d) 4, 3, 3, 4, 4







                                          


Raspuns:se foloseste formula 2*m=2*9=18,d) este varianta corecta.