Discussion :

[Tokapi]

Bonjour à tous.

Actuellement sur un projet d'étude type mémoire, je suis bloqué sur le problème suivant qu'il me faut résoudre (et qui se résout, mais je ne trouve pas de documentation explicite sur le sujet) :

J'ai un graphe supposé planaire et codé par liste de voisins.
Je veux lui ajouter des arêtes jusqu'à ce qu'il devienne maximalement planaire, c'est-à-dire triangularisé (toutes ses faces sont des triangles) et planaire.

Si jamais vous pouviez m'aider sur ce sujet je vous en serais très reconnaissant.

Merci

[Flodelarab]

Bonjour

Je ne sais pas.

Intuitivement, je ferais ceci:

• Fais la liste des faces du graphe.
• Pour chaque face, distribue un sommet (n'importe lequel) sur les autres sommets de la face, si l'arête n'existe pas déjà.
• Pour les sommets non-impliqués dans une face:
  
  1. Trouver un voisin impliqué dans une face
  2. Relier le sommet non-impliqué à tous les sommets de la face dans laquelle est impliqué le voisin (n'importe laquelle)
  3. Recommencer à 1 jusqu'à ce que tous les sommets non-impliqués soit intégrés.
  4. Si aucun sommet n'a de voisin impliqué dans une face, choisir un sommet et le relier à tous les autres.
• Et ton graphe sera triangularisé.

[Tokapi]

Bonjour Flodelarab, merci pour ta réponse.

Effectivement c'est ce que j'avais pensé faire en premier lieu, mais je n'ai pas trop compris non plus comment trouver les faces d'un graphe (qui ne sont pas uniques), il faut a priori commencer par faire un tri cyclique des listes de voisins et je ne sais pas le faire : mon ex-prof de graphes m'a dit qu'un déterminant bien placé suffit mais je ne sais pas comment m'y prendre et je ne trouve pas de documentation explicite sur ce sujet-là non plus.

J'imagine que le tri cyclique dont il est question est juste un tri arbitraire des voisins mais je n'en suis pas bien sûr.

[tbc92]

J'essaie de comprendre la question...
J'imagine que le contexte, c'est une imprimante 3D. Tu as un volume (disons un cube pour avoir un exemple simple). Pour ce volume, tu connais les 12 arêtes (non ordonnées ...).
Et pour pouvoir imprimer ce cube, tu as besoin de définir sa surface comme une série de triangles.
Ton problème ressemble à ça ?

[Flodelarab]

les faces d'un graphe (qui ne sont pas uniques)

J'ai énormément de mal avec cette phrase. As-tu un exemple qui montre que les faces ne sont pas uniques ?

Le graphe suivant a 4 noeuds, 6 arêtes, 3 faces bien définies.


Non ?

[Tokapi]

@tbc92 : Non pas du tout. J'ai juste un graphe planaire que j'essaie de représenter planairement. Par exemple, ça sert à concevoir des circuits imprimés sur une carte sans croisements d'arrêtes.

@Flodelarab : Non, par exemple si tu dessines l'un des deux triangles dans l'autre triangle, c'est le même graphe mais les faces sont différentes.

[Flodelarab]

On est d'accord. Mais je reprends l'algorithme: ta triangularisation ne sera jamais unique puisque tu peux distribuer n'importe quel sommet sur tous les autres ...

Avec une face en pentagone, tu as 5 façons de trianguler.
Avec un graphe avec un heptagone, un hexagone et un ennéagone, tu as 7x8x9 = 504 façons de trianguler l'intérieur.


Et dans tous les cas, ton noeud non-impliqué dans une face ne pourra jamais être triangulé sans choisir une face d'appartenance.

[Tokapi]

Ah oui la triangularisation n'est pas unique du tout je cherche juste à en trouver une, même pas optimale pour l'instant.

Le problème pour ton algorithme c'est que pour l'instant, même si apparemment ce n'est pas la mer à boire, je ne sais pas comment faire un algorithme qui trouve un arrangement de faces pour un graphe donné.

[wiwaxia]

Bonjour,

Une demande très proche, non mentionnée en bas de page, a été exprimée en novembre dernier.
Déterminer les faces d'un graphe (24/11/2015, 19h20)

[Tokapi]

Bonjour,

Merci pour ta réponse mais pour être honnête cela ne m'aiguille pas beaucoup sur la recherche des faces (ou alors il y a quelque chose que je n'ai pas compris).

(Les faces d'un graphe ne sont pas ses cycles minimaux, d'ailleurs)

[anapurna]

salut


voici un petit pdf qui pourrais t'interesser
il se trouve ici
ou celui-ci

sinon quelques propriété importante
Euler a démontré
Soit :
- S le nombre de sommets d'un graphe planaire topologique
- A son nombre d'arêtes
- F son nombre de faces
F= A-S+2

[Tokapi]

Heu merci anarpuna mais pour être honnête ça ne m'avance pas beaucoup sur mon problème qui est un peu plus avancé que ça ^^

[anapurna]

salut ,

bon alors j'ai pas bien compris la question ^^

si tu cherche a définir des faces les graphes de voronoi me parait être le plus adapté

en fait le principe est de tracer une droite perpendiculaire passant au milieux de deux points perpendiculaire à la droite passant pas ces deux point

pour la triangulation le plus connu est Delaunay pour les graphes c'est voronoi il existe un tas d'exemple pour passer de l'un à l'autre
je ne sais pas si cela pourra t'aider mais j'avoue que ta question est un peu flou

[Flodelarab]

@anapurna:
Le problème de tout ce que tu proposes est que la situation géographique est fixée.
Alors, ça devient facile.
Mais, lui, il est dans un cas purement abstrait auquel correspond une multitude de situations géographiques différentes.
Donc avec des faces différentes, et une triangulation qui en découle.

Sincèrement, je sèche. Comment faire la liste des faces d'un graphe ?

@Tokapi: Par contre, si tu as du temps, tu peux étudier le code de Graphviz qui dessine un graphe à partir de sa description abstraite.

[Tokapi]

Merci pour le conseil flodelarab, en fait c'est déjà ce que je suis en train de faire avec PIGALE ^^

Mais c'est assez difficile de rentrer dans le code, de trouver le bon et de vraiment comprendre ce qu'il se passe.

[Tokapi]

Enfin si j'y ai trouvé cet algo de brutasse qu'au moins je comprends... :

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// G0 is planar and we try to add edges, keeping it planar                       
  {tedge e,e0;
  int nn = n;
  int i,j;
  for(i = 1,j = 1;i <= nn;i++)
      {e = tab[j] = tab[i];
      e0 = G0.NewEdge(G.vin[e],G.vin[-e]);
      if(G0.TestPlanar() == 1)
          n--;
      else
          {j++;
          G0.DeleteEdge(e0);// as G0 would be non planar
          }
      }
  }

(on ajoute une arête au hasard, et on teste si le graphe est toujours planaire...)

Au pire ça peut toujours se faire, mais je n'ose même pas imaginer la tête de la fonction TestPlanar(). Je vais regarder, d'ailleurs.

[Tokapi]

Sinon sur les forum où j'ai demandé (et pour mes professeurs), la solution naturelle semble en effet d'être d'abord de définir les faces puis d'ensuite les trianguler, encore faut-il savoir comment définir les faces. A priori il faut pour cela un "tri cyclique" des voisins de chaque sommet (dans le sens horaire par exemple, ensuite on suit simplement le tri cyclique pour trouver les faces une à une), mais j'ai du mal à comprendre comment faire ça.

[Flodelarab]

Ça me fait un peu la même impression que de faire de la géométrie avec un dessin.
C'est joli.
C'est compréhensible.
Mais le fait de faire un dessin particulier et parfois faux donne des résultats mathématiques incorrects.

[Tokapi]

Ben disons que quand on cherche la solution de ce problème sur une feuille on a exactement la même impression.

Du coup j'ai demandé sur les forum de maths anglais, mais les gars sont totalement incapables de répondre simplement à la question, ils partent dans tous les sens à celui qui étalera le plus ses connaissances hors-sujet...

[anapurna]

@anapurna:
Le problème de tout ce que tu proposes est que la situation géographique est fixée.
Alors, ça devient facile.
Mais, lui, il est dans un cas purement abstrait auquel correspond une multitude de situations géographiques différentes.
Donc avec des faces différentes, et une triangulation qui en découle.

je comprend pas bien.
tu veut dire qu'il a une liste d’éléments n'ayant pas une représentation physique et qu'il cherche à déterminer et optimiser leur position ?
je comprend bien ?
prenons un exemple on a une suite de composant électronique avec les liens interconnexion entre eux
et on veut en déduire leur implémentation ?
je suppose que cette liste est un graphe orienté (sens de courant et contact entre composants dans mon exemple)