| dbo:abstract
|
- En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile: « Arête-transitif » signifie que pour toute paire d'arêtes et , il existe un automorphisme qui envoie l'une sur l'autre, donc tel que , alors que « arc-transitif » demande qu'en plus et que, pour un autre automorphisme , on ait . Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles. Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif. (fr)
- En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile: « Arête-transitif » signifie que pour toute paire d'arêtes et , il existe un automorphisme qui envoie l'une sur l'autre, donc tel que , alors que « arc-transitif » demande qu'en plus et que, pour un autre automorphisme , on ait . Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles. Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif. (fr)
|
| rdfs:comment
|
- En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif. (fr)
- En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif. (fr)
|
