Cuprins Modele de Subiecte 2012

Biologie anatomie si fiziologie umana, genetica si ecologie umana
Biologie vegetala si animala
Chimie anorganica
Chimie organica
Ecologie
Filosofie
Fizica
Geografie
Informatica C matematica-informatica
Informatica C stiinte ale naturii
Informatica Pascal matematica informatica
Informatica Pascal stiinte ale naturii
Istorie
Logica
Matematica M1 matematica-informatica
Matematica M2
Matematica M3
Psihologie
Limba Romana
Sociologie

Cuprins Modele de Subiecte 2013

Biologie – Anatomie si fiziologie umana, genetica si ecologie umana
Biologie – vegetala si animala
Chimie anorganica filiera tehnologica
Chimie anorganica filiera teoretica
Chimie organica filiera tehnologica
Chimie organica filiera teoretica
Ecologie
Filosofie
Fizica filiera tehnologica
Fizica filiera teoretica
Geografie
Informatica C matematica-informatica
Informatica C stiinte ale naturii
Informatica Pascal matematica informatica
Informatica Pascal stiinte ale naturii
Istorie
Logica
Matematica M1 matematica-informatica
Matematica M3 pedagogic
Matematica M2 Stiinte ale Naturii
Matematica M2 Profil Tehnologic
Psihologie
Romana profil real, tehnologic
Romana profil uman, pedagogic
Sociologie

Cuprins Modele de Subiecte 2014

Biologie – Anatomie si fiziologie umana, genetica si ecologie umana
Biologie – vegetala si animala
Chimie anorganica filiera tehnologica
Chimie anorganica filiera teoretica
Chimie organica filiera tehnologica
Chimie organica filiera teoretica
Ecologie
Filosofie
Fizica filiera tehnologica
Fizica filiera teoretica
Geografie
Informatica C matematica-informatica
Informatica C stiinte ale naturii
Informatica Pascal matematica informatica
Informatica Pascal stiinte ale naturii
Istorie
Logica
Matematica M1 matematica-informatica
Matematica M3 pedagogic
Matematica M2 Stiinte ale Naturii
Matematica M2 Profil Tehnologic
Psihologie
Romana profil real, tehnologic
Romana profil uman, pedagogic
Sociologie

Cuprins Modele de subiecte 2015

Biologie – Anatomie si fiziologie umana, genetica si ecologie umana
Biologie – vegetala si animala
Chimie anorganica filiera tehnologica
Chimie anorganica filiera teoretica
Chimie organica filiera tehnologica
Chimie organica filiera teoretica
Ecologie
Filosofie
Fizica filiera tehnologica
Fizica filiera teoretica
Geografie
Informatica C matematica-informatica
Informatica C stiinte ale naturii
Informatica Pascal matematica informatica
Informatica Pascal stiinte ale naturii
Istorie
Logica
Matematica M1 matematica-informatica
Matematica M3 pedagogic
Matematica M2 Stiinte ale Naturii
Matematica M2 Profil Tehnologic
Psihologie
Romana profil real, tehnologic
Romana profil uman, pedagogic
Sociologie

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)

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;

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

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

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

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