$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Mathématiques discrètes > Théorie des graphes >

Graphe planaire

Un graphe est dit planaire si on peut le représenter dans le plan de telle sorte que ses arêtes ne se croisent pas.

Il est assez facile de prouver qu'un graphe est planaire : il suffit de trouver une représentation dans le plan dont les arêtes ne se coupent pas! C'est en revanche beaucoup plus difficile de prouver qu'un graphe n'est pas planaire, car il faut pouvoir démontrer qu'aucune représentation du graphe ne convient!

Une fois représenté dans le plan, un graphe planaire nous donne des données supplémentaires : on dispose de ses sommets, de ses arêtes, mais aussi des faces (ou des régions) que ces arêtes délimitent. Par exemple, dans la représentation planaire précédente, on a 3 faces (ou régions) : celle coloriée en jaune, celle coloriée en bleu, et la face extérieure au graphe. Le résultat suivant, appellé relation d'Euler-Descartes, relie le nombre d'arêtes, de sommets et de faces d'un graphe planaire.

Théorème : Soit $G$ un graphe planaire possédant $s$ sommets, $a$ arêtes et $f$ faces. Alors $$s-a+f=2.$$

Cette relation permet de démontrer que certains graphes ne sont pas planaires. Elle entraine en effet qu'un graphe planaire ayant $s$ sommets possède au plus $3s-6$ arêtes. Le graphe complet à 5 sommets possède 10 arêtes, et 10>9. Il n'est pas planaire!

Consulter aussi...
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives