#exercice 1 # connexe : Non (2 composantes ADC et BEG) | oui | oui # sommet deg max : B (degré 3) | K (degré 4) | n'importe lequel (degré 3) #exercice 2 def mystere(n): if n == 0: return 0 k = -1 print (" ", k, n) #ligne ajoutée pour l'affichage des valeurs while n > 0 : ch = n%10 if ch%2 == 0: k = ch n = n // 10 print (ch, k, n) #ligne ajoutée pour l'affichage des valeurs return k mystere(3276) #question 1 # ch | | 6 | 7 | 2 | 3 # k | -1 | 6 | 6 | 2 | 2 # n | 3276 | 327 | 32 | 3 | 0 #question 2 # mystere(3276) vaut 2 #question 3 mystere(511) # mystere (511) vaut -1 #question 4 # De manière générale, mystere(n) retourne le chiffre pair de n le plus à gauche. # Si n est composé que de chiffres impairs, mystere(n) retourne -1 #exercice 3 def auMoinsUnElementCommun(L1, L2): for x in L1: for y in L2: if x == y: return True return False def auMoinsUnElementCommunV2(L1, L2): for x in L1: if x in L2: return True return False print(auMoinsUnElementCommun([2, 15, 17], [5, 32, 12])) print(auMoinsUnElementCommun([2, 15, 17], [5, 32, 12, 2])) #exercice 4 def nbFeuillesAdjacentes(s): nb_feuilles = 0 for s in listeVoisins(s): if degre(s) == 1: nb_feuilles = nb_feuilles + 1 return nb_feuilles def tousOntUneFeuille(G): for s in listeSommets(G): if degre(s) > 1: if nbFeuillesAdjacentes(s) == 0: return False return True #exercice 5 def fusionne(imagePersonnage, imageFond): wF = imageFond.width hF = imageFond.height wP = imagePersonnage.width hP = imagePersonnage.height for y in range (hP): for x in range (wP): c = Image.getpixel(imagePersonnage, (x, y)) if c != (0, 255, 0): Image.putpixel(imageFond, (x, y), c) #exercice 6 from PIL.Image import * def diagonaleCarre(img): l = img.width for x in range(l): Image.putpixel(img, (x,x), (255,255,255)) monImage = new("RGB",(200,200)) diagonaleCarre(monImage) Image.show(monImage) def triangleInferieurGauche(img, c): l = img.width for x in range (l): for y in range(l): if y>=x: Image.putpixel(img,(x,y),c) # autre version possible def triangleInferieurGauche(img, c): l = img.width for x in range (l): for y in range(x,l): Image.putpixel(img,(x,y),c) monImage = new("RGB",(200,200)) triangleInferieurGauche(monImage, (255,255,255)) Image.show(monImage) def drapeau(img): l = img.width for x in range (l): for y in range(l): Image.putpixel(img,(x,y),(0,0,0)) for x in range (l//2,3*l//4): for y in range(l): Image.putpixel(img,(x,y),(128,128,128)) triangleInferieurGauche(img, (255,255,255)) for x in range(l//4): for y in range(l): Image.putpixel(img,(x,y),(128,128,128)) monImage = new("RGB", (200,200)) drapeau(monImage) Image.show(monImage) def rectanglePlein(img, x1, x2, y1, y2, c): for x in range(x1, x2+1): for y in range(y1, y2+1): Image.putpixel(img, (x,y), c) def drapeau(img): l = img.width rectanglePlein(img, 0, l-1, 0, l-1, (0,0,0)) rectanglePlein(img, l//2, 3*l//4, 0, l-1, (128,128,128)) triangleInferieurGauche(img, (255,255,255)) rectanglePlein(img, 0, l//4, 0, l-1, (128,128,128)) monImage = new("RGB", (200,200)) drapeau(monImage) Image.show(monImage) #exercice 7 #question 1 : formule des poignées de mains : la somme des degrés des sommet = 2 fois le nombre d'arêtes #question 2 : non, car la somme des degrés serait alors un nombre impair, ce qui est en contradiction avec la formule des poignées de mains. #question 3 : pour que la somme des degrés soit un nombre pair, il faut un nombre pair de sommets de degré impair. #question 4 : Supposons que les 2 sommets impairs ne sont pas dans la même composante connexe. Soit G1 la composante connexe du premier sommet impair. # ce sous graphe G1 peut également être vu comme un graphe à part entière. Donc il doit vérifier la formule des poignées de mains. Comme on l'a vu à la # question 2 un graphe ne peut avoir 1 seul sommet impair. Contradiction. # On en déduit donc que si un graphe possède 2 sommets impairs, alors ils sont forcément dans la même composante connexe. # Remarque : plus généralement, chaque composante connexe d'un graphe doit possèder un nombre pair de sommets impairs.