Problema Rezolvate

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.

  

Probleme rezolvate

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);
}

! Observatii

üOrice varf izolat este considerat componenta conexa.

üDaca numarul componentelor conexe dintr-un graf este mai mare decât 1, atunci graful nu este conex.

üUn graf conex are o singura componenta conexa, care cuprinde toate nodurile sale.

üÎn teoria grafurilor, un graf conex este un graf neorientat în care există un drum între oricare două noduri distincte. Un graf neorientat conex ,care are un nod cu proprietatea că dacă acel nod este eliminat (împreună cu muchiile adiacente), graful își pierde proprietatea de conectivitate, se numește

1-conex. Similar, un graf este 2-conex dacă pentru a-i elimina proprietatea de conexitate, este nevoie de eliminarea a două noduri. În general, dacă dintr-un graf conex este nevoie să se elimine un minim de

k noduri (cu muchiile adiacente lor) pentru a obține un graf neconex, acel graf este k-conex.

üNumarul minim de muchii necesare ca un graf neorientat sa fie conex este n-1 ( n=numarul de noduri ) .

üUn graf conex cu n noduri si m-1 muchii este aciclic si maximal in raport cu aceasta proprietate.

üDaca un graf neorientat conex are n noduri si m muchii , numarul de muchii care trebuie eliminate pentru a obtine un graf partial conex , aciclic este (m-n+1).

üDaca un graf are n noduri si m muchii si p componente conexe numarul de muchii care trebuie eliminate pentru a obtine un graf partial aciclic

( arbore) este (m-n+p) .

üPentu a obtine dintr-un graf neorientat conex , 2 componente conexe ,numarul minim de muchii care trebuie eliminate este egal cu gradul minim din graf .

                          Reprezentarea grafurilor neorientate

1.Cu ajutorul matricei de adiacenta(matricei adiacente).

 A є M(m,n),n-nr de varfuri,m-nr de muchii.,unde A(i,j)=1,daca exista muchia (i,j)

                                                                                      0,daca nu exista

OBS! Matricea de adiacenta este simetrica fata de diagonala principala: A(i,j)=A(j,i).

OBS! Gradul unui varf x se poate determina calculand suma pe linia x.

·  Graf partial si subgraf

Def! Fie graful  G=(X,U).Un graf partial al lui G,este un graf G1=(X,V) ,cu V≤U(inclus).Altfel spus ,un graf partial se obtine pastrand toate varfurile si eliminand niste muchii.

Def! Fie graful G=(X,U).Un subgraf al lui G,este un graf S=(Y,T),unde Y≤X si T≤V,iar T va contine numai acele muchii care au ambele extremitati in Y.Altfel spus,un subgraf S al lui G se obtine din G eliminand niste varfuri si odata cu acestea acele muchii care au cel putin o extremitate in submultimea eliminata.

Se numeste graf complet cu n varfuri,notat K indice n (Kn),un graf G=(X,U) cu proprietatea ca oricare doua varfuri sunt adiacente,adica oricare cuplu x,y є X,esista muchia [x,y] є U.

Teorema! Un graf complet  cu n varfuri are n(n-1)/2 muchii.

Definitie!Se numeste graf bipartit ,un graf G=(X,U) cu proprietatea ca exista doua multimi distincte A si B incluse in X,astefel incat:

      -A∩B=multime vida,A+B=X.(+ este reunit);

      -toate muchiile grafului au o extremitate in A si cealalta in B.

Definitie!Se numeste graf bipartit complet ,un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B , exista muchia [x,y].(A+B=X).

Grafuri neorientate. Probleme propuse

1. Fie un graf neorientat memorat prin matricea de adiacente si o succesiune de k noduri. Sa se determine daca succesiunea citita este un lant din graf
2. Din fisierele mat1.in si mat2.in se citesc doua matrici patratice associate grafurilor g1 si g2. Sa se deremine daca g2 este graf partial pentru g1
3. Fie o harta cu n orase. Cele n orase se citesc din fisier. Intre cele n orase exista m drumuri. Se cunosc distantele celor n drumuri.
1. Sa se determine daca orasul x si orasul y sunt vecine
2. Sa se afiseze lungimile tuturor localitatilor intre care exista drum direct
3. Sa se determine lungimea minima a drumului dintre doua localitati citite de la tastatura
4. La o receptie sunt invitate n personae. Se cunosc numele celor n persoane .  Intre anumite persoane exista relatii de colaborare. Sa se determine daca se pot dispune cele n personae la o masa rotunda astfel incat intre oricare doua personae alaturate sa existe relatii. Se citesc : numele persoanelor si cele m relatiile sub forma de perechi de nume
5. Un eschimos locuieste la iglul cu numarul z. El are o harta pe care sunt marcate iglu-urile din zona (numerotate de la 1 la n) si distantele dintre acestea. Stiind ca din cauza frigului eschimosul nu poate sa parcurga o distanta mai mare de 20 km fara oprire, afisati o varianta de a ajunge  la prietenul lui care locuieste la iglul cu numarul w, eventual cea mai scurta varianta care indeplineste cerinta data. Cati kilometri  a parcurs eschimosul?
6. Un graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua multimi A si B astfel incat oricare doua varfuri din aceeasi multime sa nu fie adiacente. Sa se scrie un program care verifica daca un graf este bipartit si in caz afirmativ sa se tipareasca multimile A si B
7. Problema colorarii unei harti. Se citesc 4 culori (siruri de caractere) si denumirile a n tari (siruri de caractere) . Sa se coloreze harta astfel incat sa nu existe doua tari alaturate avand aceeasi culoare.  Se va afisa o solutie : tara-culoare, tare-culoare etc.
8. Sa se coloreze un graf astfel incat oricare doua muchii incidente cu acelasi nod sa fie colorate diferit. Care este numarul minim de culori necesar.
9. O pestera are n incaperi, fiecare situata la o adancime h. Configuratia pesterii este data de cele m culoare de acces intre camerele pesterii (culoarele sunt date ca extremitati). In incaperea s exista un izvor de apa sulfuroasa. Se dau n, m, cele m culoare (ca perechi x-y), s si adancimile h ale camerelor. Determinati incaperile inundate si culoarele umezite.
10. Fie un graf neorientat. Sa se determine daca graful contine cicluri.

Descompunerea in componente conexe a unui graf neorientat, dat prin matricea de adiacenta

#include<fstream.h>
int s[20],a[20][20],n,i,j,k;

void df(int nod)
{
int k;
cout<<nod<<" ";
s[nod]=1;
for(k=1;k<=n;k++)
 if((a[nod][k]=1) && (s[k]==0)) df(k);
}

void main()
{
fstream f("graf.txt",ios::in);
f>>n;
while(f>>i>>j) a[i][j]=1;
f.close();
k=1;
for(i=1;i<=n;i++)
 if(s[i]==0)
 {
 cout<<"componenta "<<k<<endl;
 df(i);
 cout<<endl;
 k++;
 }
}

Sa se verifice daca un graf este hamiltonian

Fiind dat un graf neorientat memorat prin matricea de adiacenta sa se determine daca graful este Hamiltonian sau nu.

Notiuni teoretice

Definitie: Se numeste ciclu hamiltonian un ciclu elementar care trece prin toate varfurile grafului.

Definitie: Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian.

#include<fstream.h>

int st[100],n,m,k,a[20][20];

int ns;

int e_valid()

{if(k>1)

if(!a[st[k-1]][st[k]])

return 0;

else

for(int i=1;i<=k-1;i++)

if(st[i]==st[k])

return 0;

if(k==n)

if(!a[st[1]][st[k]])

return 0;

return 1;

}

void afisare()

{for(int i=1;i<=n;i++)

cout<<st[i]<<" ";

cout<<st[1];

k=0;

ns++;

}

void back()

{k=1;

while(k>0)

if(st[k]<n)

{st[k]++;

if(e_valid())

if(k==n)

afisare();

else

{k++;

st[k]=0;}

}

else

k--;

}

void main()

{

fstream f;

f.open("hamiltonian.in",ios::in);

int u,v;

if(f)

cout<<"ok!";

else

cout<<"eroare";

cout<<endl;

f>>n>>m;

for(int i=1;i<=m;i++)

{f>>u>>v;

a[u][v]=a[v][u]=1;

}

cout<<"matricea de adiacenta "<<endl;

for( i=1;i<=n;i++)

{for(int j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

back();

if(ns==0)

cout<<”nu exista solutii”;

}