P comme (graphe) planaire

Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).

Un graphe « planaire » est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu’aucune arrête se croise. En revanche, si cette représentation n’existe pas, le graphe est considéré comme « non-planaire ». Attention, s’il existe une représentation non-planaire d’un graphe, cela ne permet pas de conclure que ce graphe est non-planaire, car cette représentation ne présage pas de l’existence d’une représentation planaire. C’est pourquoi il peut sembler plus facile de déterminer qu’un graphe est planaire, puisqu’il « suffit » de trouver une représentation planaire.

planaire1

Analyse visuelle

Pour déterminer si un graphe est non-planaire, il existe parfois des formules mathématiques. Ainsi, pour un graphe simple (voir S comme (graphe) simple) connexe (voir C comme Connexité) de plus de trois nœuds, un graphe planaire doit respecter la majoration suivante : a ≤ 3n – 6 (où a correspond au nombre d’arcs et n correspond au nombre de nœuds). Si le graphe ne respecte pas cette condition, le graphe est non-planaire.

planaire2

Analyse mathématique

Plus généralement, pour déterminer si un graphe est planaire ou non-planaire, il faut avoir recours à des algorithmes qui détectent la présence de certaines structures topologiques que l’on sait non-planaires (caractérisation de Kuratowski). A titre d’exemple, dans la figure ci-dessus, le graphe de droite est précisément une des structures topologiques recherchées. Ce graphe porte le doux nom de K: graphe complet (voir C comme (graphe) complet) à 5 sommets.

planaire3

Analyse algorithmique

Néanmoins, ce n’est pas parce que l’on sait qu’un graphe est planaire qu’il est pour autant facile de trouver une représentation planaire de ce graphe. Ainsi, vous pouvez essayer pour le graphe situé au centre de la figure ci-dessus (une réponse ici). Si vous n’avez pas trouvé, sachez que cette solution est pourtant considérée comme facile.

Pourquoi est-il important de déterminer si un graphe est planaire ou non ? Tout simplement parce que certains indicateurs sont influencés par ce caractère particulier. Par exemple, deux des indicateurs de Kansky, très utilisés en géographie des transports, sont influencés par ce caractère. Ainsi, l’indice γ, qui mesure la densité d’un graphe (voir D comme densité), vaut dans le cas général 2a/(n(n-1)) et pour un graphe planaire a/(3(n-2)). Quoi qu’il en soit, l’intérêt de déterminer si un graphe est planaire n’est pas forcément à chercher dans l’analyse de réseau stricto sensu. Les méthodes associées aux graphes planaires permettent notamment de résoudre des problèmes mathématiques très difficiles comme le théorème des quatre couleurs.

Billets liés : C comme (graphe) complet, C comme connexité, D comme densité, S comme (graphe) simple.

Retour au glossaire


Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *