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
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
