Cycle (théorie des graphes) - Cycle (graph theory)
En théorie des graphes , un cycle dans un graphe est une piste non vide dans laquelle les seuls sommets répétés sont les premier et dernier sommets. Un cycle dirigé dans un graphe orienté est une trace dirigée non vide dans laquelle les seuls sommets répétés sont les premier et dernier sommets.
Un graphe sans cycles est appelé graphe acyclique . Un graphe orienté sans cycles orientés est appelé un graphe orienté acyclique . Un graphe connexe sans cycles s'appelle un arbre .
Définitions
Circuit, cycle
- Un circuit est un chemin non vide dans lequel le premier sommet est égal au dernier sommet ( chemin fermé ).
- Soit G = ( V , E , ϕ ) un graphe. Un circuit est un chemin non vide ( e 1 , e 2 ,…, e n ) avec une séquence de sommets ( v 1 , v 2 ,…, v n , v 1 ) .
- Un cycle ou circuit simple est un circuit dans lequel le seul sommet répété est le premier / dernier sommet.
- La longueur d'un circuit ou d'un cycle est le nombre d'arêtes impliquées.
Circuit dirigé, cycle
- Un circuit dirigé est un chemin dirigé non vide dans lequel le premier sommet est égal au dernier sommet.
- Soit G = ( V , E , ϕ ) un graphe orienté. Un circuit réalisé est une piste dirigée non vide ( e 1 , e 2 , ..., e n ) avec une séquence de sommet ( v 1 , v 2 , ..., v n , v 1 ) .
- Un cycle dirigé ou circuit dirigé simple est un circuit dirigé dans lequel le seul sommet répété est le premier / dernier sommet.
Cycles sans accords
Un cycle sans accord dans un graphe, également appelé trou ou cycle induit, est un cycle tel qu'aucun sommet du cycle n'est connecté par une arête qui n'appartient pas elle-même au cycle. Un anti-trou est le complément d'un trou de graphe. Des cycles sans accords peuvent être utilisés pour caractériser des graphes parfaits : par le théorème du graphe parfait fort , un graphe est parfait si et seulement si aucun de ses trous ou anti-trous n'a un nombre impair de sommets supérieur à trois. Un graphe d'accords , un type spécial de graphe parfait, n'a pas de trous de taille supérieure à trois.
La circonférence d'un graphique est la longueur de son cycle le plus court; ce cycle est nécessairement sans accord. Les cages sont définies comme les plus petits graphiques réguliers avec des combinaisons données de degré et de circonférence.
Un cycle périphérique est un cycle dans un graphe avec la propriété que tous les deux bords non sur le cycle peuvent être reliés par un chemin dont les sommets intérieurs évitent le cycle. Dans un graphe qui n'est pas formé en ajoutant une arête à un cycle, un cycle périphérique doit être un cycle induit.
Espace vélo
Le terme cycle peut également désigner un élément de l' espace cyclique d'un graphe. Il existe de nombreux espaces de cycle, un pour chaque champ de coefficient ou anneau. Le plus courant est l' espace de cycle binaire (généralement appelé simplement l' espace de cycle ), qui se compose des ensembles d'arêtes qui ont un degré pair à chaque sommet; il forme un espace vectoriel sur le champ à deux éléments . Selon le théorème de Veblen , chaque élément de l'espace cyclique peut être formé comme une union disjointe d'arêtes de cycles simples. Une base de cycle du graphe est un ensemble de cycles simples qui forme une base de l'espace de cycle.
En utilisant des idées de topologie algébrique , l'espace de cycle binaire se généralise aux espaces vectoriels ou aux modules sur d'autres anneaux tels que les entiers, les nombres rationnels ou réels, etc.
Détection de cycle
L'existence d'un cycle dans les graphes orientés et non dirigés peut être déterminée par si la recherche en profondeur d'abord (DFS) trouve une arête qui pointe vers un ancêtre du sommet actuel (elle contient une arête arrière ). Tous les bords arrière ignorés par DFS font partie de cycles. Dans un graphe non orienté, l'arête du parent d'un nœud ne doit pas être comptée comme une arête arrière, mais trouver tout autre sommet déjà visité indiquera une arête arrière. Dans le cas des graphes non orientés, seul un temps O ( n ) est nécessaire pour trouver un cycle dans un graphe à n -vertex, car au plus n - 1 arêtes peuvent être des arêtes d'arbre.
De nombreux algorithmes de tri topologique détecteront également les cycles, car ce sont des obstacles à l'existence de l'ordre topologique. De plus, si un graphe orienté a été divisé en composants fortement connectés , les cycles n'existent qu'à l'intérieur des composants et non entre eux, car les cycles sont fortement connectés.
Pour les graphes orientés, des algorithmes basés sur des messages distribués peuvent être utilisés. Ces algorithmes reposent sur l'idée qu'un message envoyé par un sommet dans un cycle reviendra à lui-même. Les algorithmes de détection de cycle distribué sont utiles pour traiter des graphiques à grande échelle à l'aide d'un système de traitement de graphique distribué sur un cluster d'ordinateurs (ou superordinateur).
Les applications de la détection de cycle incluent l'utilisation de graphiques d' attente pour détecter les blocages dans les systèmes concurrents.
Couvrir les graphiques par cycles
Dans son article de 1736 sur les sept ponts de Königsberg , largement considéré comme la naissance de la théorie des graphes, Leonhard Euler a prouvé que, pour qu'un graphe non dirigé fini ait une promenade fermée qui visite chaque arête exactement une être connecté sauf pour les sommets isolés (c'est-à-dire que toutes les arêtes sont contenues dans un composant) et ont un degré pair à chaque sommet. La caractérisation correspondante pour l'existence d'une marche fermée visitant chaque arête exactement une fois dans un graphe orienté est que le graphe est fortement connecté et a un nombre égal d'arêtes entrantes et sortantes à chaque sommet. Dans les deux cas, la marche qui en résulte est connue sous le nom de cycle d' Euler ou de visite d'Euler. Si un graphe non orienté fini a un degré pair à chacun de ses sommets, qu'il soit ou non connecté, alors il est possible de trouver un ensemble de cycles simples qui, ensemble, couvrent chaque arête exactement une fois: c'est le théorème de Veblen . Lorsqu'un graphe connexe ne remplit pas les conditions du théorème d'Euler, une marche fermée de longueur minimale couvrant chaque arête au moins une fois peut néanmoins être trouvée en temps polynomial en résolvant le problème d'inspection d'itinéraire .
Le problème de trouver un seul cycle simple qui couvre chaque sommet exactement une fois, plutôt que de couvrir les arêtes, est beaucoup plus difficile. Un tel cycle est connu sous le nom de cycle hamiltonien , et déterminer s'il existe est NP-complet . De nombreuses recherches ont été publiées concernant des classes de graphes dont on peut garantir qu'elles contiennent des cycles hamiltoniens ; un exemple est le théorème d'Ore selon lequel un cycle hamiltonien peut toujours être trouvé dans un graphe pour lequel chaque paire de sommets non adjacents a des degrés totalisant au moins le nombre total de sommets dans le graphe.
La conjecture de double couverture de cycle stipule que, pour chaque graphe sans pont , il existe un multiset de cycles simples qui couvre chaque arête du graphe exactement deux fois. Prouver que cela est vrai (ou trouver un contre-exemple) reste un problème ouvert.
Classes de graphes définies par cycles
Plusieurs classes importantes de graphes peuvent être définies ou caractérisées par leurs cycles. Ceux-ci inclus:
- Graphe bipartite , un graphe sans cycles impairs (cycles avec un nombre impair de sommets).
- Cactus graph , un graphe dans lequel chaque composant biconnecté non trivial est un cycle
- Graphique de cycle , un graphique qui se compose d'un seul cycle.
- Graphe chordal , un graphe dans lequel chaque cycle induit est un triangle
- Graphe acyclique dirigé , un graphe orienté sans cycles
- Graphique à ligne parfaite , un graphique dans lequel chaque cycle impair est un triangle
- Graphique parfait , un graphique sans cycles induits ou leurs compléments de longueur impaire supérieure à trois
- Pseudoforêt , un graphe dans lequel chaque composante connexe a au plus un cycle
- Graphique étranglé , un graphique dans lequel chaque cycle périphérique est un triangle
- Graphe fortement connecté , un graphe orienté dans lequel chaque arête fait partie d'un cycle
- Graphe sans triangle , un graphe sans cycles à trois sommets
Voir également
- Espace vélo
- Base de cycle
- Détection de cycle dans une séquence de valeurs de fonction itérées
Les références
- Balakrishnan, VK (2005). Schéma de la théorie de Schaum et problèmes de la théorie des graphes ([Nachdr.] Ed.). McGraw – Hill. ISBN 978-0070054899 .
- Bender, Edward A .; Williamson, S. Gill (2010). Listes, décisions et graphiques. Avec une introduction à la probabilité .