Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Peripheral cycle
Résumé
In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
A peripheral cycle in a graph can be defined formally in one of several equivalent ways:
is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges and in , there exists a path in that starts with , ends with , and has no interior vertices belonging to .
is peripheral if it is an induced cycle with the property that the subgraph formed by deleting the edges and vertices of is connected.
If is any subgraph of , a bridge of is a minimal subgraph of that is edge-disjoint from and that has the property that all of its points of attachments (vertices adjacent to edges in both and ) belong to . A simple cycle is peripheral if it has exactly one bridge.
The equivalence of these definitions is not hard to see: a connected subgraph of (together with the edges linking it to ), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in .
Peripheral cycles appear in the theory of polyhedral graphs, that is, 3-vertex-connected planar graphs. For every planar graph , and every planar embedding of , the faces of the embedding that are induced cycles must be peripheral cycles. In a polyhedral graph, all faces are peripheral cycles, and every peripheral cycle is a face. It follows from this fact that (up to combinatorial equivalence, the choice of the outer face, and the orientation of the plane) every polyhedral graph has a unique planar embedding.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.