Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CAHIERS DE LA CRM Introduction à la théorie des graphes Didier Müller CAHIER NO

CAHIERS DE LA CRM Introduction à la théorie des graphes Didier Müller CAHIER NO 6 COMMISSION ROMANDE DE MATHÉMATIQUE Table des matières Avant-propos 1 But de ce fascicule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Logiciels pour les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Pour aller plus loin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Graphes non orientés 3 1.1 Premières déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Représentation graphique . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Quelques types de graphes . . . . . . . . . . . . . . . . . . . . . 3 1.1.3 Exemple d’utilisation d’un graphe pour résoudre un problème . . 4 1.1.4 Graphes d’intervalles . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Graphe partiel et sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Degré d’un sommet . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.2 Degré d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Chaînes et cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Graphes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Graphes hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Couplages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.1 Calcul d’un couplage maximum . . . . . . . . . . . . . . . . . . 13 1.8 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.9 Représentations non graphiques d’un graphe . . . . . . . . . . . . . . . . 15 1.9.1 Matrice d’adjacences . . . . . . . . . . . . . . . . . . . . . . . . 15 1.9.2 Listes d’adjacences . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.10 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.10.1 Codage de Prüfer . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.11 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.11.1 Arbre couvrant de poids minimum . . . . . . . . . . . . . . . . . 20 1.12 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.12.1 Encadrement du nombre chromatique . . . . . . . . . . . . . . . 21 1.12.2 Algorithme de coloration de Welsh et Powell . . . . . . . . . . . 24 1.12.3 Graphes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.12.4 Coloration des sommets d’un graphe planaire . . . . . . . . . . . 24 1.12.5 Coloration des arêtes d’un graphe . . . . . . . . . . . . . . . . . 25 1.13 Graphes triangulés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Graphes orientés 29 2.1 Graphes orientés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 Degré d’un sommet d’un digraphe . . . . . . . . . . . . . . . . . . . . . 29 2.3 Chemins et circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.1 Digraphe fortement connexe . . . . . . . . . . . . . . . . . . . . 31 2.4 Représentations non graphiques des digraphes . . . . . . . . . . . . . . . 31 2.4.1 Matrice d’adjacences . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.2 Listes d’adjacences . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.5 Digraphes sans circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6 Graphes de comparabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 34 CAHIERS DE LA CRM No 6 · i 2.7 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.8 Réseau PERT (Project Evaluation and Review Technique) . . . . . . . . . 37 Bibliographie 40 Lexique 41 Index 46 ii · No 6 CAHIERS DE LA CRM Avant-propos La mise en oeuvre du RRM a nécessité certains ajustements des programmes de mathéma- tiques enseignés dans les gymnases de Suisse romande. La Commission Romande de Ma- thématique (CRM) tient à proposer des moyens d’enseignement conformes aux exigences du règlement de maturité. Aussi ses membres s’emploient-ils depuis plusieurs années à la mise à jour de sa collection « Ouvrages collectifs » qui couvrent en priorité les besoins du programme de niveau standard. Certaines notions généralement étudiées dans les cours de mathématiques de niveau ren- forcé ont été volontairement retirées des ouvrages de base. En outre, l’introduction des options spéciﬁques a ouvert de nouveaux horizons quant aux sujets de mathématiques abordés. Soucieuse de tenir compte de cette évolution, la CRM proposait en 2004 les deux premiers ouvrages d’une nouvelle collection, les Cahiers de la CRM. Ce cahier, le sixième de la série, parle des graphes, un sujet uploads/Philosophie/ graphes.pdf