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
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
Theorie des graphesPreparation CAPES UCBLIntroduction Ces quelques pages ont pour objectif de vous initier aux notions de theorie des graphes enseignees en Terminale ES. Le programme de Terminale (voir ci-apres) est construit sur la resolution de problemes. Aucune theorie formelle n'est introduite, mais beaucoup de vocabu- laire. Il faut donc conna^tre quelques denitions pour pouvoir aronter sans mal les oraux du CAPES. Une lecon d'expose est consacree aux graphes, et le theme est deja paru lors de l'epreuve sur dossier. Programme de Terminale ES SpecialiteResolution de problemes a l'aide de graphes
ContenusCapacites attendues
Resolution de problemes conduisant
a la modelisation d'une situation par un graphe oriente ou non, eventuel- lement etiquete ou pondere et dont la solution est associee : au col oriaged' ungr aphe al are cherched un ombrec hroma- tique al 'existenced 'unec ha^neou d' un cycle eulerien ala r echerched 'unep lusc ourte cha^ne d'un graphe pondere ou non al acar acterisationd esmot sr e- connus par un graphe etiquete et, reciproquement, a la construction d'un graphe etiquete reconnais- sant une famille de mots, al are cherched 'un etatst able d'un graphe probabiliste a 2 ou 3 sommetsLes problemes proposes met- tront en jeu des graphes simples, la resolution pouvant le plus souvent ^etre faite sans recours a des algorithmes.On indiquera que pour des
graphes complexes, des algo- rithmes de resolutions de cer- tains problemes sont absolu- ment necessaires.On presentera un algorithme
simple de coloriage des graphes et un algorithme de recherche de plus courte cha^ne.ContenusCapacites attenduesVocabulaire elementaire des
graphes : sommets, sommets adjacents, ar^etes, degre d'un sommet, ordre d'un graphe, cha^ne, longueur d'une cha^ne, graphe complet, distance entre deux sommets, dia- metre, sous-graphe stable, graphe connexe, nombre chromatique, cha^ne eulerienne, matrice associee a un graphe, matrice de transition pour un graphe pondere par des probabilites.Les termes seront introduits a l'occasion de resolutions de problemes et ne feront pas l'objet d'une denition formelle, sauf lorsque cette derniere denition est simple et courte (degre d'un som- met, ordre d'un graphe par exemple).Resultats elementaires sur les graphes : l iene ntrel asom med esd egresd es sommets et le nombre d'ar^etes d'un graphe; con ditionsd 'existenced ec ha^neset cycles euleriens; ex emplesde c onvergencep ourd es graphes probabilistes a deux som- mets, ponderes par des probabilites.On pourra, dans des cas elementaires, interpreter les termes de la puissance n-ieme de la matrice associee a un graphe.References et prerequis Dans tout livre de Terminale ES specialite, vous trouverez de nom- breux exercices et des methodes pratiques (Declic, Hyperbole,...). N'hesitez pas a les consulter pour vous habituer aux programmes et vous preparer a l'epreuve sur dossier. Peu de notions sont utilisees en theorie des graphes. On utilise prin- cipalement le calcul matriciel (programme de Premiere ES Specialite) et, pour la derniere partie sur les graphes probabilistes, les notions sur les suites geometriques (Premiere ES Obligatoire) et les probabilites conditionnelles (Terminale ES Obligatoire).2009-20101/6
Theorie des graphesPreparation CAPES UCBL1 Vocabulaire de baseDenition 1.
Ungrapheest un ensemble de points et de lignes reliant certains de ces points. Unsommetdu graphe est un point du graphe. Le nombre de som- mets est l'ordredu graphe. Unear^etedu graphe est une ligne reliant deux sommets. Une boucleest une ar^ete reliant un sommet a lui-m^eme. Un sommet estisolelorsque aucune ar^ete de le relie aux autres sommets. Ungraphe simpleest un graphe sans boucle tel que, entre deux sommets, il y ait au plus une ar^ete. Deux sommets relies par une ar^ete sontadjacents. Ungraphe orienteest un graphe dont les ar^etes sont orientees. Une ar^ete orientee va d'un sommet vers un autre sommet, elle est representee par une eche. Ledegred'un sommet est egal au nombre d'ar^etes dont ce sommet est une extremite.Exemples.Le graphe 1 est un graphe simple d'ordre 5, de sommetsA,B,C,D etE. Les sommetsAetBsont adjacents,AetCne le sont pas,Eest un sommet isole. Le graphe 2 est un graphe oriente ayant sept ar^etes. Le sommetEestde degre 3 car trois ar^etes partent ou arrivent ene.Theoreme 1.La somme des degres de tous les sommets d'un
graphe est egal au double du nombre total d'ar^etes.Exemple.Dans le graphe 1 precedent, il y a 5 ar^etes. La somme des
degres est 2 + 3 + 2 + 3 + 0 = 10 = 25.Denition 2.Ungraphe completest un graphe simple dont tous les sommets sont adjacents les uns avec les autresExemple.Le graphe 3 est un graphe complet d'ordre 5.
Dans le graphe complet d'ordren:
le degre de chacun des sommets estn1 le nombre d'ar^etes estn(n1)22009-20102/6
Theorie des graphesPreparation CAPES UCBL2 Cha^ne et cycle euleriensDenition 3.
Unecha^ne, dans un graphe non oriente, est une suite d'ar^etes mises bout a bout reliant deux sommets du graphe. Unecha^ne orientee, dans un graphe oriente, est une suite d'ar^etes orientees telles que l'extremite terminale de l'une est l'ex- tremite initiale de l'autre. Uncycle, dans un graphe, est une cha^ne dont les extremites con- cident, composee d'ar^etes toutes distinctes. Une cha^ne est notee par la liste des sommets ou elle passe, relies par un segment ou une eche quand le graphe est oriente. Un graphe estconnexelorsque, pour chaque paire de sommets, ilexiste au moins une cha^ne reliant les deux sommets.Exemples.Dans le graphe 1 precedent, (A;D;B;D;C) est une cha^ne.
Une cha^ne orientee du graphe 2 est (B;A;C;A;D). Le graphe 1 n'est pas connexe puisqu'il posseede un sommet isole.Denition 4. Unecha^ne eulerienneest une cha^ne composee de toutes les ar^etes du graphe, prises une seule fois. Uncycle eulerienest une cha^ne eulerienne dont les extremites co ncidentTheoreme 2(Theoremes d'Euler). (i) Un g raphec onnexeadm etu nec ha^nee uleriennee ntrele ss ommets AetBsi et seulement siAetBsont les seuls sommets de degre impair. (ii) U ng raphec onnexeadm etu nc yclee uleriens ie tse ulements itou s les sommets sont de degre pair.Exemple.Le graphe 1 admet (B;C;D;B;A;D) pour cha^ne eule- rienne mais d'admet pas de cycle eulerien.3 Matrice d'adjacence d'un grapheDenition 5.
Lalongueur d'une cha^neest le nombre d'ar^etes qui la com- posent. Ladistanceentre deux sommets d'un graphe connexe est la lon- gueur de la cha^ne qui les relie, ayant le moins d'ar^etes. Lediametred'un graphe connexe est la plus grande distance consta- tee entre deux sommets de ce graphe parmi toutes les paires de som- mets.Exemple. Dans le graphe 4, la distance entreAetDest 2. Le diametre du graphe est 3 (distance entreAetE).Denition 6.Lamatrice d'adjacenced'un graphe d'ordren (resp. graphe oriente d'ordren) est la matrice carreeAde taillenn, dont l'elementai;jest egal au nombre d'ar^etes reliant les sommetsi etj. (resp. allant du sommetivers le sommetj).Exemple.Reprenons le graphe 4.Sa matrice d'adjacence est la sui-
vante. Elle est symetrique puisque le graphe n'est pas oriente.0 BBBB@0 1 1 0 0
1 0 1 1 0
1 1 0 1 0
0 1 1 0 1
0 0 0 1 01
C CCCA.Theoreme 3.SoitAla matrice d'adjacence d'un graphe et soit p1. Alors, l'elementpi;jde la matriceApest egal au nombre de cha^nes de longueurpreliant le sommetiau sommetj.2009-20103/6 Theorie des graphesPreparation CAPES UCBL4 Coloriage des sommets d'un grapheDenition 7.
Unsous-graphed'un grapheGest un graphe compose de sommets deGet de certaines ar^etes qui relient ces sommets. Un sous-graphe est ditstablelorsqu'il ne comporte aucune ar^ete, autrement dit si deux sommets quelconques ne sont pas adjacents.Denition 8. Colorier les sommets d'un grapheGnon oriente, c'est leur attribuer une couleur de facon a ce que deux sommets adjacents ne soient pas colories de la m^eme couleur. Le nombre minimal de couleurs necessaires est lenombre chroma- tiquedu graphe, note (G).Theoreme 4. (i) L enom brec hromatiqued' ung raphec omplete st egal al 'ordredu graphe. (ii) So itDle degre maximal des sommets d'un grapheG, alors (G)1 +D: (iii) Soi tpl'ordre d'un sous-graphe complet d'ordre maximal contenu dans un graphe, alors p (G):Exemple :Pour le graphe 5, (B;C;E;F) est un sous-graphe complet d'ordrep= 4 (il est maximal). De plus, voici les degres des sommets :sommetABCDEFG degre4342564 Ainsi, le plus haut degre estD= 6. On sait donc que 4 (G)6 + 1 = 7 Algorithme de Welsh et Powell: algorithme de coloriage d'un graphe.1.On liste les sommets par ordre decroissant des degres(plusieurs
possibilites).Par exemple ici, une liste possible est
FECAGBD
2.On attribue une couleurc1au premier sommet de la liste, et
on attribue cette m^eme couleur aux sommets qui ne lui sont pas adjacents. Ici, par exemple, on met une couleurc1pourF. Aucun sommet ne lui est pas adjacent.3.On attribue une couleurc2au premier sommet non colorie de la
liste et on recommence comme en 2. tant qu'il reste des sommets non colories dans la liste.Dans notre exemple, on met
u necou leurc2aEetD. u necou leurc3aCetA. u necou leurc4aGetB. On a ainsi un coloriage du graphe 5 en 4 couleurs, donc (G)4. On peut donc en deduire que le nombre chromatique du graphe 5 est egal a 4.2009-20104/6
Theorie des graphesPreparation CAPES UCBL5 Graphes ponderesDenition 9.
Un graphe (oriente ou non) est ditponderelorsque ses ar^etes sont aectees de nombres positifs. Lepoids d'une ar^eteest le nombre positif qui lui est aecte. Lepoids d'une cha^neest la somme des poids des ar^etes qui la composent. Uneplus petite courte cha^neentre deux sommets donnes est une cha^ne de poids minimal parmi toutes les cha^nes reliant les deux sommets.Algorithme de Dijkstra: algorithme de determination d'une plus courte cha^ne d'un graphe pondere entre un sommetDet un som- metG.1.Etape d'initialisation.
O n xel ep oidsdu s ommetDa 0.
O nmar quep rovisoirementc haques ommetad jacent aDdu poids de l'ar^ete reliantDa ce sommet. Ces sommets sont des successeursdeD. O nm arquep rovisoirementl esau tress ommetsd up oids+ 1.2.Etapes d'iterations.
On noteSl'ensemble des sommets xes, etSl'ensemble des sommets marques provisoirement. Tant que l'ensembleSn'est pas vide, on choisit dansSle sommet Xdont le poids marque provisoirementpXest le plus petit. O nmar qued enitivementc esomm etXdu poidspX. On en- leveXdeSet on le place dansS. O nmar quep rovisoirementc haquesom metYsuccesseur du sommetXpar le poidspY=pX+pX;YoupX;Yest le poids de l'ar^ete reliantXaY. Si le poids obtenupYest plus petit que le poids marque provsoirement au sommetY, alors on barre ce poids marque et on marqueYdu poidspY. O nr eiterel ep rocedetan tq uel 'ensemblede ss ommetsn on xes n'est pas vide.3.Conclusion. On obtient un graphe dont tous les sommets sont xes. Le poids xe du sommetGest le poids de la plus courte cha^ne du sommetDvers le sommetGdans le graphe.
Exemple :On cherche a determiner le plus court chemin entreDetG.Voici le graphe obtenu apres l'algorithme. On ecrit a c^ote de chaque
sommet le poids (provisoire ou xe), et le sommet precedent.On peut presenter egalement le resultat dans un tableau ou chaque
ligne represente une etape de l'algorithme.DABCEFG