# EXERCICE 1 #Q1. G_0 : non, existence noeud isolée, G_1: oui, G_2: non, par ex., il n'existe pas de chaîne entre C et H #Q2. A:4, a:5, n'importe lequel 2. #Q3. B-C-D-E-G-B, e-f-g-e, E-F-G-H-I-E # EXERCICE 2 logique ### question 1 ### # a est vraie, on prend x=-1. # la négation est: ∀𝑥 ∈ ℝ ∃ 𝑦 ∈ ℝ 𝑦^2 ≤ x ### question 2 ### (forme p=>q où p="n^2 est impair" et q="n est impair") # contraposée: si n est pair alors n^2 est pair (forme non q => non p). Posons n=2p où p est un entier naturel alors n^2=(2p)^2=2*(2p^2) on retrouve la forme 2q où q=2p donc n^2 est également pair. # Par le principe de contraposition, on a démontré la proposition initiale est vraie. # négation : (n^2 est impair) et (n est pair) est fausse (forme p et non q) # réciproque : si n est impair alors n^2 est impair (forme q=>p) # EXERCICE 3 graphes from bibgraphes import * isocaedre = ouvrirGraphe("isocaedre.dot") #Q1 n-1 #Q2 def sommetEstUniversel(G:graphe, s: sommet) -> bool: return degre(s) == nbSommets(G) - 1 print(sommetEstUniversel(isocaedre, listeSommets(isocaedre)[0])) #Q3 def nbSommetsUniversels(G:graphe) -> int: n = 0 for s in listeSommets(G): if sommetEstUniversel(G, s): n = n + 1 return n print(nbSommetsUniversels(isocaedre)) #Q4 # Version simpliste: def grapheEstComplet(G:graphe) -> int: return nbsommetsUniversels(G) == nbSommets(G) # Version un peu plus efficace def grapheEstComplet(G:graphe) -> int: for s in listeSommets(G): if not sommetEstUniversel(G, s): return False return True print(grapheEstComplet(isocaedre)) # EXERCICE 4 def mystere1(img1, img2, y1, y2, dx): larg=largeurImage(img1) for x in range (larg): for y in range(y1, y2): (r,g,b)=couleurPixel(img1, x, y) colorierPixel(img2, (x+dx)%larg, y, (r,g,b)) def mystere2(img1, img2, y1, y2, dx): larg=largeurImage(img1) for x in range (larg): for y in range(y1, y2): (r,g,b)=couleurPixel(img1, x, y) colorierPixel(img2, (x-dx)%larg, y, (r,g,b)) #q1. a #q2. e #q3. La fonction mystere1 décale une bande horizontale de l'image mystere1 vers la droite, de dx pixels. La partie qui déborde à droite est placée à gauche #q4. La fonction mystere2 décale une bande horizontale de l'image mystere1 vers la gauche, de dx pixels. La partie qui déborde à gauche est placée à droite #Q5. from bibimages import * img=ouvrirImage("personnage.jpeg") larg=largeurImage(img) haut=hauteurImage(img) nouvImg1=nouvelleImage(larg,haut) mystere1(img,nouvImg1,0,haut//2,100) mystere2(img,nouvImg1,haut//2,haut,100) afficherImage(nouvImg1) # EXERCICE 5 images from bibimages import * def repliquerCouleursBande(img, d) : l = largeurImage(img) h = hauteurImage(img) for x in range(l): c1 = couleurPixel(img, x, d - 1) c2 = couleurPixel(img, x, h - d) for y in range(d - 1): colorierPixel(img, x, y, c1) colorierPixel(img, x, h - y - 1, c2) imag = ouvrirImage("blesGris.png") #afficherImage(imag) repliquerCouleursBande(imag, 40) #afficherImage(imag) #ecrireImage(imag, "blesGris40.png") # EXERCICE 6 #Q1. Le nombre de sommets parcoursus est inconnu, je vais utiliser une boucle while #Q2. On peut utiliser la fonction estMarqueSommet (on pourrait aussi utiliser des couleurs) def longueurMarcheAlea(s: sommet) -> int: n = 0 while not estMarqueSommet(s): marquerSommet(s) s = elementAleatoireListe(listeVoisins(s)) n = n + 1 return n print(longueurMarcheAlea(listeSommets(isocaedre)[0])) # EXERCICE 7 #Q1. 2n (n arêtes du cycle plus n arêtes incidentes au sommet central) #Q2. 3 (les sommets du cycle) et n (le sommet central) #Q3. n fois 3 plus 1 fois n = 4n #Q4. La somme des degrés étant égale au double du nombre d'arêtes, ce dernier est donc 4n/2 = 2n #Q5. Un cycle élémentaire à 7 sommets #Q6. L'union d'un cycle à 3 sommet et d'un cycle à 4 sommets #a) Si le graphe ne contenait aucun cycle élémentaire, alors la chaîne élémentaire la plus longue possible dans un tel graphe a à ses extrémités des sommets de degré 1, une contradiction. #Alternativement, on peut trouve un cycle élémentaire d'une manière constructive (algorithmique): Partons d'un sommet quelconque par une de ses arêtes incidentes, en marquant les sommets et les arêtes visités. A chaque étape, quand on découvre un nouveau sommet par une des arêtes incidentes, il est possible de continuer (par l'autre arête incidente). Tout sommet visité se voit marquer les deux arêtes incidentes et aussi lui-même. Puisque le graphe est fini, forcément au bout d'un temps on doit retomber sur un sommet déjà marqué. Ceci ne peut être que le sommet de départ, c'est le seul sommet marqué ayant une arête non-marquée. On obtient donc un cycle élémentaire. #a) Si le graphe contenait deux cycles élémentaires disjoints, il ne serait pas connexe (aucune possibilité de relier les deux cycles sans augmenter les degrés). Pareil, si le graphe contenait deux cycles élémentaires pas disjoints, le sommet qu'il partagent mais où ils ne partagent pas les deux arêtes incidentes doit être de degré au moins 3, une contradiction. #E1. Oui, le sommet de degré n doit être relié à tous les autres (comme le graphe est simple), ils sont donc tous accessible entre eux. #E2. Non, par exemple, si on ajoute un sommet universel à l'union de deux cycles disjoints, on obtient un graphe qui n'est pas une roue. #E3. Oui. En supprimant le sommet de degré n, on obtient un graphe avec que des degrés 2, supposé connexe, alors d'après le théorème c'est un cycle élémentaire. En rajoutant le sommet supprimé, on obtien une roue par définition.