################ Exercice 1 ##################### ################################################## # G0 G1 G2 # ========================================================================================================= # Connexe | Oui | Non (e est un sommet isolé) | Non (sommet 4 noin relié au sommet 2) # --------------+----------------------+-----------------------------+-------------------------------------- # degré max | d(E)=8 | d(g)=4 | d(9)=9 # --------------+----------------------+-----------------------------+-------------------------------------- # cycle élém max| A,E,B,C,F,I,H,G,D,A | b,d,h,f,c,b | 4,e9,7,e7,4 # --------------+----------------------+-----------------------------+-------------------------------------- ################ Exercice 2 ##################### ################################################## # 1. # énonce 1: Vrai énoncé 2: Faux # 2. # énonce 1: Vrai énoncé 2: Faux # 3. # énonce 1: Vrai énoncé 2: Vrai # Démonstration: 1./ énoncé 1 # Il suffit de choisir y = x^2 # Démonstration: 2./ énoncé 2 # Il suffit de choisir un x négatif (par exemple -25). Il n'existe # pas de nombre y élevé au carré qui soit négatif dans Z. ################ Exercice 3 ##################### ################################################## # mystere(8, [2,3,6,8,10]) renvoie 3 # mystere(9, [2,3,6,8,10]) renvoie 4 # mystere(12, [2,3,6,8,10]) renvoie 5 # mystere(1, [2,3,6,8,10]) renvoie 0 # La fonction renvoie l'indice du plus petit nombre dans la liste L # mais qui soit supérieur à égal à x. ################ Exercice 4 ##################### ################################################## from bibimages import * # Qs 1) def miroir(img1:image, img2:image): l1 = largeurImage(img1) h1 = hauteurImage(img1) h2 = hauteurImage(img2) for x in range(l1): for y in range(h1): c = couleurPixel(img1,x,y) colorierPixel(img2,x,y,(r,g,b)) colorierPixel(img2,x,h2-(y+1),c) # Qs 2) theiere = ouvrirImage("teapot.png") l = largeurImage(theiere) h = hauteurImage(theiere) nouvelle = nouvelleImage(l, 2*h) miroir(theiere,nouvelle) afficherImage(nouvelle) ################ Exercice 5 ##################### ################################################## from bibgraphes import * from random import * def colorierEnBlanc(G:graphe ): for s in listeSommets(G): colorierSommet(s, "white") # teste si tous les voisins de s sont de couleur blanche def voisinsTousCouleurBlanc(s : sommet) -> bool: for v in listeVoisins(s): if couleurSommet(v) != "white": return False return True #retourne un sommet de couleur blanche dont tous les voisins sont de couleur blanche, None #si il n'existe pas un tel sommet def sommetEtVoisinsTousCouleurBlanc(G:graphe) -> sommet: for s in listeSommets(G): if couleurSommet(s) == "white" and voisinsTousCouleurBlanc(s): return s return None def stable(G : graphe, c : str) -> list: L = [] colorierEnBlanc(G) v = elementAleatoireListe(listeSommets(G)) while v != None : colorierSommet(v, c) L = L + [v] v = sommetEtVoisinsTousCouleurBlanc(G) return L tgv = ouvrirGraphe("tgv2005.dot") Lstable = stable(tgv, "orange") print(Lstable) dessiner(tgv) # Exercice 6 # Q1: $\sum_{i=0}^{i=n-1} x_i$ = somme des degrés de G Or, somme des # degrés de G = 2 |E| (théorème des poignés de mains), donc # $\sum_{i=0}^{i=n-1} x_i$ est pair #Q2: O---O O---O O O #Q3: On partitionne V(G) en deux sous-ensemble A et B. L'ensemble A # contient les sommets de degré 0, et l'ensemble B contient les # sommets de degré 1. # A B # +-----+ +---------+ # | O | | O---O | # | O | | O---O | # | O | | O---O | # | . | | . | # | . | | . | # | . | | . | # | O | | O---O | # | O | +---------+ # | O | # +-----+ # Comme B ne contient que les sommets de degré 1, alors |B| est pair # (car chaque sommet est de degré 1 et que la somme des degrés est # pair). Ainsi, on peut aligner 2 par 2 les sommets dans B (voir # figure ci-dessus) et les connecter par une arêtes, les sommets sont # ainsi tous de degré 1. Ce processus construit finalement un graphe G # ayant la répartition des degrés demandé. #Q4: En ne considérant dans un premier temps uniquement les degrés # $r_i \in {O,1}$, on peut partitionner les sommets de G_0 comme à la # question précédente. # # Une fois cette partition faite, on rajoute sur chaque sommet $s_i$ # pour $i$ allant de 0 à n-1, $d_i$ boucles. L'ajout de $d_i$ boucles # sur le sommet $s_i$ augmente son degré de $2*d_i$. Le degré final de # $s_i$ est donc $x_i=2*d_i+r_i$.