| dbo:abstract
|
- 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. (fr)
- 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. (fr)
|
| prop-fr:contenu
|
- Un premier lemme est utile :
* Tout graphe planaire connexe peut s'obtenir en adjoignant des arêtes à un arbre connexe ayant les mêmes nœuds :
Un arbre est un graphe ne contenant qu'une unique face. On procède par récurrence sur f, le nombre de faces du graphe.
Supposons que le graphe ne possède qu'une unique face, le graphe est un arbre et la proposition est trivialement vérifiée. Supposons que la proposition est vraie pour f et montrons-la pour un graphe G à f + 1 faces. Le théorème de Jordan montre que s'il existe plusieurs faces, il existe une courbe de Jordan formée par des arêtes. Si l'on retranche une des arêtes A de la courbe au graphe G, les parties droite et gauche du complémentaire du graphe, qui formaient précédemment deux faces, n'en font plus qu'une et ce qui reste de la courbe de Jordan garantit que G est toujours connexe. Le graphe amputé de A vérifie les hypothèses de récurrence et s'obtient en adjoignant des arêtes à un arbre connexe. Ajouter la dernière arête A fournit le graphe initial.
* Formule d'Euler :
Démontrons la proposition tout d'abord pour un arbre, par récurrence sur le nombre n de ses nœuds. Si l'arbre ne contient qu'un unique nœud, il possède une face et aucune arête, la formule est vérifiée. On suppose que la formule est vraie pour n, montrons-la pour un arbre G contenant n + 1 nœuds. Comme l'arbre ne contient qu'une unique face, il contient au moins un nœud N connecté à une unique arête . L'arbre G privé de ce nœud et de l'arête adjacente est un arbre connexe contenant n nœuds, il vérifie l'hypothèse de récurrence. Ajouter le nœud N et l'arête associée correspond à ajouter un nœud et une arête, la formule d'Euler reste vraie pour G, ce qui termine cette première étape.
Démontrons maintenant la proposition pour un graphe connexe, par récurrence sur le nombre f de ses faces. Si f est égal à 1, la formule est vérifiée d'après la récurrence précédente. Supposons-la vraie pour tout graphe ayant f faces et montrons-la pour un graphe G ayant f + 1 faces. La récurrence du lemme montre qu'il est possible de retrancher une arête à G de manière que le nouveau graphe soit encore connexe et ait exactement f faces. La formule d'Euler est alors vérifiée par hypothèse de récurrence. Rajouter l'arête manquante ne modifie pas le nombre de nœuds, et incrémente de un le nombre d'arêtes et de faces. La formule d'Euler est encore vérifiée, ce qui termine la démonstration. (fr)
- Un premier lemme est utile :
* Tout graphe planaire connexe peut s'obtenir en adjoignant des arêtes à un arbre connexe ayant les mêmes nœuds :
Un arbre est un graphe ne contenant qu'une unique face. On procède par récurrence sur f, le nombre de faces du graphe.
Supposons que le graphe ne possède qu'une unique face, le graphe est un arbre et la proposition est trivialement vérifiée. Supposons que la proposition est vraie pour f et montrons-la pour un graphe G à f + 1 faces. Le théorème de Jordan montre que s'il existe plusieurs faces, il existe une courbe de Jordan formée par des arêtes. Si l'on retranche une des arêtes A de la courbe au graphe G, les parties droite et gauche du complémentaire du graphe, qui formaient précédemment deux faces, n'en font plus qu'une et ce qui reste de la courbe de Jordan garantit que G est toujours connexe. Le graphe amputé de A vérifie les hypothèses de récurrence et s'obtient en adjoignant des arêtes à un arbre connexe. Ajouter la dernière arête A fournit le graphe initial.
* Formule d'Euler :
Démontrons la proposition tout d'abord pour un arbre, par récurrence sur le nombre n de ses nœuds. Si l'arbre ne contient qu'un unique nœud, il possède une face et aucune arête, la formule est vérifiée. On suppose que la formule est vraie pour n, montrons-la pour un arbre G contenant n + 1 nœuds. Comme l'arbre ne contient qu'une unique face, il contient au moins un nœud N connecté à une unique arête . L'arbre G privé de ce nœud et de l'arête adjacente est un arbre connexe contenant n nœuds, il vérifie l'hypothèse de récurrence. Ajouter le nœud N et l'arête associée correspond à ajouter un nœud et une arête, la formule d'Euler reste vraie pour G, ce qui termine cette première étape.
Démontrons maintenant la proposition pour un graphe connexe, par récurrence sur le nombre f de ses faces. Si f est égal à 1, la formule est vérifiée d'après la récurrence précédente. Supposons-la vraie pour tout graphe ayant f faces et montrons-la pour un graphe G ayant f + 1 faces. La récurrence du lemme montre qu'il est possible de retrancher une arête à G de manière que le nouveau graphe soit encore connexe et ait exactement f faces. La formule d'Euler est alors vérifiée par hypothèse de récurrence. Rajouter l'arête manquante ne modifie pas le nombre de nœuds, et incrémente de un le nombre d'arêtes et de faces. La formule d'Euler est encore vérifiée, ce qui termine la démonstration. (fr)
|
| rdfs:comment
|
- 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. (fr)
- 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. (fr)
|
