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

https://fr.wikipedia.org/wiki/Graphe_planaire

À 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 (22)

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study h

2022

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have

IEEE COMPUTER SOC2022

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above

EPFL2019

Afficher plus

Personnes associées (6)

, , , , ,

Concepts associés (144)

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .

Afficher plus

Cours associés (91)

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

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

A first course in statistical network analysis and applications.

Afficher plus

Séances de cours associées (828)

Couvre les matrices, les applications linéaires, les espaces vectoriels et les fonctions bijectives.

Explore le produit scalaire des vecteurs, y compris les propriétés et les méthodes de calcul.

Explore les applications linéaires dans la représentation R2 et matricielle, y compris la base, les opérations et l'interprétation géométrique des transformations.

MOOCs associés (14)

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Introduction aux nombres complexes

Afficher plus