Trace de graphes

Trace de graphes

Tracé de graphes

En théorie des graphes, le tracé de graphes s'applique à une topologie et géométrie pour produire une représentation à deux ou trois dimensions des graphes. 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.

Sommaire

Méthodes

Les graphes sont généralement représentés en images en utilisant des points pour représenter les sommets, et des arcs pour représenter les arêtes entre les sommets reliés. Des flèches peuvent être utilisées pour montrer l'orientation des graphes orientés. 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 arrêtes impacte la compréhensibilité, l'usabilité, le coût de fabrication et l'esthétique.

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

  • force-based layout: gradient-descent minimization of an energy function based on physical metaphors.
  • spectral layout: layout basé sur une fonction energie qui est amenable à de la minimisation globale basé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 symmetries dans le graphe.
  • dessins arborescents : montrent un arbre-like formation, utile pour les arbres (i.e. les graphes sans cycles)
  • dessins hierarchiques : 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 (the complete graph with 4 vertices) can be drawn with or without overlapping edges (move one of the corners to the outside)

Il n'y a pas de "meilleur" layout — différentes manière 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'entrecoupants. Alors que certains graphes ne peuvent être traçé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 croisement que possible.

Voir aussi

Références

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

Ce document provient de « Trac%C3%A9 de graphes ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Trace de graphes de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Tracé de graphes — En théorie des graphes, le tracé de graphes s applique à une topologie et géométrie pour produire une représentation à deux ou trois dimensions des graphes. Le tracé de graphes est utile à des applications telles que la conception de circuits… …   Wikipédia en Français

  • GRAPHES (THÉORIE DES) — On appelle théorie des graphes une classe de problèmes plus ou moins bien résolus. Leur résolution suscite chez les mathématiciens, en particulier à l’étranger, un engouement sans cesse croissant. Claude Berge, dans le discours inaugural des… …   Encyclopédie Universelle

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

  • Théorie spectrale des graphes — La théorie spectrale des graphes s intéresse aux rapports entre le spectre d un graphe et ses propriétés, et fait partie de la théorie algébrique des graphes. Un graphe peut être représenté par plusieurs matrices, et les valeurs propres d une… …   Wikipédia en Français

  • Pierre Rosenstiehl — en 2002 (photo Hubert de Fraysseix) Pierre Rosenstiehl, né en 1933, est un mathématicien français à l École des Hautes Études en Sciences Sociales de Paris. Il est également membre de l Oulipo et Chevalier de la Légion d honneur …   Wikipédia en Français

  • traceur — traceur, euse [ trasɶr, øz ] n. • 1582; de tracer 1 ♦ Techn. Spécialiste exécutant des tracés, ou chargé des opérations de traçage et d ajustage. Personne qui établit le tracé d un parcours de compétition ou d une piste de ski. 2 ♦ N. m. (1958)… …   Encyclopédie Universelle

  • Force-based layout — Les algorithmes de dessin basé sur les forces (Force based ou Force directed algorithms) permettent de positionner les nœuds d un graphe pour faciliter sa visualisation en utilisant un système de force appliqués entre les nœuds et les arcs.… …   Wikipédia en Français

  • Calculatrices Graphiques Texas Instruments — La société Texas Instruments diffuse depuis 1990 des calculatrices graphiques, utilisées aussi bien par les lycéens que les ingénieurs. Toutes ces calculatrices ont les caractéristiques communes suivantes : calculs numériques de base, dont… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”