from bibimages import * from bibgraphes import * # Résumé: ### exercice 1 2pts (0.5 + 0.5 + 1) ### exercice 2 4.5pts (1.5 + 0.5 + 0.5 + 2) ### exercice 3 3.5pts (2 + 1.5) ### exercice 4 4pts (2 + 2) ### exercice 5 6pt (1 + 1.5 + 1.5 + 0.5 + 1.5) ### exercice 1 2pts (0.5 + 0.5 + 1) # composantes connexes : [0,5 points] # G0 : 1 composante connexe {1,2,3,4,5} # G1 : 4 composantes connexes {1,2,3,4},{A,B},{C},{D} # G2 : 2 composantes connexes {1,2,3,4,5,6} et {7} # Sommet de degré maximal : [0,5 points] # G0 : degré(1) = 4 # G1 : degré(A) = 2 # G2 : degré(6) = 5 # cycle élémentaire de longueur maximale [1 point] # G0 : 1->2->3->4->5->1 (cycle de longueur 5) # G1 : 1->2->3->4->1 (cycle de longueur 4) # G2 : 1->2->3->4->5->6->1 (cycle de longueur 6) ### exercice 2 [4.5pt] def mystere(n,d): k = 0 p = 0 while n > 0 : ch = n%10 k = k + 1 if ch == d: p = k n = n // 10 return p # 1. [1.5pt] # n : 3767 - - - - - 376 - - 37 - - - 3 - - 0 # k : - 0 - - 1 - - - 2 - - 3 - - - 4 - # p : - - 0 - - 1 - - - - - - 3 - - - - # ch : - - - 7 - - - 6 - - 7 - - - 3 - - # 2. [0.5pt] print(mystere(3767,7)) #3 # 3. [0.5pt] print(mystere(3236,7)) #0 # 4. [2pt] # mystere(n,d) retroune la plus grande position du chiffre d dans n ### exercice 3 [3.5pt] ## 3.1) [2 points] def filigrane(img1, img2): for y in range(hauteurImage(img1)): for x in range(largeurImage(img1)): (r1,g1,b1) = couleurPixel(img1,x,y) (r2,g2,b2) = couleurPixel(img2,x,y) colorierPixel(img2,x,y, ((r1+r2)//2, (g1+g2)//2, (b1+b2)//2)) ## 3.2) [1.5 points] def filigraneBasDroite(img1, img2): for y in range(hauteurImage(img1)): for x in range(largeurImage(img1)): (r1,g1,b1) = couleurPixel(img1,x,y) (r2,g2,b2) = couleurPixel(img2,x,y) colorierPixel(img2, largeurImage(img2)-largeurImage(img1)+x, hauteurImage(img2)-hauteurImage(img1)+y, ((r1+r2)//2, (g1+g2)//2, (b1+b2)//2)) logo = ouvrirImage("logo.jpg") fond = ouvrirImage("road.jpg") filigraneBasDroite(logo, fond) afficherImage(fond) # exercice 4 4pts (2 + 2) ## 4.1 [2pt] def regulier(G): d = degre(elementAleatoireListe(listeSommets(G))) for s in listeSommets(G): if degre(s) != d: return False return True ## 4.2 [2pt] def bienColorie(G): for s in listeSommets(G): for v in listeVoisins(s): if couleurSommet(s) == couleurSommet(v): return False return True print('bienColorie(octaedre) ', bienColorie(octaedre)) print('bienColorie(construireGrille(1,10)) ', bienColorie(construireGrille(1,10))) print('regulier(construireGrille(1,10)) ', regulier(construireGrille(1,10))) print('regulier(octaedre) ', regulier(octaedre)) # Exercice 5 6pt ## 5.1: 1pt # Si chaque personne sauf une serre la main d'exactement 3 personnes, la somme des # des degrés vaut 3 x 20 + 1 = 61. Ce n'est pas possible puisque d'après la # formule des poignées des mains, cela doit être un nombre pair. ## 5.2: 1.5pt # Rappelons que d'après la formule des poignées de main, nous savons que # la somme des degrés vaut précisément 2 x m. Si chaque sommet a un degré # au moins delta, celle-ci vaut au moins n x delta # et donc n x delta <= somme des degrés = 2 x m et donc n <= (2 x m)/delta. ## 5.3: 1.5pt # Supposons par l'absurde que G ne soit pas connexe, et soit u et v deux # sommets n'appartenant pas à une même composante connexe. Par hypothèse, # u et v possèdent chacun au moins p voisins. Comme u et v ne sont pas # dans la même composante connexe, ces deux voisinages sont disjoints # (sinon si u et v ont un voisin commun, on obtient un chemin élementaire # de longueur 2 de u à v). Par conséquent, G possède au moins # 2 x p + 2 (pour u et v) sommets, contradiction. ## 5.4 a-b): 0.5pt # Figure a : o ------ o # \ / # \ / # \ / # o # _________ _________ # Figure b: / \ / \ # o o o # \_________/ \_________/ # # ## 5.4 V/F): 1.5pt # Le graphe est simple, i.e. sans boucle ni arête multiple. # Faux : contre-exemple figure 4b # # Il y a au plus une île d’où partent exactement 4 ponts. # Faux : on peut répéter la construction de la Figure 4b et avoir > 1 sommet # de degré 4 # # Il y a au moins une île d’où partent exactement 2 ponts. # Faux : contre-exemple un graphe avec deux sommets et 4 arêtes multiples #  # Le graphe est connexe et tout sommet est de degré pair, la suppression d’une arête # ne détruit pas la connexité du graphe. # Vrai # # Le graphe est connexe et tout sommet est de degré pair, la suppression d’une arête # ne détruit pas la connexité du graphe, mais il n’y a plus de cycle élémentaire. # Faux : contre-exemple Figure 4b #  # S’il n’y a aucun cycle élémentaire de longueur supérieure ou égale à 3, alors le graphe # contient forcément des arêtes multiples. # Vrai