Discussion :

[spartcrk]

Bonjour,

Je cherche à calculer les différentes faces d'un graphe planaire, mais je peine à trouver une bonne méthode... J'ai testé pas mal de choses, parcours en largeur, donner des poids aux arêtes... J'ai aussi pensé créer, pour chaque face, un sommet qui serait connecté à chaque sommet de cette face, mais pour le coup je ne parvient pas non plus à faire ça.

Vous auriez une idée d'algo afin de m'aider à progresser ?

Merci d'avance et bonne journée !

[dinobogan]

Tu parles de la recherche des plus petits cycles du graphe ?

[wiwaxia]

Je cherche à calculer les différentes faces d'un graphe planaire, mais je peine à trouver une bonne méthode ...
Vous auriez une idée d'algo afin de m'aider à progresser ?

Bonjour,
L'énoncé du problème est ambigu, comme le suggère la précédente réponse, car il donne l'impression que l'on puisse travailler sur une représentation géométrique du graphe; et le fait qu'il soit planaire, et que deux arêtes ne s'entrecroisent pas dans un plan, serait de nature à orienter les recherches dans ce sens ... sauf qu'en y réfléchissant bien, la méthode conduit à de sérieux ennuis: un graphe (même planaire) peut admettre plusieurs représentations différentes par leur topologie, et les polygones de plus de 3 sommets comporter des angles rentrants. Mieux vaut donc s'abstenir de toute considération géométrique, et partir de la définition.

Un graphe est défini par la donnée de deux ensembles:
1) celui (noté E_S) des (N_S) sommets qu'il comporte E_S = { S₁, S₂ ... S_Ns };
2) celui (noté E_A) des (N_A) arêtes présentes, dont chaque élément est un couple (S_i, S_j) de sommets: E_A = { (S_i, S_j)_k }.

Le point de départ du programme sera donc:
a) la liste des sommets indexés, qui - en l'absence de toute représentation graphique - se réduit à l'intervalle d'entiers [1 ... N_S], donc à la valeur de (N_S);
b) la liste des arêtes, donnée essentielle définissant le graphe; il s'agit d'un tableau comportant (N_A) couples d'entiers (i, j) qui vérifient (j>i), afin que chaque arête ne soit citée qu'une seule fois.

L'inventaire rapide et complet des arêtes sera possible si leur indexation est conforme à la comparaison immédiate des deux couples (i, j) et (i', j'): (k' > k) étant équivalent à ((i' > i) ou ((i'=i) et (j' > j))).
La limitation raisonnable au cas des graphes simples exclut la présence de boucles (i=j) et de liens multiples ((i=i') et (j=j')), et permet d'envisager une matrice d'adjacence, matrice symétrique d'ordre (N_S) dont les éléments sont des booléens.

L'inventaire des cycles est le plat de résistance du programme; il exige que chaque cycle soit caractérisé par son sommet de départ, et son sens de parcours. On conviendra pour cela que:
a) la position de départ correspond à l'indice minimal: on aura donc (i₁ < i_p) pour tous les autres sommets du cycle;
b) des 2 voisins possibles (i₂ et i_m),le premier abordé est celui de plus petit indice soit (i₂ < i_m).
De plus, la longueur des cycles ne peut dépasser les nombres de sommets (N_S) et d'arêtes (N_A); et par ailleurs, tout graphe simple connexe et acyclique comportant (N_S - 1) arêtes, le nombre de cycles minimaux (indécomposables en cycles plus petits) admet pour expression N_cm = N_A - N_S + 1 .

La recherche sera confrontée à des arborescences; mais elle sera possible, et relativement rapide, en se basant sur les propriétés précédentes, qui fournissent des critères d'arrêt, de sélection et de reconnaissance des cycles.
Elle pourra commencer par une présélection du sommet de départ: pour (i₀) variant de (1) à (N_S) , inventorier tous les autres sommets auxquels il peut être relié; plusieurs cas d'impossibilité se présentent alors:
- aucun sommet voisin: c'est un point sans connexion avec le reste du graphe - à éliminer;
- un seul voisin: il s'agit de l'extrémité d'une chaîne - à éliminer;
- deux voisins avec (i₀) > Min(j₁, j₂): ce ne peut être le départ d'un cycle - à éliminer.