Famille de Petersen

thumb|300px|La famille de Petersen. Le graphe complet K6 est en haut de l'illustration, et le graphe de Petersen est en bas. Les liaisons bleues indiquent des transformations Δ-Y ou Y-Δ entre les graphe s de la famille. En mathématiques, et plus précisément en théorie des graphes, la famille de Petersen est un ensemble de sept graphes non orientés contenant le graphe de Petersen et le graphe complet K6. Cette famille a été découverte et étudiée par le mathématicien danois Julius Petersen. La forme des transformations Δ-Y et Y-Δ utilisée pour définir la famille de Petersen est la suivante : Si un graphe G contient un sommet s ayant exactement trois voisins (donc trois arêtes partant de lui), la transformation Y-Δ de G en s est le graphe obtenu en supprimant s (et les trois arêtes qui en partent) de G et en ajoutant une nouvelle arête entre chaque couple de voisins de s. Si un graphe H contient un triangle rst, la transformation Δ-Y de H en rst est le graphe formé en supprimant les arêtes rs, st, et rt de H, et en ajoutant un nouveau sommet x et les trois arêtes rx, sx et tx. (le nom de ces transformations provient de la forme en Δ d'un triangle du graphe, et de la forme en Y d'un sommet de degré 3). Bien que ces opérations puissent en principe conduire à des multigraphes, cela ne se produit pas pour les graphes de la famille de Petersen. Ces transformations conservant le nombre d'arêtes d'un graphe, on ne peut, en les utilisant, construire qu'un nombre fini de graphes (ou de multigraphes) à partir d'un graphe initial donné. La famille de Petersen est définie comme l'ensemble des graphes qui peuvent être atteint à partir du graphe de Petersen par combinaison de transformations Δ-Y et Y-Δ. Parmi les sept graphes de la famille, outre le graphe de Petersen, on trouve le graphe complet K6 à six sommets, le graphe à huit sommets obtenu en supprimant une arête du graphe biparti complet K4,4, et le graphe complet triparti à sept sommets K3,3,1.

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

Publications associées (1)

Concepts associés (9)

Information Processing and Structure of Dynamical Networks

Ali Ajdari Rad

Networks are everywhere and we are confronted with many networks in our daily life. Networks such as Internet, World Wide Web, social, biological and economical networks have been subject to extensive studies in the last decade. The volume of publications ...

EPFL2011

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K_5 or K_3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

Linkless embedding

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.