Graphe planaire extérieur

vignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire. Les graphes planaires extérieurs furent étudiés et nommés en 1967 par et Frank Harary, en relation avec le problème de déterminer la planarité de graphes formés à l'aide d'un couplage parfait entre deux copies d'un graphe donné (par exemple, beaucoup des graphes de Petersen généralisés sont formés de cette manière à partir d'un cycle). Ils démontrèrent que lorsque le graphe de base est biconnexe (c'est-à-dire lorsque la suppression d'un sommet quelconque laisse le graphe connecté), le graphe ainsi construit est planaire si et seulement si le graphe de base est planaire extérieur et le couplage forme une permutation diédrale de son cycle extérieur. Les graphes planaires extérieurs possèdent des caractérisations par graphes exclus analogues à celles des graphes planaires données par les théorèmes de Kuratowski et de Wagner : un graphe est planaire extérieur si et seulement s'il ne contient pas de subdivision du graphe complet K4 ou du graphe biparti complet K2,3. De même, un graphe est planaire extérieur si et seulement s'il ne contient ni K4, ni K2,3 comme mineur, c'est-à-dire comme graphe obtenu en contractant et en supprimant des arêtes. Un graphe sans triangle est planaire extérieur si et seulement s'il ne contient pas de subdivision de K2,3. Un graphe planaire extérieur est biconnexe si et seulement si la face extérieure du graphe forme un cycle simple (sans répétition de sommets).

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

Concepts associés (36)

Cours associés (2)

Séances de cours associées (22)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

FIN-406: Macrofinance

This course provides students with a working knowledge of macroeconomic models that explicitly incorporate financial markets. The goal is to develop a broad and analytical framework for analyzing the

En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières, notamment en utilisant la décomposition arborescente. Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée.

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.

Part des revenus du travail FIN-406: Macrofinance

Analyse un modèle macroéconomique axé sur la part du revenu du travail et les effets des chocs de productivité sur le PIB, la consommation, l’investissement et les cours des actions.

Théorie des probabilités : le théorème de Markov MATH-467: Probabilistic methods in combinatorics

Explore le théorème de Markov, la liaison de Chernoff et les fondamentaux de la théorie des probabilités, y compris une bonne coloration, des graphiques à 2 couleurs et des événements rares.

Méthodes probabilistes en combinatoire MATH-467: Probabilistic methods in combinatorics

Couvre les méthodes probabilistes en combinatoire, les bords monochromatiques, les graphiques à 2 couleurs et les bons 2 couleurs.