° Graphe planaire. – Graphe tracé dans un plan de telle sorte que deux arêtes quelconques se rencontrent uniquement en leurs extrémités et donc ne se coupent pas. Le graphe associé aux ponts de Königsberg est planaire. 

Dudeney, en 1917, a proposé un problème d'échanges d'oies et de renards qui peut être résolu par un graphe planaire. Sur le diagramme de gauche, trois oies sont placées sur les cases 1, 2 et 3. Trois renards sont sur les cases 10, 11, 12. Échangez les oies contre les renards en suivant les lignes qui relient les cases. 

À droite, le graphe planaire représente la situation.

Ce problème est analogue à celui de l'échange des cavaliers, sauf que le tablier est différent. Les solutions sur un échiquier réduit 3 × 3, 3 × 4 ou 3 × 5 peuvent être représentées par un graphe planaire, mais pas pour un échiquier de plus grande taille.

© Charles-É. Jean  

Index : P