Graphe asymétrique

Graphe asymétrique

En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d'automorphismes du est d'ordre 1. C'est donc un graphe n'admettant aucun automorphisme autre que l'identité.

Le plus petit graphe asymétrique est le graphe singleton, qui est également un graphe symétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets[1]. Il existe 8 graphes asymétrique distincts à isomorphisme près à l'ordre 6, 152 à l'ordre 7, 3 696 à l'ordre 8, 135 004 à l'ordre 9, 7 971 848 à l'ordre 10 et 805 364 776 à l'ordre 11[2].

Si on s'intéresse aux graphes cubiques, le plus petit graphe asymétrique est le graphe de Frucht. Il a 12 sommets.

Sont également des graphes asymétrique le graphe de Kittell, le graphe 4-chromatique de Heawood et le graphe de Walther.

Références

  1. ↑ (en) Eric W. Weisstein, Identity Graph (MathWorld)
  2. ↑ N. J. A. Sloane Number of asymmetric (not necessarily connected) graphs with n nodes. The On-Line Encyclopedia of Integer Sequences (id:A003400).

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Graphe de Frucht — Le graphe de Frucht Nombre de sommets 12 Nombre d arêtes 18 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Graphe singleton — Représentation du graphe singleton. Nombre de sommets 1 Nombre d arêtes 0 Distribution des degrés 0 régulier Rayon 0 …   Wikipédia en Français

  • Graphe de Kittell — Représentation du graphe de Kittell. Nombre de sommets 23 Nombre d arêtes 63 Distribution des degrés 5 (15 sommets) 6 (5 sommets) 7 (3 sommets) Rayon …   Wikipédia en Français

  • Graphe 4-chromatique de Heawood — Nombre de sommets 25 Nombre d arêtes 69 Distribution des degrés 5 (17 sommets) 6 (3 sommets) 7 (5 sommets) Rayon 3 Diamètre 5 Maille 3 Automorphismes 1 ({id}) …   Wikipédia en Français

  • Graphe de Walther — Représentation du graphe de Walther. Nombre de sommets 25 Nombre d arêtes 31 Distribution des degrés 1 (3 sommets) 2 (7 sommets) 3 (15 sommets) Rayon …   Wikipédia en Français

  • Graphe cubique — En théorie des graphes, un graphe cubique est un graphe régulier de degré 3. Exemples Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non planaire. Le graphe de Petersen est… …   Wikipédia en Français

  • Relation binaire — En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est caractérisée par un sous ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la …   Wikipédia en Français

  • Problème du voyageur de commerce — Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce consiste, étant donné un… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Probleme du voyageur de commerce — Problème du voyageur de commerce Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce …   Wikipédia en Français

Share the article and excerpts

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