[PDF] Théorie des graphes Introduction Programme de Terminale ES

View - Download Théorie des graphes Introduction Programme de Terminale ES

Previous PDF

Next PDF

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 attendues

Vocabulaire 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 base

Denition 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 sommetEest

de 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)2

2009-20102/6

Theorie des graphesPreparation CAPES UCBL2 Cha^ne et cycle euleriens

Denition 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, il

existe 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 graphe

Denition 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 B

BBB@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 graphe

Denition 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 ponderes

Denition 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 sommet

Dvers 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

03;D12;D+1+1+1+13;D12;D8;A+138;A+112;D8;A18;C16;C+112;D18;C16;C+118;C16;C29;F18;C29;F29;FLa cha^ne la plus courte est doncDACFG

2009-20105/6

Theorie des graphesPreparation CAPES UCBL6 Graphes probabilistes On veut modeliser l'evolution d'un individu pouvant changer alea- toirement d'etat. On suppose que le passage d'un etat a un autre est toujours regi de la m^eme facon. A chaque etapen, on denit une loi de probabilite sur l'ensemble des etats, appele etat probabiliste de l'etapen, represente par une matrice ligne notee P n=anbncn:::Denition 10. Ungraphe probabilisteest un graphe oriente et pondere tel que : les sommets du graphes sont les etats possiblesA,B,C,... le poids d'une ar^ete corientee issue du sommetiet allant vers le sommetjest la probabilite conditionnelle d'^etre a l'etatja l'etape n+ 1sachant que l'etatiest realise a l'etapen. Lamatrice de transitiondes etats d'un graphe probabiliste est une matrice carree dont les elements sont les poids des ar^etes du graphe.Exemple : Un eleve peut se rend a son lycee par trois cheminsA,BetC. Chaque jour il peut changer ou non d'iteneraire : S 'ilpas sep arl ec heminA, le lendemain il prend le cheminB avec proba 0;5 et le cheminCavec proba 0;2. S 'ilpas sep arl ec heminB, le lendemain il prend le cheminA avec proba 0;1 et le cheminCavec proba 0;6. S 'ilpas sep arl ec heminC, le lendemain il prend le cheminA avec proba 0;6 et le cheminBavec proba 0;2.

La matrice de transition associee est donc

M=0 @0;3 0;5 0;2

0;1 0;3 0;6

0;6 0;2 0;21

Aet le graphe probabiliste correspondant a la situation est le suivant : Theoreme 5.SoitP0la matrice representant l'etat probabiliste initial et pour toutn1,Pnla matrice representant l'etat probabiliste a l'etapen. On a alors pour toutn0, P n+1=PnM; Pn=P0Mn Pour tout graphe probabiliste d'ordre 2, lorsquendevient tres grand, l'etat probabilistePntend vers un etat stablePindependant de l'etat initialP0. De plus,P=PM.Ainsi, si on note au journ, {anla probabilite que l'eleve emprunte le cheminA, {bnla probabilite que l'eleve emprunte le cheminB, {cnla probabilite que l'eleve emprunte le cheminC,

Alors, les probabilitesan+1,bn+1,cn+1verient :

an+1bn+1cn+1=anbncnM

Dans notre exemple, on a donc

8< :a n+1= 0;3an+ 0;1bn+ 0;6cn b n+1= 0;5an+ 0;3bn+ 0;2cn c n+1= 0;2an+ 0;6bn+ 0;2cn Lorsqu'il y a trois etats comme dans cet exemple, on ne peut pas conclure sur la limite de l'etat probabilistePn.

2009-20106/6

quotesdbs_dbs47.pdfusesText_47

[PDF] Maths spécialité nombres premiers

[PDF] Maths spécialité T ES : complément sur les suites

[PDF] Maths Spheres

[PDF] maths st2s exercices

[PDF] maths staatistiquee

[PDF] MATHS STATISTIQUES URGENT SVP!!

[PDF] maths stats

[PDF] Maths Suite géométrique terminale

[PDF] Maths super urgent avec grosse récompense (voir le devoir )

[PDF] maths sur les fonction

[PDF] Maths sur les fonctions

[PDF] Maths sur les probabilités exercices

[PDF] maths sur puissances

[PDF] Maths sur Thalès pour demain

[PDF] maths svp