from bibV3 import * from PIL.Image import * #### # Exercice 1 # Q1 # mystere(a, d) retourne 2 # Les sommets B et C sont marqués # Q2 # mystere(b, d) retourne 1 # Les sommets A,D,E sont marqués # Q3 # De manière générale, la fonction mystere(u,v) retourne le nombres de sommets # qui sont simultanément voisins de u et de v. #### # Exercice 2 # connexité : # -G0 n'est pas connexe, il possède 3 composantes connexes {{A,F},{B,E,G},{D,C}} # -G1 est connexe # -G2 est connexe # Est-il simple ? # -G0 n'est pas simple car il possède une boucle autour de B # -G1 n'est pas simple car il possèdes 2 aretes entre H et K # -G2 est simple # nombre chromatique # -G0 n'admet pas de coloration propre car il possède une boucle # -le nombre chromatique de G1 est 3. Ce nombre est supérieur ou égal à 3 car # G1 possède un triangle, et on peut le colorier avec 3 couleurs : # couleur(H)=couleur(J)=1; couleur(I) = 2; couleur(K) = 3 # -le nombre chromatique de G2 est 2 : Ce nombre est supérieur ou égal à 2 car # car ce graphe contient des aretes. De plus on peut le 2-colorier : # couleur(sommet de numéro impair) = 1 ; couleur(sommet de numéro pair) = 2 # cycle élémentaire de longueur maximale : # -G0 : [B,B] # -G1 : [H,I,J,K,H] # -G2 : [1,2,3,4,5,6,1] #### # Exercice 3 # Q1 def cullen(n): return n*2**n+1 # Q2 def indiceCullen(x): n = 0 while cullen(n) <=x: n = n + 1 return n - 1 #### # Exercice 4 # Q1 def seuil(img, lim): (large, haut) = img.size for x in range(large): for y in range(haut): (r,g,b) = Image.getpixel(img,(x,y)) if (r+g+b)/3 < lim: Image.putpixel(img,(x,y),(0,0,0)) # Q2 def pixelMaxHaut(img): (large,haut)= img.size for y in range(haut): for x in range(large): (r,g,b) = Image.getpixel(img, (x,y)) if r+g+b > 0: return (x,y) monImage = open('teapot.png') seuil(monImage,100) Image.show(monImage) print(pixelMaxHaut(monImage)) #### # Exercice 5 # Q1 def marqueAvecVoisinNonMarque(G): for s in listeSommets(G): if not estMarqueSommet(s): for t in listeVoisins(s): if estMarqueSommet(t): return t return None # Q2 def marqueVoisins(s): for t in listeVoisins(s): marquerSommet(t) # Q3 def marquerCompConnexe(G,s): marquerSommet(s) while marqueAvecVoisinNonMarque(G) != None: marqueVoisins(marqueAvecVoisinNonMarque(G)) # Q4 marquerCompConnexe(Europe, sommetNom(Europe,'Belgique')) #### # Exercice 6 # Q1 # arete e4 # aretes e6, e7, e8 # Q2 # Montrons ce résultat par l'absurde. # Soit (s,t) une arête d'un arbre G. Supposons que cette arête ne soit pas # un isthme. Cela implique que G\e est connexe, et donc qu'il existe un chemin # entre s et t dans G\e. Si on ajoute à ce chemin, l'arête (s,t) on obtient un # cycle dans G. G étant un arbre, il ne contient pas de cycle. Contradiction. # Q3 # Soit G' une des deux composantes connexes de G\e. G' contient 1 sommet de # degré 2 et k sommets de degré 3. Soit m' le nombre d'arêtes de G'. D'après # la formule des poignées de mains : # 2m' = 2+ 3*k # Cela implique que k doit être un nombre pair. G' possède k+1 sommets, donc # un nombre impair de sommets.