Discussion :

[valliere]

Bonjour à tous,

le problème que je rencontre est le suivant:

J'ai implémenté une bibliothèque pour afficher un graphe orienté (arcs) et le lire à partir d'un fichier. Sauf que mon prof veut maintenant que je calcule le couplage max du graphe mais non orienté (arêtes) cette fois-ci. Je ne sais pas comment faire pour avoir un graphe non orienté . J'ai besoin d'idées d'implémentation svp. Je précise que la lecture du fichier se fait dans l'un des constructeurs de la classe Cgraphe

Ma bibliothèque contient: une classe Carc contenant comme attribut:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
        unsigned int uiARCdestination;  //Cette variable contient le sommet destination
 
une classe Csommet contenant comme attributs:
 
       Carc** pSOMarcPartant;     //cette variable contient les sommets partants
 
Carc** pSOMarcArrivant;   //cette variable contient les sommets arrivants
 
unsigned int uiSOMnumeroSommet;   //cette variable contient le numéro du sommet 
 
unsigned int uiSOMnombrePartant;  //cette variable contient le nombre d'arc partant
 
unsigned int uiSOMnombreArrivant;
 
une classe Cgraphe contenant comme attributs:
 
        Csommet** pGRAtableau;   //cette variable contient les sommets du graphe
 
unsigned int uiGRAnbSommet;  //cette variable contient le nombre de sommets du graphe

Merci pour votre aide

[picodev]

Bonjour,

mis à part l'implémentation, tu peux peut-être simplement considérer qu'à chaque graphe G(V,E) non orienté correspond un graphe orienté Go(Vo,Eo) tel que V=Vo et que pour chaque arrête {u,v} de G correspond deux arcs (u,v) et (v,u) dans Go.

[alexgille]

Dans ta Matrice d'adjacence, si tu veux relier deux sommets u et v alors matrice[u][v] = matrice[v][u] = true. Dans ce cas ta matrice est une matrice triangulaire.