Ê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
Graphe planaire
Résumé
Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul.
Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
1)
2)
3)
4)
Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.
C'est un graphe complet à quatre sommets (K4). Il est planaire : si on déplace le sommet 4 dans le triangle 1 2 3, on constate qu'il n'y a plus d'intersection d'arêtes.
C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.
C'est un graphe biparti complet K3,3 à 6 sommets, 3 d'entre eux se connectant aux trois autres. Il n'est pas planaire.
En fait, K5 et K3,3 sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.
vignette|Le graphe des pays du monde reliés par un arête s'ils sont limitrophes n'est pas planaire car il possède une expansion de K5 parmi ses sous-groupes partiels.
Le mathématicien polonais Kazimierz Kuratowski a établi en 1930 la caractérisation suivante des graphes planaires :
Un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphe partiel qui est une expansion de K5 (le graphe complet à 5 sommets) ou K3,3 (le graphe complet biparti à 3+3 sommets).
L'expansion (ou subdivision) d'un graphe est le résultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arêtes (par exemple, transformation de l'arête •——• en •—•—•).
Quelques années plus tard le mathématicien allemand Klaus Wagner en donna une caractérisation semblable :
Un graphe fini est planaire si et seulement s'il ne compte pas K5 ou K3,3 parmi ses mineurs.
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.
Proximité ontologique
Cours associés (29)
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
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
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
Personnes associées (104)