GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Page 5/11 jgcuaz@hotmail.com. GRAPHES - EXERCICES CORRIGES. CORRECTION. Exercice n°1. 1) a) Recopier et compléter le tableau suivant : Sommets.
Graphes exercices et correction
16 déc. 2001 L'algorithme proposé dans cet exercice donne UNE coloration de n'importe quel graphe mais ne donne pas le nombre chromatique du graphe ; en fait ...
Corrigé des exercices
Corrigé des exercices. • Combinatoire des graphes. £. ¢. ¡. Exercice 1 a) Soit G = (VE) un graphe non orienté simple. Notons V1 l'ensemble des sommets de
ENSM - Graphes - Correction Feuille TD1
Feuille TD n° 1 – Exercices (Graphes) éléments de correction. Exercice 1. Graphes 3-réguliers. d'un graphe cubique à n sommets est 3n/2 (la somme des.
Introduction à la théorie des graphes Solutions des exercices
Le nombre minimum de véhicules est le nombre minimum de chemins passant par tous les sommets du graphe. Exercice 70. Corrigé abrégé : 1. Oui. Preuve par
Correction des exercices sur les graphes probabilistes (état stable
Correction des exercices sur les graphes probabilistes (état stable) : feuille no 1 (b) La matrice de transition M de ce graphe est M = (. 085 0
THEME 3 : LES RESEAUX SOCIAUX – ACTIVITE 2 – LES GRAPHES
Ce genre de figure s'appelle un graphe. Les graphes sont des objets mathématiques très utilisés notamment en informatique.
Terminale générale - Matrices et graphes - Exercices
Matrices et graphes – Exercices. Exercice 1 corrigé disponible. Déterminer le produit BA ; le comparer à AB. Exercice 2 corrigé disponible.
Série corrigée Initiation aux graphes
1 mai 2017 Exercice n°1. Déterminer le degré de chacun des sommets du graphe ci-dessous : Exercice n°2. ... Correction série Initiation aux graphes.
IT3004 Graphes et algorithmes Notes de cours et exercices
20 févr. 2017 liens sur d'autres sites parlant de graphes et d'algorithmes . ... on notera l(xy) la longueur de u (plutôt que l((x
Chapitre 2option informatique
Corrigé des exercices
Combinatoire des graphes
Exercice 1
a)SoitG= (V;E)un graphe non orienté simple. NotonsV1l"ensemble des sommets de degré pair etV2 l"ensemble des sommets de degré impair. Nous savons queX v2Vdeg(v) = 2jEj, donc : X v2V2deg(v) = 2jEjX v2V1deg(v):De cette égalité il résulte que
X v2V2deg(v) est un entier pair, ce qui impose àjV2jd"être pair.b)Si aucune personne n"a d"ami dans cette assemblée, ils ont tous le même nombre d"amis, à savoir 0.
On suppose maintenant qu"il existe au moins un couple d"amis dans l"assemblée, et on considère le graphe
G= (V;E) où V est l"ensemble des personnesqui ont au moins un amiet où E est défini par : (a;b)2E()aetbsont amis: Gest un graphe non orienté simple d"ordrek, et chacun desksommets a un degré compris entre1etk1;
d"après le principe des tiroirs il existe au moins deux sommets de même degré. c)Considérons un grapheG= (V;E)dont les sommets sont les ordinateurs et les arêtes les liaisons qui les
relient. Si chaque sommet est de degré 3, la formuleX v2Vdeg(v) = 2jEjs"écrit : 315 = 2jEj, ce qui ne se peut.Exercice 2
a)Les suites (3;3;2;2) et (3;3;2;1;1) sont graphiques, comme le prouvent les deux graphes ci-dessous :12
3 41234 5
En revanche, la suite(3;3;1;1)ne peut être graphique. En effet, dans un graphe d"ordre 4 ayant deux sommets
de degré 3, autrement dit deux sommets reliés à chacun des trois autres, les deux derniers sommets sont au
moins de degré 2.b)Les deux graphes suivants sont distincts bien que correspondants tous deux à la suite (3;2;2;2;1) :12
3 4512345
c)
L"implication(ii) =)(i)est claire : s"il existe un graphe dont les sommets ont pour degrés la suite(d2
1;d31;:::;dd1+11;dd1+2;dd1+3;:::;dn), il suffit de rajouter un sommet et de le relier auxd1premiers sommets
du graphe pour obtenir un nouveau graphe correspondant à la suite : (d1;d2;d3;:::;dd1+1;dd1+2;dd1+3;:::;dn) = (d1;d2;:::;dn): http://info-llg.fr2.2option informatiqueRéciproquement, si(d1;d2;:::;dn)est graphique, nous allons montrer qu"il existe un grapheG= (V;E)tel
queV= (v1;:::;vn),deg(vi) =diettel quev1soit adjacent aux sommetsv2;v3;:::;vd1+1. Une fois ceci prouvé,
il suffira de supprimerv1ainsi que les arêtes qui le relient au reste du graphe pour en déduire que la suite
(d21;d31;:::;dd1+11;dd1+2;dd1+3;:::;dn) est graphique.Nous allons prouver l"existence deGpar l"absurde en considérant un grapheGpour lequelv1est relié au plus
grand nombre possible de sommets parmiv2;:::;vd1+1, mais pas à tous. Dans ces conditions, il existei2~2;d1+1tel que(v1;vi)Sideg(vi) =deg(vj), tous les sommets d"indices dans~i;jont même degré, et il suffit d"inverser la
numérotation des sommetsvietvjpour aboutir à une contradiction. Sideg(vi)>deg(vj), il existe un sommetvktel que(vi;vk)2Emais(vj;vk)degrés reste inchangée, mais maintenantv1est relié à un sommet de plus parmiv2;v3;:::;vd1+1ce qui
contredit le caractère maximal de G et achève la preuve du théorème. d)Prouvons tout d"abord que la suite (4;4;3;2;2;1) est graphique en appliquant le théorème : (4;4;3;2;2;1) est graphique()(3;2;1;1;1) est graphique()(1;0;0;1) = (1;1;0;0) est graphique ()(0;0;0) est graphique.La suite(0;0;0)est bien graphique donc la construction demandée est possible, et la preuve du théorème nous
donne un moyen de construire une solution à partir des équivalences ci-dessus :123 (0;0;0)=)123 4 (1;0;0;1)=)123 45(3;2;1;1;1)=)123 456
(4;4;3;2;2;1)
Si les deux sommets de degré 2 étaient voisins, on obtiendrait en retirant l"arête qui les relie un graphe dont la
suite des degrés serait (4;4;3;1;1;1). Or si on applique le théorème à cette suite on obtient :
(4;4;3;1;1;1) est graphique()(3;2;0;0;1) = (3;2;1;0;0) est graphique ()(1;0;1;0) = (1;0;0;1) est graphique ce qui est absurde.Exercice 3
Notons que la formule
X v2Vdeg (v) = 2jEj= 2n2montre que dans un arbre il existe au moins un sommet de degré 1, ce qui prouve que la terminaison de l"algorithme dePrüfer. a)La suppression des différents sommets s"effectue de cette façon :1234 5678=)123567
8=)12357
8=)1357
8=)357
8=)358=)58
et conduit au codage : (2;2;1;3;3;5).Corrigé des exercices2.3
b)Pour décoder un codage dePrüferon propose l"algorithme suivant : fonctiondecode(liste : L)V ~1;n, E ;
I V tant quejIj>2faire i minnj2IjI Infig
L queue(L)
E E[f(a;b)gavec I =fa;bg
renvoyer(V;E) qui reconstitue la liste des arêtes qui ont été supprimées par l"algorithme dePrüfer.c)Avec la suite (2;2;1;3;3;1;4;4), la suite L et les ensembles I et E évoluent de la façon suivante :LIE
(2;2;1;3;3;1;4;4)f1;2;3;4;5;6;7;8;9;10g;(2;1;3;3;1;4;4)f1;2;3;4;6;7;8;9;10gf(5;2)g(1;3;3;1;4;4)f1;2;3;4;7;8;9;10gf(5;2);(6;2)g(3;3;1;4;4)f1;3;4;7;8;9;10gf(5;2);(6;2);(2;1)g(3;1;4;4)f1;3;4;8;9;10gf(5;2);(6;2);(2;1);(7;3)g(1;4;4)f1;3;4;9;10gf(5;2);(6;2);(2;1);(7;3);(8;3)g(4;4)f1;4;9;10gf(5;2);(6;2);(2;1);(7;3);(8;3);(3;1)g(4)f4;9;10gf(5;2);(6;2);(2;1);(7;3);(8;3);(3;1);(1;4)g( )f4;10gf(5;2);(6;2);(2;1);(7;3);(8;3);(3;1);(1;4);(9;4)g;f(5;2);(6;2);(2;1);(7;3);(8;3);(3;1);(1;4);(9;4);(10;4)gce qui conduit à l"arbre :
1 2 563784
910
Représentation d"un graphe
Exercice 4Pour calculer les degrés sortants, il suffit de calculer la longueur de chacune des listes d"adjacence :letdeg_sortant = map_vect list_length ;;
Le calcul de la longueur d"une liste a un coût proportionnel à sa longueur donc le coût total de cette fonction
est un(n+p), oùn=jVjetp=jEj.Pour calculer les degrés entrants, il faut parcourir chaque liste d"adjacence et pour chaque arête(a;b)rencontrée
itérer la case d"indicebdu tableaudeg_e:letdeg_entrant g = letn = vect_length gin letdeg_e = make_vect n 0in let rec aux =function | b::q> deg_e.(b)2.4option informatique
Exercice 5Calculer la transposée d"un graphe représenté par matrice d"adjacence est facile puisqu"il suffit
de calculer la transposée de celle-ci; le coût est à l"évidence un(n2).Pour un graphe représenté par liste d"adjacence, il n"y a guère d"autre possibilité que de parcourir chacune des
listes d"adjacence en ajoutant l"arc inverse au graphe transposé, qui se construit peu à peu. Pour un graphe de typegraphe, cela conduit à la définition suivante :lettransposee g = letn = vect_length gin letgt = make_vect n []in let rec aux a =function | b::q> gt.(b)Exercice 6
Notons(1;2;:::;n)les sommets deG= (V;E)et pour touti2~1;nnotonsV(i)l"ensemble des voisins dei. Posons en outre M = (mij)16i;j6net Mp= (m(p) ij)16i;j6n. a)Montrons par récurrence surpquem(p) ijest égal au nombre de chemins de longueurpqui mènent deiàj.C" estclair si p= 1 puisquem(1)
ij=mij=8 >><>>:1 si (i;j)2E0 sinon.
Si p >1, supposons le résultat acquis au rangp1. On a :m(p) ij=n X k=1m ikm(p1) kj=X k2V(i)m(p1) kj.Puisquem(p1)
kjest égal au nombre de chemins de longueurp1reliantkàj,m(p) ijest bien le nombre de chemins de longueurpreliantiàj.En particulier,m(p)
iiest le nombre de cycles de longueurppassant par le sommeti. Ainsi,tr(M(p))est égal aunombre de cycles de longueurp(chaque cycle étant compté autant de fois que le cardinal de son support).
b)En particulier, la matriceMnn"est pas nulle si et seulement s"il existe un chemin de longueurn. Or dans un
tel chemin il existe nécessairement un sommet atteint au moins deux fois, ce qui dénote l"existence d"un cycle
au sein de ce chemin.Réciproquement, à partir d"un cycle de longueurpil est facile de construire un chemin de longueurnen
considérant la division euclidienne denparp:n=pq+ravec06r < p. Il suffit de parcourir le cycle dans son
entierqfois, puis de parcourir encorersommets en son sein.La méthode classique pour calculer le produit de deux matrices d"ordrena un coût en(n3). L"algorithme
d"exponentiation rapide appliqué au calcul de Mnaurait donc un coût en(n3logn).Parcours dans un graphe
Exercice 7
Considérons un graphe pour lequel on a pu attribuer un rang à chaque sommet. S"il existait uncircuit dansG, on pourrait considérer le sommetvde ce circuit qui possède le rang minimal ainsi que son
prédécesseurudans ce circuit et aboutir à une contradiction car on aurait à la foisr(u)< r(v)etr(v)6r(u).G
ne possède donc pas de circuit.Réciproquement, supposons que G= (V;E) ne possède pas de circuit, et raisonnons par récurrence surjVj.
Le résul tatest éviden tl orsquejVj= 1.
Si jVj>1, supposons le résultat acquis jusqu"au rangjVj1.Il existe au moins dansGun sommet sans prédécesseur (dans le cas contraire, on pourrait remonter
successivement d"un sommet à un prédécesseur jusqu"à former un cycle). Attribuons le rang 1 à tous ces
sommets, puis supprimons ces sommets et les arcs qui les concernent. On obtient un nouveau grapheG0= (V0;E0), toujours sans circuit, avecjV0j attribuant un rang à chacun de ces sommets, en faisant en sorte que pour toutv2V0,r(v)>2. On obtient k k+1LorsqueGest représenté par sa matrice d"adjacence, déterminer si un sommet n"a pas de prédécesseur a un coût linéaire et calculer P un coût quadratique, donc le coût total de cet algorithme est un O(n3), avecn=jVj.Corrigé des exercices2.5
L"algorithme d"attribution d"un rang à chaque sommet d"un graphe sans circuit s"écrit donc : procedurerang(graphe : G= (V;E)) k 1 S V tant queS,;faire P nv2S8u2S;(u;v)
Exercice 8
a)Notons Nnle graphe d"ordrensans arêtes; alors(Nn) =n. NotonsCnle graphe complet d"ordren>1; alors(Cn) =max((Cn1);1)et par une récurrence immédiate (Cn) = 1. NotonsLnle chemin d"ordren>2non ramifié; alors(Ln) =max((Ln1);1+(Ln2)). On prouve dans ce cas par récurrence que(Ln) =jn2 k. Notons U
nle graphe cyclique d"ordren>3; alors(Un) = max((Ln1);1+(Ln3)) donc(Un) =jn12 k. b)On raisonne par récurrence sur l"ordrendu graphe G.quotesdbs_dbs29.pdfusesText_35
[PDF] Exercice n° HU 0601 - Corrigé
[PDF] 10
[PDF] 14
[PDF] Examen d analyse personnel technique (ANT) - carrieres gouv
[PDF] Examen d 'habileté ? comprendre les lois et règlements (CLRB)
[PDF] Informations admissions 2016-2017 - Gymnase français de Bienne
[PDF] Examen d analyse personnel technique (ANT) - carrieres gouv
[PDF] Examen d 'aptitude au travail de bureau (APTB) - carrieres gouv
[PDF] Atomistique
[PDF] Électrostatique et électrocinétique 1re et 2e années - 2ème édition
[PDF] Examen d 'admission aux études d 'ingénieur civil Université
[PDF] Bachelier en sciences informatiques - Université catholique de
[PDF] Informations générales sur l examen spécial d admission - ULB
[PDF] Comment (Se) préparer (? ) l 'examen d - Université de Mons
