Bac ES 2014 Afrique Exercice 3 Spécialité Corrigé

• Enoncé voir Exercice 3
• A.1.a) G n'est pas complet : il y a des sommets qui ne sont pas reliés entre eux par une arête,
  par exemple : E et F ne sont pas reliés par une arête
• A.1.b) G est connexe : il n'y a pas de point ou d'ensemble de points isolé
  tous les sommets sont reliés entre eux par une chaîne
  ( remarque : la différence entre complet et connexe est la longueur des chemins reliant 2 sommets
    complet : chemins de longueur 1 ; connexe : chemins de longueur quelconque )
• A.2.a) degré(S) = nombre d'arêtes partant du sommet S

  Sommet	A	B	C	D	E	F	G	H	I
  Degré	4	5	4	4	2	2	3	4	2

• A.2.b) Il y a 2 sommets de degré impair : on ne peut pas revenir au point de départ pas de cycle Eulérien
  (pour avoir un cycle Eulérien, il ne faudrait aucun noeud de degré impair)
  mais on peut passer par toutes les arêtes 1 fois : chaîne Eulérienne d'extrêmités B et G
  
• A.3.a) Matrice d'adjacence M :
  élément M(i,j) = 1 s'il existe une arête allant du sommet i (ligne) au sommet j (colonne)

  	A	B	C	D	E	F	G	H	I
  A	0	1	1	1	0	0	0	1	0
  B	1	0	1	1	1	1	0	0	0
  C	1	1	0	0	0	0	1	1	0
  D	1	1	0	0	1	1	0	0	0
  E	0	1	0	1	0	0	0	0	0
  F	0	1	0	1	0	0	0	0	0
  G	0	0	1	0	0	0	0	1	1
  H	1	0	1	0	0	0	1	0	1
  I	0	0	0	0	0	0	1	1	0

  vérification 1 : la somme des 1 dans chaque ligne ou colonne doit être égale au degré du sommet
  vérification 2 : la matrice doit être symétrique car les arêtes ne sont pas orientées
• A.3.b) Calcul du coefficient (7, 4) de la matrice M³ : M³ = M × M² ( ou M² × M )
  il est obtenu par le produit de la 7^ème ligne de M (sommet G) avec la 4^ème colonne de M² (sommet D)
  M³(7,4) = ∑_k M(7,k) × M²(k,4)     soit : M³(G,D) = ∑_k M(G,k) × M²(k,D)
  coef = ( 0, 0, 1, 0, 0, 0, 0, 1, 1 ) × ^t( 1, 3, 2, 4, 1, 1, 0, 1, 0 )
  coef = 0×1 + 0×3 + 1×2 + 0×4 + 0×1 + 0×1 + 0×0 + 1×1 + 1×0 = 2 + 1 = 3
  ( remarque M³(G,D) donne le nombre de trajets de 3 arêtes entre G et D passant par k :
    2 trajets passant par C et 1 trajet passant par H)
• B.1) faire un graphe correspondant au plan du lycée avec les noms des pièces (en abrégé)
      on voit mieux les connexions entre pièces
  degré des pièces = nombre de portes (en tournant autour de la pièce) :

  SdP	CDI	Ca	Ad	H1	H2	Vs&I	B1	B2
  4	2	2	4	5	4	4	3	2

  
  on commence par identifier les pièces avec des degrés uniques :
  • degré(B) = degré(Hall 1) = 5     B = Hall 1
  • degré(G) = degré(Bât. 1) = 3     G = Bât. 1
  ensuite, on recherche les pièces reliées à celles déjà identifiées :
      (triangles dont 2 sommets sont déjà identifiés)
  • C et Hall 2 sont reliées à B(Hall 1) et G(Bât. 1)     C = Hall 2
  • A et Administration sont reliées à B(Hall 1) et C(Hall 2)     A = Administration
  • H et Vie Scolaire et Infirmerie sont reliées à C(Hall 2) et G(Bât. 1)     H = Vie Scolaire et Infirmerie
  • I et Bât. 2 sont reliées à H(Vie Scolaire et Infirmerie) et G(Bât. 1)     I = Bât. 2
  • D et Salle des Professeurs sont reliées à A(Administration) et B(Hall 1)     D = Salle des Professeurs
  • E, F, CDI, Cantine sont reliées à B(Hall 1) et D(Salle des Professeurs)     E = CDI et F = Cantine
        (ou l'inverse)
  Récapitulatif :

  Sommet du graphe	A	B	C	D	E	F	G	H	I
  Lieu du Lycée	Admin.	Hall 1	Hall 2	Salle des Professeurs	CDI	Cantine	Bât. 1	Vie Sco. et Infirmerie	Bât. 2

• B.2) trajets du Bâtiment 1 (G) à la Salle des Professeurs (D)
  la matrice M³ donne le nombre de trajets en 3 arêtes : G correspond à la ligne 7 et D correspond à la colonne 4 (coefficient déjà calculé en 3.b)
  le coeff(7,4) de M³ = 3   :   il y a 3 trajets de 3 arêtes entre G et D
  liste des 3 trajets : 1) arêtes de départ et arêtes d'arrivée possibles

  Bâtiment 1 (G)

  Bâtiment 2 (I) Vie Sco. et Infirmerie (H) Hall 2 (C)

  arête ?

  Admin. (A) Hall 1 (B) CDI (E) Cantine (F)

  Salle des Prof. (D)

  Liaisons existantes de longueur 1 entre les lieux des colonnes 2 et 4 ?
  • Bât.2 (I) : aucune
  • Vie Sco. et Infirmerie (H) : Administration (A)
  • Hall 2 (C) : Administration (A), Hall 1 (B)
  • (on passe par les sommets de contribution non nulle lors du calcul de M³(7,4) : C et H)
  Soient les 3 trajets suivants : (G H A D), (G C A D), (G C B D)

  Bâtiment 1 (G)	Vie Sco. et Infirmerie (H)	Admin. (A)	Salle des Prof. (D)
  	Hall 2 (C)	Admin. (A)
  		Hall 1 (B)

• B.3.a) On peut visiter le Lycée en suivant la chaîne Eulérienne : Hall 1 (B) −> Bât 1 (G)
  Le départ et l'arrivée sont aux 2 noeuds de degrés impairs.
• B.3.b) trajet le plus court entre G et D par l'algorithme de Dijkstra :
  On part du plus petit sommet qui n'a pas encore été traité : il est à une distance minimale du point de départ
  On garde la distance minimale des sommets connectés (en mémorisant son origine pour refaire le parcours)
  G(dist=0) → H(dist=40), I(dist=20) C(dist=90)
  I(dist=20) → H(dist=45 > 40) rejeté
  H(dist=40) → A(dist=100), C(dist=65 < 90) accepté
  C(dist=65) → A(110 > 100) rejeté, B(dist=95)
  B(dist=95) → A(125 > 100) rejeté, D(dist=175), B(dist=145), F(dist=130)
  A(dist=100) → D(dist=170 < 175) accepté
  F(dist=130) → D(dist=165 < 170) accepté
  E(dist=145) → D(205 > 165) rejeté

  Sommet	A	B	C	D	E	F	G	H	I
  	∞	∞	∞	∞	∞	∞	0	∞	∞
  G(0)	∞	∞	90 (G)	∞	∞	∞		40 (G)	20 (G)
  I(20)	∞	∞	90 (G)	∞	∞	∞		40 (G)
  H(40)	100 (H)	∞	65 (H)	∞	∞	∞
  C(65)	100 (H)	95 (C)		∞	∞	∞
  B(95)	100 (H)			175 (B)	145 (B)	130 (B)
  A(100)				170 (A)	145 (B)	130 (B)
  F(130)				165 (F)	145 (B)
  E(145)				165 (F)
  D(165)

  Il faut au minimum 165 secondes pour aller de G à D :
  reconstitution du trajet depuis l'arrivée : D (165) <− F (130) <− B (95) <− C (65) <− H (40) <− G (0)
  trajet : ( G H C B F D ) soit (Bât.1, VieSco&Infirmerie, Hall2, Hall1, Cantine, SalledesProf.)

retour au menu : math TES