materie

by

Grafuri neorientate – drumul optim intr-un graf

Una din problemele care apar foarte des în practică este găsirea drumului optim între două noduri ale unui graf.

Formalizarea problemei drumului optim este următoarea:

“Fiind dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)”.

Valoarea unui drum este dată de suma valorilor arcelor care îl compun. Pentru problema drumului optim s-au elaborat mai multe categorii de algoritmi, după cum urmează:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell)
Algoritmi prin ajustări succesive (Ford)
Algoritmi prin inducţie (Dantzig)
Algoritmi prin ordonare prealabilă a vârfurilor grafului
Algoritmi prin extindere selectivă (Dijkstra)

by

Grafuri neorientate – implementarea unui graf utilizand pointeri

Pentru a defini un graf utilizând pointeri, vom defini următoarele structuri:
typedef struct NODL
{
  //nodul adiacent indicat
  struct NODG *nod;
  //pointer spre următorul nod în lista de adiacenţe
  struct NODL *urml;
} nodl;

typedef struct NODG
{
  int cheie;
  … informaţii
  //începutul şi sfârşitul listei de adiacenţă
  struct NODL *inc_lista, *sfarsit_lista;
  //pointer spre următorul nod al grafului
  struct NODG *urmg;
} nodg;

//începutul şi sfârşitul listei de noduri din graf
struct nodg *incG, *sfG;

by

Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta


//definirea tipului nod
typedef TIP_NODG
{
  int cheie;
  ... informaţii
} tip_nodg;
ntip_nodg nod[Nmax];
//tabloul de noduri
//Nmax este numărul maxim de noduri
int arc[N max] [N max];
//matricea de adiacenţă

Adăugarea unui nod cu cheia key:
int i;
nod[N].cheie=key;
//adăugăm nodul N+1
for(i=0;i <= N;i++)   arc[i][N]=arc[N][i]=0; //iniţalizarea cu o a conexiunilor cu celelalte noduri N++; //incrementarea numărului de noduri Continue reading →

by

Grafuri neorientate – euleriene

Fiind dat un graf neorientat, să se determine dacă este eulerian, iar dacă răspunsul este afirmativ, să se determine toate ciclurile euleriene care încep dintr-un nod dat.

Pentru a rezolva această problemă, vom parcurge următorii paşi:
• se determină dacă graful este conex
• se determină dacă fiecare nod are grad par


#include "stdio.h"
#include "conio.h"
int a[10][10],viz[10],n,m;
//parcurgere in adâncime
void df_r(int nod)
{
  int k;
  //afişăm nodul curent ca vizitat
  printf("%d ",nod);
  //marcăm nodul curent ca vizitat
  viz[nod]=1;
  //pentru fiecare nod k
  for(k=1;k <= n;k++)     //dacă există muchie între nodul curent şi nodul k şi nodul k nu a fost incă vizitat,     //apelăm funcţia recursivă de vizitare depth first df_r având ca parametru nodul k     if(a[nod][k] && !viz[k])       df_r(k); } Continue reading →

by

Grafuri neorientate – hamiltonian

Se citeşte matricea de adiacenţă a unui graf. Să se determine dacă graful este hamiltonian.

Soluţie: vom folosi metoda backtracking, aplicată asupra unei stive în care vom păstra nodurile care compun lanţul. Vom porni de la primul nod şi vom putea adăuga în stivă doar un nod adiacent. De asemenea, nodul adăugat nu trebuie să se regăsească pe nivelurile anterioare. Dacă am atins în stivă numărul total de noduri iar nodul final este adiacent cu nodul iniţial, am găsit soluţia problemei.


#include "stdio.h"
#include "conio.h"
int stiva[100],n,m,k,nr_solutii,a[20][20];
int verifica()
{
  int i;
  if(k>1)
    //dacă a[st[k-1]][st[k]] este 0 returnăm 0
    if(!a[stiva[k-1]][stiva[k]])
       return 0;
    else
      //dacă a [stiva[k-1]][stiva [k]] este 1 căutam pe toate nivelurile
      //anterioare nivelului curent
      for(i=1;i <= k-1;i++)         //dacă nodul curent se găseşte pe unul din nivelurile         //anterioare returnăm 0         if(stiva[i] == stiva[k])           return 0;         //dacă stiva conţine toate nodurile grafului         if(k == n)           //iar ultimul nod nu este adiacent cu primul nod returnăm 0           if(!a[stiva[1]][stiva[k]])             return 0;   return 1; } Continue reading →

by

Grafuri neorientate – ponderate

Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.

Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel:
p(i,j) = 0 dacă i=j
p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j)
P(i,j) = $latex \infty$ în restul cazurilor

Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe.

Să se scrie un program C care verifică dacă un graf este conex şi să se afişeze toate componentele sale conexe.


#include "stdio.h"
#include "conio.h"
int n,m,a[20][20],viz[20],nrc=0;
void viziteaza(int nod)
{
  int i;
  viz[nod]=nrc;
  for(i=1;i <= n;i++)     if(a[nod][i] == i && viz[i] == 0)       viziteaza(i); } void main() {   int nod,i,j,x,y;   printf("Introdu numărul de noduri:");   scanf("%d",&n);   printf("Introdu numărul de muchii:");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   printf("Introdu muchiile :\n");   for(i=1;i <= m;i++)   {     printf("De la nodul: ");     scanf("%d",&x);     printf("la nodul: ");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   for(nod=1;nod <= n;nod++)     if(viz[nod] == 0)     {       nrc++;       viziteaza(nod);     }   if(nrc == 1)     printf("Graful este conex!\n");   else     printf("Graful nu este conex!\n");   printf("Componentele conexe sunt:\n");   for(i=1;i <= nrc;i++)   {     printf("Componenta %d:",i);       for(j=1;j <= n;j++)         if(viz[j] == i)           printf("%d ",j);     putchar("\n");   }   getch(); }

by

Grafuri neorientate – Drumuri intr-un graf

Matricea de adiacenţă A(n,n) a unui graf G=(X,U) evidenţiază drumurile de lungime 1 între oricare 2 noduri ale grafului.

Pentru a găsi drumurile de lungime 2 între 2 noduri ale unui graf se procedează astfel. Se consideră două noduri $latex x_{i}$ şi $latex x_{j} \in X$. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod $latex x_{k} \in X$, cu proprietatea că există atât arcul $latex \left ( x_{i},x_{k} \right )$ cât şi arcul $latex \left ( x_{i},x_{k} \right )$. Pentru a vedea dacă acest arc există, se poate lua pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce $latex \left (\left ( x_{i},x_{k} \right ) si \left ( x_{i},x_{k} \right ) \right )$. Aceasta este echivalent cu a verifica dacă în matricea de adiacenţă există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Acest lucru este echivalent cu a verifica dacă elementul de pe poziţia (i,j) din $latex A^{2}$ este diferit de 0. Numărul de drumuri de lungime 2 dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Generalizând, numărul de drumuri de lungime k dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Dacă între nodurile $latex x_{i}$ şi $latex x_{j}$ există un drum de lungime >= n atunci el va conţine un număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem $latex x_{k}$, va apărea de două ori. Vom avea în acest caz un drum de la $latex x_{i}$ până la prima apariţie a lui $latex x_{k}$, şi un drum de la ultima apariţie a lui $latex x_{k}$ la $latex x_{j}$.Eliminând toate nodurile dintre prima apariţie a lui $latex x_{k}$, şi ultima apariţie a sa vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care $latex x_{k}$ apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la $latex x_{i}$ la $latex x_{j}$ atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între $latex A^{1}$ şi $latex A^{n-1}$, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A.

by

Grafuri neorientate – parcurgerea in adancime

Implementarea parcurgerii în adâncime pentru un graf neorientat


#include
#include
int a[20][20],n,i,j;
void parc_adancime()
{
  int s[40],varf,k,nod,urm[20],viz[20],in;
  printf("Introduceti nodul iniţial de pornire= ");
  scanf("%d",&in);
  for (nod=1;nod <= n;nod++)   {     urm[nod]=0;     viz[nod]=0;   }   varf=1;   //şirul s va păstra ordinea de traversare în adâncime;   //introducem nodul de start în acest şir   s[varf]=in;   //marcăm nodul de pornire ca vizitat   viz[in]=1;   //afişăm nodul de start ca prim nod în traversarea în adâncime   printf("%d ",in);   while (varf >= 1)
  {
    //nod va fi nodul căruia îi mai căutăm succesori
    nod=s[varf];
    //k va conţine numărul nodului de unde reîncepem să
    // căutam succesori pentru nodul nod
    k=urm[nod]+1;
    while ((k <= n) && ((a[nod][k] == 0) || ((a[nod][k]==1)&&(viz[k]==1))))     {       k++;     urm[nod]=k;     }     if (k == n+1)       vârf--;     else     {       varf++;       s[varf]=k;       viz[k]=1;       printf("%d", s[varf]);     }   }   putchar("\n"); } void main() {   int m,i,j,x,y;   printf("Introduceti numărul de noduri n=");   scanf("%d",&n);   printf("Introduceti numărul de muchii m=");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   for(i=1;i <= m;i++)   {     printf("De la nodul:");     scanf("%d",&x);     printf("La nodul:");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   parc_adancime();   getch(); }

by

Grafuri neorientate – parcurgerea in latime

Implementarea parcurgerii în lăţime pentru un graf neorientat


#include "stdio.h"
#include "conio.h"
int a[20][20],n;
void parc_latime()
{
  int c[20],p,u,v,viz[20],im,nod;
  printf("Dati nodul de pornire pentru parcurgere: ");
  scanf("5d",&in);
  for(nod=1;nod <= n; nod++)     viz[nod]=0;   p=1;u=1;   //traversarea începe cu nodul in; şirul c va păstra ordinea de traversare   c[1]=in;   //marcăm nodul in ca vizitat   viz[in]=1;   while(p <= u)   {     //vom căuta vecinii nodului v     v=c[p];     for(nod=1;nod <= n;nod++)       //dacă există muchie între nodul nod şi nodul v şi       //nodul nod nu a fost vizitat       if((a[v][nod]==1)&&(viz[nod]==0))       {         //incrementăm indicele şirului ce conţine traversarea         u++;         //punem nodul în şirul ce conţine traversarea         c[u]=nod;         //marcăm nodul ca vizitat         viz[nod]=1;       }       //vom căuta vecinii următorului nod din şirul ce conţine traversarea       p++;   }   for (ind=1;ind <= n;ind++)     printf("%d ",c[ind]);   putchar("\n"); } Continue reading →

by

Metoda Divide et Impera – Problema cautarii binare

Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Se citeşte un şir de n elemente numere întregi ordonate crescător şi o valoare întreagă key. Să se decidă dacă valoarea key se găseşte printre valorile şirului de elemente şi în caz afirmativ să se tipărească indicele componentei care conţine acea valoare.


#include "stdio.h"
int a[10],n,key;

void caut(int i, int j)
{
  if(key == a[(i+j)/2])
    printf("Valoarea a fost gasita la indicele %d\n",(i+j)/2);
  else
    if(i < j)       if(nr < a[(i+j)/2])         caut(i, (i+j)/2-1);       else         caut((i+h)/2+1,j); } Continue reading →