from bibimages import * from bibgraphes import * ### exercice 1 2pts (0.5 + 0.5 + 1) # composantes connexes : [0,5 points] # G0 : 2 composantes connexes {A,D,E,F,I} et {B,C,G,H} # G1 : 1 composante connexe {1,2,3,4,5,6} # G2 : 2 composantes connexes {P} et {J,K,L,M,N,O} # Sommet de degré maximal : [0,5 points] # G0 : degré(E) = 4 # G1 : degré(6) = 5 # G2 : degré(M) = degré(P) = 4 # cycle élémentaire de longueur maximale [1 point] # G0 : B->C->H->G->B (cycle de longueur 4) # G1 : 1->6->2->3->4->5->1 (cycle de longueur 6) # G2 : M->L->O->N->M (cycle de longueur 4) ### exercice 2 3pts (1+1+1) ### remplacement de la fonction elementAleatoireListe pour générée la séquence de nombres du sujet seed=0 def elementAleatoireListe(L): global seed L0 = [1, 6, 4, 5, 6, 6, 3, 6, 2, 5, 5,6] seed = seed+1 return L0[seed-1] def mystere1(n): test = 0 cpt = 0 print (test, cpt) ### affichage des valeurs intermédiares while test < n: e = elementAleatoireListe(range(1,7)) print (test, cpt, e) ### affichage des valeurs intermédiares if e == 6 : test = test + 1 print (test, cpt, e) ### affichage des valeurs intermédiares cpt = cpt + 1 print (test, cpt, e) ### affichage des valeurs intermédiares return cpt def mystere2(n): test = 0 cpt = 0 print (test, cpt) while test < n: e = elementAleatoireListe(range(1,7)) print (test, cpt, e) ### affichage des valeurs intermédiares if e == 6 : test = test + 1 else: test = 0 print (test, cpt, e) ### affichage des valeurs intermédiares cpt = cpt + 1 print (test, cpt, e) return cpt print(mystere1(2)) ## 2.1) [1 point] # test 0 0 0 0 0 1 1 1 1 1 1 1 2 2 # cpt 0 0 1 1 1 2 2 3 3 4 4 4 5 # e 1 1 6 6 6 4 4 5 5 6 6 6 # valeur retournée 5 seed=0 ### réinitialisation de la séquence de nombres print(mystere2(2)) ## 2.2) [1 point] # test 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 2 2 # cpt 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 # e 1 1 1 6 6 6 4 4 4 5 5 5 6 6 6 6 6 6 # valeur retournée 6 # 3) [1 point] # La fonction mystere1 retourne le nombre de tirages aléatoires effectués pour obtenir n fois la valeur 6 # La fonction mystere2 retourne le nombre de tirages aléatoires effectués pour obtenir n fois la valeur 6 de manière consécutive ### exercice 3 3pts (2 + 1) ## 3.1) [2 points] def copieCoin(grande,petite): for y in range(hauteurImage(petite)): for x in range(largeurImage(petite)): colorierPixel(grande,x,y,couleurPixel(petite,x,y)) ## 3.2) [1 point] def copieCentre(grande,petite): dx = (largeurImage(grande) - largeurImage(petite))//2 dy = (hauteurImage(grande) - hauteurImage(petite))//2 for y in range(hauteurImage(petite)): for x in range(largeurImage(petite)): colorierPixel(grande,x+dx,y+dy,couleurPixel(petite,x,y)) p = nouvelleImage(30,298) g = nouvelleImage(400,300) for y in range(hauteurImage(p)): for x in range(largeurImage(p)): colorierPixel(p,x,y,(100,20,100)) copieCoin(g,p) for y in range(hauteurImage(p)): for x in range(largeurImage(p)): colorierPixel(p,x,y,(80,90,200)) copieCentre(g,p) # afficherImage(g) # exercice 4 4pts (0,5 + 1 + 2,5) ## 4.1) [0,5 points] ## (a) G_3 ne satisfait pas la propriété P : les arêtes HF et HJ ## ne sont pas couvertes ## (b) G_4 satisfait P ## (c) G_5 ne satisfait pas P : l'arête BC n'est pas couverte ## 4.2) [1 point] def tousMarques(s): for u in listeVoisins(s): if estMarqueSommet(u) == False: return False return True # G = ouvrirGraphe("tgv2005.dot") # nantes = sommetNom(G,'Nantes') # for u in listeVoisins(nantes): # marquerSommet(u) # bdx = sommetNom(G,'Bordeaux') # for u in listeVoisins(bdx): # marquerSommet(u) # demarquerSommet(sommetNom(G,'Toulouse')) # print(tousMarques(nantes)) ## affiche True # print(tousMarques(bdx)) ## affiche False ## 3) [2,5 points] def aretesCouvertes(G): for s in listeSommets(G): if estMarqueSommet(s) == False and tousMarques(s) == False: return False return True # for s in listeSommets(G): # demarquerSommet(s) # marquerSommet(sommetNom(G,'Lille')) # marquerSommet(sommetNom(G,'Paris')) # marquerSommet(sommetNom(G,'Toulouse')) # marquerSommet(sommetNom(G,'Lyon')) # marquerSommet(sommetNom(G,'Lille')) # marquerSommet(sommetNom(G,'Nantes')) # marquerSommet(sommetNom(G,'Marseille')) # print(aretesCouvertes(G)) ## affiche True # demarquerSommet(sommetNom(G,'Marseille')) # print(aretesCouvertes(G)) ## affiche True # demarquerSommet(sommetNom(G,'Toulouse')) # print(aretesCouvertes(G)) ## affiche False ### exercice 5 4pts (2 + 2) ## Préalable def demarquerVoisins(s): for v in listeVoisins(s): demarquerSommet(v) ## 5.1 [2 points] def nbVoisinsDistincts(s): nb=0 demarquerVoisins(s) marquerSommet(s) for v in listeVoisins(s): if not estMarqueSommet(v): marquerSommet(v) nb=nb+1 return nb ## 5.2 [2 points] def estSimplementUniversel(s,G): return (nbVoisinsDistincts(s) == nbSommets(G) - 1) and (degre(s) == nbSommets(G) - 1) ### exercice 6 4pts (0,5 + 1,5 + 1 + 1) # 6.1) [0,5 points] # x---o---o---u # | | # | |e # | | # o---v---o---o---o---y # # 6.2) [1,5 points] # Soient x, y, e, C et G les sommets/arête/cycle/graphe qui vérifient les hypothèses de la proposition 1. # Soit P1 une chaine de x à y passant par e=(u,v) # Soit P2 la chaine de u à v obtenu en supprimant l'arête e du cycle C. # Soit chaine P3 obtenu en remplacant dans P1 l'arête e par la chaine P2. # Cette chaine P3 va de x à y et évite l'arête e. CQFD # # 6.3) [1 point] # il existe une chaîne reliant x et y dans G' # 6.4) [1 point] # le graphe obtenu est toujours connexe