Worldlex Wiki En théorie des graphes , un graphe cyclique ou graphe circulaire est un graphe constitué d'un seul cycle , ou en d'autres termes, d'un certain nombre de sommets (au moins 3, si le graphe est simple ) connectés en chaîne fermée. Le graphe cyclique à n sommets est appelé C n . Le nombre de sommets dans C n est égal au nombre d' arêtes , et chaque sommet a un degré 2 ; c'est-à-dire que chaque sommet a exactement deux arêtes incidentes avec lui.
Terminologie
Il existe de nombreux synonymes pour « graphe cyclique ». Parmi ceux-ci, on trouve notamment « graphe cyclique simple » et « graphe cyclique » , bien que ce dernier terme soit moins souvent utilisé, car il peut également désigner des graphes qui ne sont tout simplement pas acycliques . Parmi les théoriciens des graphes, on utilise aussi souvent cycle , polygone ou n -gone . Le terme n -cycle est parfois utilisé dans d'autres contextes.
Un cycle avec un nombre pair de sommets est appelé un cycle pair ; un cycle avec un nombre impair de sommets est appelé un cycle impair .
Propriétés
Un graphique cyclique est :
- Colorable à 2 arêtes , si et seulement si elle a un nombre pair de sommets
- 2-régulier
- Un graphe est bipartite si et seulement s'il possède un nombre pair de sommets. Plus généralement, un graphe est bipartite si et seulement s'il ne possède pas de cycles impairs ( Kőnig , 1936).
- Connecté
- Eulérien
- Hamiltonien
- Un graphique de distance unitaire
En outre:
- Les graphes cycliques pouvant être dessinés comme des polygones réguliers , les symétries d'un n -cycle sont les mêmes que celles d'un polygone régulier à n côtés, le groupe diédrique d'ordre 2n . En particulier, il existe des symétries prenant n'importe quel sommet vers n'importe quel autre sommet, et n'importe quelle arête vers n'importe quelle autre arête, donc le n -cycle est un graphe symétrique .
De la même manière que les graphes platoniciens , les graphes cycliques forment les squelettes des dièdres . Leurs duals sont les graphes dipolaires , qui forment les squelettes des hosoèdres .
Graphique de cycle dirigé
Un graphe cyclique orienté est une version orientée d'un graphe cyclique, avec toutes les arêtes orientées dans la même direction.
Dans un graphe orienté , un ensemble d'arêtes contenant au moins une arête (ou arc ) de chaque cycle orienté est appelé un ensemble d'arcs de rétroaction . De même, un ensemble de sommets contenant au moins un sommet de chaque cycle orienté est appelé un ensemble de sommets de rétroaction .
Un graphe cyclique orienté possède un degré entrant uniforme 1 et un degré sortant uniforme 1.
Les graphes de cycles dirigés sont des graphes de Cayley pour les groupes cycliques (voir par exemple Trevisan).