AccueilđŸ‡«đŸ‡·Chercher

Tracé de graphes

En théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique.

Types de tracés

Les graphes sont gĂ©nĂ©ralement reprĂ©sentĂ©s en utilisant des points, disques ou boites pour reprĂ©senter les sommets, et des courbes ou des segments pour reprĂ©senter les arĂȘtes. Pour les graphes orientĂ©s, on utilise habituellement ses flĂšches en bout d'arĂȘte pour reprĂ©senter l'orientation. Cette reprĂ©sentation graphique ne doit pas ĂȘtre confondue avec le graphe lui-mĂȘme (la structure abstraite et non graphique). Des dessins trĂšs diffĂ©rents peuvent correspondre au mĂȘme graphe. La seule chose qui compte vraiment est le nombre d'arĂȘtes entre chaque paire de sommets. En pratique, cependant l'arrangement de ces nƓuds et arĂȘtes influence la comprĂ©hensibilitĂ©, l'usabilitĂ©, le coĂ»t de fabrication et l'esthĂ©tique.

D'autres exemples de conventions sont la représentation par intersection et les représentations de la matrice d'adjacence.

MĂ©thodes

Fondées sur ces concepts et problématiques, différentes stratégies de dessin de graphes existent, telles que:

  • Layout dirigĂ© par les forces : minimisation par descente de gradient d'une fonction d'Ă©nergie, inspirĂ© par une mĂ©taphore physique.
  • spectral layout: layout basĂ© sur une fonction Ă©nergie qui est amenable Ă  de la minimisation globale fondĂ©e sur des techniques d'algĂšbre linĂ©aire.
  • orthogonal layout: layout avec des arcs courant horizontalement et verticalement, avec des approches pour rĂ©duire le nombre d'arcs s'entrecoupant ainsi que la superficie. Ils sont d'un grand intĂ©rĂȘt dans le domaine de VLSI et conception de PCB .
  • symmetric layout: ils essayent de trouver les groupes de symĂ©tries dans le graphe.
  • dessins arborescents : techniques spĂ©cialisĂ©es pour le tracĂ© d'arbre.
  • dessins hiĂ©rarchiques : essayent de trouver une source et un puits dans un graphe orientĂ© et d'arranger les nƓuds en strates en ayant le plus d'arcs commençant vers la source et suivant la direction du puits.

Dans certaines applications de tracĂ© de graphes, il est important de formellement spĂ©cifier la mise en Ɠuvre et la vĂ©rification formelle de ces procĂ©dures.

MĂ©triques

K4 (le graphe complet d'ordre 4) peut ĂȘtre dessinĂ© avec ou sans arcs croisĂ©s (en dĂ©plaçant l'un des sommets Ă  l'intĂ©rieur du triangle formĂ© par les trois autres)

Il n'y a pas de « meilleur Â» tracĂ© — diffĂ©rentes maniĂšres d'afficher un graphe montrent diffĂ©rentes caractĂ©ristiques. Une mĂ©trique d'un algorithme de tracĂ© de graphes est le nombre d'arcs s'entrecoupant. Alors que certains graphes ne peuvent ĂȘtre tracĂ©s sans que les arcs s'entrecoupent, certains graphes peuvent l'ĂȘtre, on les appelle des graphes planaires. D'aprĂšs cette mĂ©trique, les « bons Â» algorithmes tracent des graphes avec aussi peu de croisements que possible. Le nombre minimal de croisements d'un graphe possible mesure cette propension.

Voir aussi

Articles connexes

Bibliographie

  • Giuseppe Di Battista, Peter Eades (en), Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
  • Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). www.cs.brown.edu
  • Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. www.cs.brown.edu

Liens externes

Exemples de layouts de graphes:

Une collection de layouts de graphes animés interactivement:

Outils de tracés de layout de graphes

Formats de graphes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.