18 oct 2002 · Graphes Pour la Terminale ES Groupe IREM de Luminy courte, donne les d efinitions et propri et es n ecessaires pour enseigner ce cours
| Previous PDF | Next PDF |
[PDF] sur 9 Terminale ES Spé : Graphes 1 VOCABULAIRE DE BASE a
Un sommet est isolé lorsqu'il n'est relié à aucun autre sommet viii Un sous graphe (G') de (G) est un graphe composé de certains sommets et de toutes les arêtes
[PDF] Théorie des graphes Introduction Programme de Terminale ES
théorie des graphes enseignées en Terminale ES Le programme de graphes : sommets, sommets adjacents, arêtes, degré d'un sommet, ordre d'un graphe
[PDF] Graphes Pour la Terminale ES
18 oct 2002 · Graphes Pour la Terminale ES Groupe IREM de Luminy courte, donne les d efinitions et propri et es n ecessaires pour enseigner ce cours
[PDF] PDF 2 - Maths Bordeaux
Extrait du programme de spécialité de Terminale ES BO hs n°4 du graphes : sommets, sommets adjacents, arêtes, degré d'un sommet, ordre d'un graphe Elle a disposé dans la cour 5 plots formant les sommets d'un pentagone régulier
[PDF] Les graphes - IREM de la Réunion - Université de La Réunion
Structure de graphes particuliers 11 Matrice d'adjacence d'un graphe 12 un cours sur les graphes du niveau de l'option de la terminale ES : on y trouvera
[PDF] GRAPHES - Lycée dAdultes
Compilation réalisée à partir d'exercices de BAC TES Exercice n°1 Un groupe Ces excursions sont résumées sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes représentent les Le cours nous affirme qu'alors 5 1
[PDF] Graphes Pour la Terminale ES - Groupe enseignement de l
18 oct 2002 · Solution de l'exercice 3 : Il a été résolu dans le cours du chapitre: on schématise la situation par un graphe dont les sommets sont les ıles, et les
[PDF] Graphes Pour la Terminale ES
18 oct 2002 · Graphes Pour la Terminale ES Groupe IREM de Luminy courte, donne les d efinitions et propri et es n ecessaires pour enseigner ce cours
[PDF] graphes
2 graphe connexe, trajet Eulérien et algorithme d'Euler 19 2 1 activités 3 graphe orienté, matrice d'adjacence, graphe étiqueté 32 donc (propriété du cours), la suite (Pn) converge vers un état P = (x;y) avec x + y = 1 qui vérifie l' équation
[PDF] Cours de mathématiques - reymarlioz
9 mar 2012 · T Rey - Cours de Terminale ES spé 9 mars 2012 un graphe est dit complet si tous les sommets sont adjacents les uns aux autres ;
[PDF] cours graphes probabilistes
[PDF] le mystère de la chambre jaune questionnaire lecture
[PDF] le mystère de la chambre jaune reponse
[PDF] le mystère de la chambre jaune audio
[PDF] qu'est qu'un diviseur
[PDF] exemple de diviseur
[PDF] qu est ce qu un multiple de 9
[PDF] qu est ce qu un divisible
[PDF] qu'est ce qu'un diviseur de 6
[PDF] trigonaliser une matrice d'ordre 4
[PDF] un multiple définition
[PDF] trigonaliser une matrice exemple
[PDF] trigonalisation méthode de jordan
[PDF] trigonalisation matrice 3x3
GraphesPour la Terminale ESGroup e IREM de LuminyPierre ArnouxFernand DidierCatherine DufosseNicolas Lichiardop olChristian MauduitDominique ProudhonChristiane Rambaud18 o ctobre 2002
TabledesmatieresIntro ductioniv1Denitions de base11.1Quelques problemes. ... ... .. ... ... ... ... ... .. ... ... ... .11.2Denitions et resultats... ... .. ... ... ... ... ... .. ... ... ... .31.2.1Vo cabulaire de base : Graphes, sommets, ar^etes.. ... .. ... ... ... .31.2.2Sous-graphes. ... ... .. ... ... ... ... ... .. ... ... ... .51.2.3Cha^nes et connexite ... .. ... ... ... ... ... .. ... ... ... .61.2.4Cha^ne eulerienne. ... .. ... ... ... ... ... .. ... ... ... .71.2.5Graphes orientes .. ... .. ... ... ... ... ... .. ... ... ... .81.3Quelques exercices supplementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .111.4.1Un p eu de terminologie. .. ... ... ... ... ... .. ... ... ... .111.4.2Demonstration du theoreme d'Euler. . . . . . . . . . . . . . . . . . . . . . . .111.4.3Chaines euleriennes dans les graphes orientes... ... .. ... ... ... .121.4.4Une application amusante : le graphe des mots . . . . . . . . . . . . . . . . .131.4.5Graphes hamiltoniens.. .. ... ... ... ... ... .. ... ... ... .141.4.6Graphes planaires. ... .. ... ... ... ... ... .. ... ... ... .141.5Solution des exercices... ... .. ... ... ... ... ... .. ... ... ... .162Graphes et matrices : problemes de comptage de cha^nes202.1Quelques problemes. ... ... .. ... ... ... ... ... .. ... ... ... .202.2Recapitulation : les denitions et resultats . . . . . . . . . . . . . . . . . . . . . . . .222.3Quelques exercices supplementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .252.4.1Quelques applications des problemes de comptage... .. ... ... ... .252.4.2D'autres matrices en theorie des graphes . . . . . . . . . . . . . . . . . . . . .252.5Solution des exercices... ... .. ... ... ... ... ... .. ... ... ... .283Problemes de coloriage303.1Quelques problemes. ... ... .. ... ... ... ... ... .. ... ... ... .303.2Recapitulation : les denitions et resultats . . . . . . . . . . . . . . . . . . . . . . . .343.3Quelques exercices supplementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .363.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .383.4.1Nombre de stabilite... .. ... ... ... ... ... .. ... ... ... .383.4.2Ma jorations du nombre chromatique . . . . . . . . . . . . . . . . . . . . . . .383.4.3Le theoreme des 4 couleurs. ... ... ... ... ... .. ... ... ... .39ii
TABLE DES MATI
ERESiii3.5Solution des exercices... ... .. ... ... ... ... ... .. ... ... ... .404Problemes de plus court chemin444.1Un probleme.. ... ... ... .. ... ... ... ... ... .. ... ... ... .444.2Recapitulation : les denitions et resultats . . . . . . . . . . . . . . . . . . . . . . . .454.3Quelques exercices additionnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .464.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .474.4.1Cet algorithme est-il ecace ?.. ... ... ... ... .. ... ... ... .484.4.2Cet algorithme est-il correct ? . . . . . . . . . . . . . . . . . . . . . . . . . . .484.4.3Quelques autres problemes. ... ... ... ... ... .. ... ... ... .494.5Solution des exercices... ... .. ... ... ... ... ... .. ... ... ... .495Graphes etiquetes515.1Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515.1.1Le jeu du labyrinthe ... .. ... ... ... ... ... .. ... ... ... .515.1.2Un digico de . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .525.1.3Reconnaissance de mo deles. ... ... ... ... ... .. ... ... ... .535.2Recapitulation : les denitions et resultats . . . . . . . . . . . . . . . . . . . . . . . .545.3Quelques exercices supplementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . .555.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .585.4.1Terminologie. ... ... .. ... ... ... ... ... .. ... ... ... .585.4.2Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .595.4.3Expressions regulieres et langages rationnels.... ... .. ... ... ... .615.4.4Automates deterministes et non deterministes . . . . . . . . . . . . . . . . . .625.4.5Quelques elements de la preuvedutheoreme de Kleene.. ... ... ... .635.4.6Une recreation mathematique : les suites automatiques.. ... ... ... .665.4.7Un p eu de b ourbakisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .675.4.8Une hierarchie de langages. ... ... ... ... ... .. ... ... ... .695.4.9Une autre generalisation : les automates avec sortie.. .. ... ... ... .695.4.10 Quelques utilisations des automates.. ... ... ... .. ... ... ... .705.5Solutionsdesexercices ... ... .. ... ... ... ... ... .. ... ... ... .716Graphes probabilistes746.1Quelques exercices.. ... ... .. ... ... ... ... ... .. ... ... ... .746.2Recapitulation : les denitions et resultats . . . . . . . . . . . . . . . . . . . . . . . .796.2.1Generalites : graphes probabilistes apetats . . . . . . . . . . . . . . . . . . .796.2.2Un cas particulier : les graphes probabilistes a2etats . . . . . . . . . . . . .816.2.3Cas general : evolution versunetat stable . . . . . . . . . . . . . . . . . . . .846.3Quelques exercices additionnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .846.4Complements p our les enseignants. ... ... ... ... ... .. ... ... ... .866.4.1Terminologie. ... ... .. ... ... ... ... ... .. ... ... ... .866.4.2Retour sur le cas de deux etats: valeurs propres, vecteurs propres . . . . . . .866.4.3Le theoreme de Perron-Frob enius . . . . . . . . . . . . . . . . . . . . . . . . .876.4.4Application aux matrices sto chastiques . . . . . . . . . . . . . . . . . . . . . .906.4.5Quelques applications des cha^nes de Markov... ... .. ... ... ... .906.5Solution des exercices... ... .. ... ... ... ... ... .. ... ... ... .91
Intro ductionCe texte presente la partie \graphes" de l'option de mathematiques de terminale ES. Le but de cetteoption n'est pas, bien s ^ur, de transformer les eleves de terminale ES en specialistes de la theoriedes graphes, mais de montrer comment l'utilisation judicieuse d'un graphe p eut rendre certainsproblemes concrets accessibles a un raisonnement mathematique.Il n'est donc pas question, comme cela est bien precise dans le programme, de faire un coursformel ; ce parti-pris se re
ete dans le present texte. Chaque chapitre debute donc par quelquesproblemes dontlaresolution est facilitee par la consideration des proprietes d'un graphe.Unedeuxieme partie, courte, donne les denitions et proprietes necessaires p our enseigner ce cours.Une troisieme partie donne d'autres exercices p ossibles, avec quelques explications, en particuliersur leur inter^et pedagogique.Enn, une quatrieme partie de chaque chapitre, intituleeComplements pour les enseignants,est consacree a des connaissances plus approfondies p ermettant d'avoir un certain recul, et decomprendre les raisons p our lesquelles on a choisi d'intro duire ces notions.Insistons sur le faitqu'elle n'est absolument pas necessaire p our l'enseignement de l'option, et qu'elle nefait pas du tout partie du programme !Elle p eut par contre donner des pistes p ourles TPE, en montrant nombredethemes \pratiques" a prop os desquels on p eut developp er unetheorie mathematique utile; elle p eut aussi, dans certains cas, donner des idees d'exercices, tels quele graphe des mots, ou les cha^nes euleriennes orientees.La terminologie a etevolontairement restreinte au maximum, p our ne pas surcharger les eleves(il s'agit d'une option de 24H !). En particulier, nous avons choisi de commencer par les graphes nonorientes, plus simples au depart, et d'intro duire quand la situation le demande les graphes orientes,en reprenantle vo cabulaire precedent (on parlera donc d'ar^ete orientee, de chaine orientee, etc. . . ).Nous reviendrons sur ce p oint dans les chapitres concernes.De m^eme, on a choisi de parler de graphes probabilistes laou les probabilistes parlentdecha^nes de Markov, et de graphes etiquetes laou les informaticiens parlent d'automates nis ;les complements de chaque chapitre donnent la terminologie usuelle.Il p eut ^etre interessantdesignaler aux eleves le vo cabulaire couramment utilise dans ces domaines, mais seul le vo cabulairedonne dans le programme est exigible au baccalaureat.Le texte a eteredigeentre mars et o ctobre 2002 par le group e de l'IREM d'Aix-Marseille, aLuminy.iv
Chapitre 1Denitionsdebase1.1Quelques problemesCommencons par un probleme recreatif :Exercice 1Une ligue de footbal l contient 15 clubs.Pour des raisons de temps, on decide quechaque club ne jouera que la moitie des matchs possibles. Comment organiser le tournoi ? (onpourracommencer par etudier le cas de 7 clubs).Avec 15 clubs, il est assez dicile de demarrer le travail sur ce probleme , a cause de la tailledes donnees. Avec 7 clubs, on est rapidement amenea un dessin o uchaque club est represente parun p oint, et o u on relie par un trait deux clubs qui disputentunmatch. Une b onne idee est alorsde compter le nombre de traits, c'est-a-dire le nombre de matchs qui serontjoues ; comme chaquetrait a deux extremites, c'est aussi la moitie du nombre de participations : si chacun des 7 clubsjoue 3 matchs, il y a 21 participations, dont
212
matchs, ce qui est absurde ! De m^eme, dans le casde 15 clubs, si chaque club joue la moitie des matchs p ossibles, soit 7, il doit y avoir
1572
matchs :l'organisation d'un tel tournoi n'est pas p ossible, p our de pures raisons arithmetiques. On voit que,plus generalement, p our la m^eme raison, s'il y a un nombre impair d'equip es, il n'est pas p ossiblequ'elles jouent toutes un nombre impair de matchs.L'idee essentielle est de representer la situation par un dessin particulier, ungraphe: des p ointsrelies par des traits. Dans ce dessin, la situation geometrique n'est pas imp ortante, ce qui comptece sont les p oints (ousommets), et la facon dont ils sont relies a d'autres par des traits (ouar^etes).Des problemes tres dierents p euvent se ramener a une m^eme representation :Exercice 2Comment tracer 5 segments sur une feuil le, de tel le maniere que chaque segment encoupe exactement 3 autres ?Si l'on p ense a representer chaque segment par un p oint, et a relier 2 p oints si les segmentscorresp ondants se coup ent, on voit, exactement comme p our l'exercice precedent, que l'exerciceprop ose est imp ossible.Remarquons que nous avons obtenuun resultat qui n'etait nullementevident : p our montrerqu'un probleme est p ossible, il sut d'en exhib er une solution ; il est en general bien plus dicilede demontrer qu'un probleme est imp ossible, et cela ne p eut se faire sans un raisonnement.Continuons par le probleme suivant, qui est un classique : prop ose en 1736 par Leonhart Euler,c'est le premier probleme de la theorie des graphes. Il est aujourd'hui parfaitementresolu, maisles habitants de Ko enigsb erg (aujourd'hui Kaliningrad, ville russe enclavee entre la Pologne et laLituanie) ne voyaient pas comment faire.1
2CHAPITRE 1.D
EFINITIONS DE BASEExercice 3Probleme des ponts de Konigsberg: Au XVIIIe siecle, la vil le de Koenisbergcomprenait2^les et 7 ponts suivant le plan ci-dessous :
Figure 1.1: Les p onts de Ko enigsb ergLes habitants souhaitaient faire une promenade passant une et une seule fois sur chaque pont.Y sont ils arrives ?Traduisons de m^eme ce probleme a l'aide d'un graphe. Chaque region de la ville est representeepar un sommet, et un p ontentre deux regions, par une ar^ete entre les sommets concernes, quelgraphe obtient-on ? Commentinterprete-on alors la condition sur la promenade ? Nous reviendronsplus loin sur ce probleme.De tres nombreux problemes pratiques p euvent^etre ainsi schematises a l'aide d'un graphe ;en simpliant la representation, on p eut ainsi trouver plus rapidement la solution (ou en voirl'imp ossibili te!). Pour certains problemes, comme ceux que nous venons de voir, les ar^etes n'ontpas d'orientation. Pour d'autres, il est indisp ensable d'avoir une orientation sur le graphe : le pland'une ville comme graphe non oriente satisfera le pieton, tandis que ce m^eme graphe oriente par lessens de circulation sera bien plus apprecie de l'automobiliste. Une autre utilisation classique desgraphes est l'ordonnancementdest^aches : p our un pro jet tel que la construction d'une maison, il ya dierentes t^aches qui doivent^etre eectuees dans un certain ordre : on doit creuser les fondationsavantd'elever les murs. On p eut representer le pro jet par un graphe dont les sommets sont lesdierentes t^aches, et o uonrelieAaBsiAdoit ^etre terminee avant de commencerB. L'ar^etecorresp ondante p ossede une orientation naturelle.Une question imp ortante est celle du choix du graphe asso ciea une situation donnee (il p eutyenavoir plusieurs) ; commentchoisir les sommets et les ar^etes ?Comme on vientdelevoirdans l'exercice 2, ce n'est pas toujours evident : dans la mo delisation prop osee, les segments sontles sommets du graphe, et les ar^etes corresp ondentauxpoints d'intersection. Dans des chapitresulterieurs, on etudiera des questions de compatibilite, il faudra decider si les ar^etes corresp ondentaux couples de p oints compatibles ou incompatibles, et si les ar^etes sontorientees ou non.
1.2.DEFINITIONS ET R
ESULTATS31.2Denitions et resultatsNous allons formaliser les notions qui precedent.1.2.1Vo cabulaire de base : Graphes, sommets, ar^etesDenition 1UngrapheG(non oriente) est constitue d'un ensembleS=fs1
;s2 ; :::; sn gde pointsappelessommets, et d'un ensembleA=fa1 ;a2 ; :::; am gd'ar^etes, tels qu'a chaque ar^eteai sontassocies deux elements deS, appeles ses extremites, et que nous noterons[sj ;sk ]i.Les deux extremites p euvent^etre distinctes ou confondues ; dans ce dernier cas, l'ar^ete s'app elleuneboucle.Une premiere maniere d'evaluer la complication d'un graphe est de compter le nombre de sessommets; les mathematiciens ont donnea ce nombre un nom particulier (que l'on retrouve dansd'autres domaines, par exemple en theorie des group es) :Denition 2L'ordred'un graphe est le nombre de ses sommets.Denition 3Etant donnee une ar^eteaassociee a[s1
;s2 ], on dit que les sommetss1 ets2 sontles extremites de l'ar^etea,ets1 ets2 sont ditsadjacents.Lorsques1 =s2,onditqueaest uneb oucle.Un graphe est ditsimplesi deux sommets distincts sont joints par au plus une ar^ete et s'il estsans boucle.Remarque :Deux ar^etes sont ditesparal leleslorsqu'elles ontm^emes extremites. Dans certainescirconstances, il est naturel de considerer des graphes avec des ar^etes paralleles (par exemple p ourle probleme des p onts de Ko enigsb erg). Cep endant, la tres grande ma jorite des problemes que nousrencontrerons concerne des graphes simples, c'est-a-dire sans b oucles ni ar^etes paralleles. Il n'estdonc pas utile d'intro duire cette terminologie en cours.Exemple 1 :Considerons le grapheG1
d'ordre 4 deni par :SoitS=fs1 ;s2 ;s3 ;s4 getA=fa; b; c; d; egtel qu'aux ar^etesa; b; c; d; esoient resp ectivementasso cies [s1 ;s1 ];[s1 ;s2 ];[s1 ;s2 ];[s1 ;s3 ];[s2 ;s3 ]. Une representation p ossible de ce graphe est : s 4 s 3 s 1 s 2ad e c bFigure 1.2: Le grapheG1Le p oints4 est unpoint isole, l'ar^eteaest une b oucle,betcsont des ar^etes ayantm^emesextremites, [s1 ;s2 ] est une ar^ete multiple, les sommetss1 ets2 sont adjacents, ainsi ques1 ets3 ,puisqu'ils sont relies par une ar^ete.4CHAPITRE 1.D
EFINITIONS DE BASEUn graphe n'est rien d'autre qu'un dessin forme de p oints joints par des traits, et il est plusfacile de representer ce dessin, que de donner les ensemblesSetA,etlesextremites de chaquear^ete ; dans le dessin, chaque sommet est represente par un p oint, et une ar^ete liant les sommetss1ets2
par un trait reliant les p oints representants1 ets2. Il faut bien remarquer qu'il y a plusieursdessins p ossibles p our un m^eme graphe, et que deux ar^etes p euvent se croiser sans p our autantdenir un sommet (Comme on le verra ci-dessous, il n'est pas toujours p ossible de representer ungraphe sur une feuille sans qu'il y ait de croisement). Le dessin doit donc clairement identier lessommets.Exemple 2 :On a represente dans le dessin qui suit un certain nombre de graphes. Il est facilede voir queG2
etG3 , d'une part,G4 etG5 d'autre part represententle m^eme graphe ; de m^eme,G 6 etG8 represententle m^eme graphe. Par contre,G6 etG7 sont des graphes d'ordre 6 dierents.Une facon de le prouver est la suivante : dansG6 etG7 , si l'on xe un sommet, il y a exactement2sommets qui ne lui sont pas adjacents ; mais dansG6 , ces deux sommets sont relies par une ar^ete(comme dansG8 bien s ^ur) alors que dansG7 ils ne sontrelies par aucune ar^ete. L L L L L L L r r r r r r r111111111111G
3 8 8 8 8 8 8 8 8 8 8 8 888888888G
26666666666
V VVVVVVVVVV
hhhhh hhhhhhG 4 x x x x x x x x x x x x x x x x x FFFFFFFFFFFFFFFFF
))))))))))))))))G 59999999999999999
999 G7 G8 G
6Figure 1.3: Quelques exemples de graphesRemarque :C'est un probleme tres dicile en general, des que le nombre de sommets est assezgrand, de decider si deux dessins represententle m^eme graphe, aun changement de nom pres p ourles sommets et les ar^etes ; il est souvent plus facile, en utilisant des proprietes particulieres, demontrer que deux dessinsne representent pasle m^eme graphe.
1.2.DEFINITIONS ET R
ESULTATS5Denition 4Un graphe simple est ditcompletsi tous ses sommets sont adjacents, c'est a diresitoutes les ar^etes possibles existent (sauf les boucles). On appeleraKn
le graphe complet ansommet(il n'y en a qu'un).Denition 5On appel ledegred'un sommet le nombre d'ar^etes dont ce sommet est une extremite( les boucles etant comptees deux fois ). Un sommet estpair(respectivementimpair) si son degreestunnombrepair (respectivement impair).Exemple 3 :
Dans le grapheG1
de l'exemple 1 :s1 est de degre5,s2 de degre3,s4de degre0.Les sommets du graphe complet d'ordre n sont tous de degre n-1.On prouve facilementletheoreme suivant:Theoreme 1La somme des degres de tous les sommets d'un graphe est egale adeux foislenombred'ar^etes de cegraphe ; c'est donc un nombrepair.Demonstration :Il sut de faire comme p our le premier exercice : lorsque on additionne lesdegres des sommets, une ar^ete est comptee deux fois, une fois p our chaque extremite.
Corollaire 1Dans un graphe le nombre de sommets impairs est toujours pair.Demonstration :En eet, sinon, la somme des degres des sommets serait impaire.
On retrouve ici le fait que le premier exercice p oseen intro duction est imp ossible : il n'existepas de graphe d'ordre 15 tel que chaque sommet soit de degre7.1.2.2Sous-graphesOn a souvent b esoin d'isoler une partie d'un graphe :Denition 6SoitG=(S; A)un graphe, le grapheG
0=(S 0;A0)est unsous-graphedeG,siS
0etA0sont des sous ensembles deSetA, tels que toutes les extremites des ar^etes deA
0soient deselements deS
0. SideplusA
0contient exactement toutes les ar^etes deAdont les extremites sontdes elements deS
0alors on dit queG
0=(S 0;A0)est lesous-graphe deGengendreparS
0;ilestdeterminede maniere unique par la donnee deS
0.Exemple 4 :Le graphe suivant:
s 3 s 1 s 2 ac6CHAPITRE 1.D
EFINITIONS DE BASEest un sous graphe deG1
, le sous graphe engendre pars1 ;s2 ;s3 estG1 fs4 g.Le sous-graphe engendreparfs4 ;s3gest sans ar^ete, c'est lui m^eme.SiSest l'ensemble des villes de France qui ont une gare, etAl'ensemble des voies ferrees lesreliant, siS
0est l'ensemble des villes d'un departement, avec une gare, etA
0l'ensemble des voiesferrees les reliant, le grapheG
0=(S 0;A0) est le sous-graphe du grapheG=(S; A) engendre parS
0.Maintenant si on considere le reseau TGV :S
00ensemble des villes de France qui ont une gare TGV,etA
00ensemble des voies ferrees TGV les reliant, le grapheG
00=(S 00;A00) est un sous graphe deG,mais n'est pas engendre parS
00, il existe des voies ordinaires entre Lyon et Marseille par exemple.Denition 7On dit qu'un sous-ensemble de l'ensemble des sommets eststables'il ne contient pasde paire de sommets adjacents.On p eut aussi parler de sous-graphe stable : cela revientaum^eme, puisque si un ensemble desommets est stable, le graphe engendre, par denition, n'a pas d'ar^ete. Dans l'exemple ci-dessus,le sous-ensemblefs4
;s3gest stable.Ce terme de \stable" p eut para^tre arbitraire. Il est en fait naturel si l'on considere ce qu'onapp elle \graphe d'incompatibilite":dans un group e d'individus, on p eut denir un graphe enreliant par une ar^ete les individus qui ne p euvent se supp orter. Si l'on veut choisir un sous-group ede p ersonnes qui travaillent ensemble, il est preferable de choisir un sous-ensemble stable ! C'estune notion imp ortante p our divers problemes ; on verra en particulier b eaucoup d'applications decette notion dans le chapitre sur les coloriages.1.2.3Cha^nes et connexiteDans bien des problemes de graphes, il est naturel de considerer ce que l'on p eut app eler, de faconinformelle, des \parcours" ou \chemins". Le mot utiliseentheorie des graphes est \cha^ne".La notion intuitivedecha^ne, ou plus tard de cha^ne orientee, se comprend bien sur un dessin,et il est essentiel que les eleves sachent reconna^tre si un ensemble donnee d'ar^etes est une cha^ne.Il est moins facile d'en donner une denition eective. C'est un b on exercice de tenter de donnerune denition formelle de cette notion, non p our obliger les eleves a l'apprendre par co eur, maisp our leur montrer les dicultes qu'il p eut y avoir arediger une denition ou un theoreme, et laraison p our laquelle cette redaction est parfois complexe :Exercice 4Les denitions suivantes formalisent-el les bien ce que l'on veut?Denition 1 : on appel le cha^ne une suitea1
;a2 ;:::;and'ar^etes qui est tel le que deux ar^etesconsecutives aient une extremitecommune.Denition 2 : on appel le cha^ne une suites0
;s1 ;:::;sntel le que deux sommets consecutifs soientadjacents.Apres avoir passe un p eu de temps sur cet exercice, on appreciera mieux la denition suivante,d'apparence un p eu complexe :Denition 8Unecha^nedans un graphe G est une suite nie :s0
;a1 ;s1 ;a2 ;s2 ;a3 ;s3 ::::an;sndebutant et nissant par un sommet, alternant sommets et ar^etes de tel le maniere que chaque ar^etesoit encadree par ses sommets extremites. Lalongueur de la cha^neest egale au nombre d'ar^etesqui la constituent ; la cha^ne est fermee sis0
=sn, si de plus toutes ses ar^etes sont distinctes ondit alors que c'est uncycle.Unk-cycleest un cycle de longueurk.
1.2.DEFINITIONS ET R
ESULTATS7Remarque :Quand il n'y a pas d'ambigute (pas d'ar^etes multiples), on p eut denir une cha^nepar seulement la suite de ses sommets ou de ses ar^etes; dans ce cas, la denition 2 prop osee dansl'exercice 4 est correcte, mais toujours pas la denition 1. On p eut la remplacer par la suivante, quiest correcte dans tous les cas: on app elle cha^ne une suitea1
;a2 ;:::;an d'ar^etes telles que chaquear^eteai , p our 1