INTRODUCTION LA THÉORIE DES GRAPHES Une approche par les problèmes

pages

Français

Documents

Écrit par
Léonard Euler

Publié par
sucun

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

sucun

Nombre de lectures

337

Langue

Français

Niveau: Secondaire, Lycée

exposé

INTRODUCTION À LA THÉORIE DES GRAPHES Une approche par les problèmes I. CHERCHER UN BON CHEMIN POUR RESOUDRE UN PROBLEME 1°) Problème n°1. Les ponts de la ville de Königsberg La ville de Königsberg (Prusse orientale) comptait 7 ponts, disposés selon la figure ci- contre. L'histoire veut que Léonard Euler, en visite dans cette ville, ait eu à résoudre le problème qui préoccupait fortement ses habitants : Est-il possible de trouver un circuit qui emprunte une fois et une seule chacun des sept ponts de la ville ? Quelques tentatives à la main ne laissent envisager aucune solution ; il s'agit d'aller plus loin que ce simple constat et d'apporter une réponse complète au problème . Pour cela, l'idée est de commencer par traduire l'énoncé du problème par un schéma : Chaque lieu de la ville est repéré par sa position géographique : N pour le nord de la ville ; S pour le sud de la ville, O pour l'ouest et I pour île . Chaque pont sera alors représenté par un « trait » reliant ces lieux entre eux. Cette modélisation s'appelle un graphe : Qu'est-ce qu'un graphe ? C'est un ensemble de sommets et de liens entre 2 sommets que l'on appelle arêtes. La traduction du problème de départ en termes de propriétés du graphe est alors : «Peut-on circuler sur le graphe à partir d'un sommet en empruntant une fois et une seule chaque arête ? » On va oublier pour un temps la situation géographique et s'intéresser à l'objet mathématique qu'est le graphe

résolution du problème de königsberg revenons

propriétés relatives aux degrés des sommets

dominos de la boîte sur la table

degré pair

Voir

Publié par

sucun

Nombre de lectures

337

Langue

Français

Exposé collège

INTRODUCTION À LA THÉORIE DES GRAPHES Une approche par les problèmes

I. CHERCHER UN BON CHEMIN POUR RESOUDRE UN PROBLEME

1°) Problème n°1. Les ponts de la ville de Königsberg

La ville de Königsberg (Prusse orientale) comptait 7 ponts, disposés selon la figure ci-contre. L’histoire veut que Léonard Euler, en visite dans cette ville, ait eu à résoudre le problème qui préoccupait fortement ses fig 1 habitants : Est-il possible de trouver un circuit qui emprunte une fois et une seule chacun des sept ponts de la ville ?

Quelques tentatives à la main ne laissent envisager aucune solution ; il s’agit d’aller plus loin que ce simple constat et d’apporter une réponse complète au problème . Pour cela, l’idée est de commencer par traduire l’énoncé du problème par un schéma : Chaque lieu de la ville est repéré par sa position géographique : N pour le nord de la ville ; S pour le sud de la ville, O pour l’ouest et I pour île . Chaque pont sera alors représenté par un « trait » reliant ces lieux entre eux . Cette modélisation s’appelle un graphe : Qu’est-ce qu’un graphe ? C’est un ensemble de ts et de liens e ts somme ntre 2 somme que l’on appelle arêtes . N La traduction du problème de départ en termes de propriétés du graphe est alors : «Peut-on circuler sur le graphe à partir d’un sommet en empruntant une fois et une seule chaque arête ? » OI On va oublier pour un temps la situation géographique et s’intéresser à l’objet u’est le ra mathématique q g phe S ig 2 2°) Définitions et vocabulaire élémentaires Graphe : Un graphe est constitué d’un ensemble non vide d’éléments appelés sommets et d’un ensemble de paires (il ne s'agit pas de couples) de divers sommets, appelées arêtes. (ou encore : Un graphe est un ensemble non vide de sommets et d’arêtes joignant deux sommets.) Exemple : D fi uGn= {g{rAa,pBh,eC,D},{{A,B},{B,C},{A,C},{C,D}}} est C g 3 Remarque : cette écriture ensembliste est destinée aux enseignants, et n’est pas à donner aux élèves.

MM - Théorie élémentaire des graphes page 1/19

Remarque :Dans d’autres cas, deux sommets peuvent être liés par plusieurs arêtes : on les appelle arêtes parallèles. Une arête peut avoir ses extrémités confondues : on parle de boucle. Dans ces deux cas, le graphe considéré est un multigraphe. Exemple de multigraphe : B fig 4 C Ici, comme dans le cadre du programme de Terminale ES le terme graphe désignera indifféremment un graphe ou un multigraphe. De plus, dans cet exposé, tous les graphes considérés seront finis. D egré : Le degré d’un sommet est le nombre d’arêtes ayant ce sommet pour extrémité. (attention : une boucle augmente de deux le degré d’un sommet). On parle aussi de rang, ou d’ordre. Exemple : dans le graphe de la figure 2 , le degré de N est trois. I ncidente : Une arête ayant un sommet pour extrémité est dite incidente à ce sommet. Une arête pourra être désignée par ses extrémités s'il n'y a pas d'ambiguïté ; dans le cas contraire on codifie : a N Exemples : a Dans la fig 3 , on peut noter : [BC] ( ou a 3 eDnacnosr lea : f{igB ,2C :} I)l faut coder les arêtes comme O a 7 I indiqué sur la figure 5 car il y a des arêtes parallèles : a 2 désigne alors sans ig té a 5 a 4 amb uï une des deux arêtes reliant N et I. a 6 S Fig 5

Dans un graphe : Une chaîne est une suite alternée de sommets et d'arêtes. Un cycle est une chaîne dont les arêtes sont distinctes et dont l'origine et l'extrémité sont confondues. Exemple (fig 5) : O, a 1 , N, a 2 , I est une chaîne d'extrémités O et I O, a 1, N, a 2 , I, a 7 , O est un cycle Remarque : Un cycle n'a ni origine ni extrémité. On peut donc lister ses composantes à partir de n'importe lequel de ses sommets : I, a 7 ; O ; a 1 , N, a 2 , I désigne le même cycle que le précédent. Une chaîne eulérienne est une chaîne empruntant une fois et une seule chaque arête du graphe. Un cycle eulérien est un cycle empruntant une fois et une seule chaque arête du graphe. Le problème 1 peut maintenant être posé en ces termes : existe-t-il une chaîne ou un cycle eulérien dans le graphe de la figure 2 ? 3°) Le théorème d'EULER : a) Un graphe connexe 1 admet une chaîne eulérienne si et seulement si tous ses sommets sont de degré pair sauf éventuellement 2 .

1 Un graphe est connexe si pour toute paire de sommets du graphe il existe une chaîne les reliant.

MM - Théorie élémentaire des graphes page 2/19

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

INTRODUCTION LA THÉORIE DES GRAPHES Une approche par les problèmes

YouScribe

Le catalogue

Le service

Les conditions