# ============================ # Tracé d'un graphe # avec le module Turtle # Version 3 # # nsi.gecif.net # ============================ """ Cette Version 3 du programme : - trace des graphes d'ordre 2, 3, 4 et 5 en fonction de la matrice d'adjacence - pour tous les graphes le tracé des sommets est automatisé dans une boucle for - pour le graphe d'ordre 5 le tracé des arêtes est automatisé dans 2 boucles for - une fonction afficher_info() permet d'afficher dans la console le contenu des variables """ from turtle import * # =========================================================================== # Définition des fonctions : # =========================================================================== def afficher_info(): # affiche, en cas de besoin, le contenu de certaines variables dans la console : print("Voici le contenu des variables principales :\n") print("matrice_adj : %s" % matrice_adj) print("nbr_sommets : %d" % nbr_sommets) print("liste_sommets : %s" % liste_sommets) print("coord : %s" % coord) # -------------------------------------------------------------------------- def afficher_message(message): # affiche un titre en haut de la fenêtre de la tortue : up() goto(-150,300) write(message) down() # -------------------------------------------------------------------------- def dessiner_sommet(x,y,nom): # dessine un cercle dont les coordonnées du centre sont passées en paramètre rayon=40 up() goto(x,y) down() pensize(8) color('black','white') begin_fill() circle(rayon) end_fill() up() goto(x-rayon//4,y+rayon//2) write(nom,font=('Arial', 24, 'bold')) down() # -------------------------------------------------------------------------- def dessiner_arete(x1,y1,x2,y2): # trace un trait entre 2 points dont les coordonnées sont passées en paramètre up() goto(x1,y1+40) down() pensize(8) goto(x2,y2+40) # =========================================================================== # Programme principal # =========================================================================== """ Nombre de sommets et d'arêtes d'un graphe complet d'ordre n : Nombre de sommets : Nombre d'arêtes du graphe complet : 2 1 3 1+2 = 3 4 1+2+3 = 6 5 1+2+3+4 = 10 6 1+2+3+4+5 = 15 7 1+2+3+4+5+6 = 21 8 1+2+3+4+5+6+7 = 28 9 1+2+3+4+5+6+7+8 = 36 """ # Description du graphe dans une matrice d'adjacence : # il s'agit ici d'un dictionnaire de liste, où les clés portent le nom des sommets matrice_adj={} """ # graphe connexe à 2 sommets (une seule arête) : matrice_adj['A']=['B'] matrice_adj['B']=['A'] # graphe non connexe à 2 sommets (2 sommets isolés) : matrice_adj['A']=[] matrice_adj['B']=[] # graphe non complet à 3 sommets : matrice_adj['A']=['C'] matrice_adj['B']=['C'] matrice_adj['C']=['A','B'] # graphe complet à 3 sommets : matrice_adj['A']=['B','C'] matrice_adj['B']=['A','C'] matrice_adj['C']=['A','B'] # graphe non complet d'ordre 4 : matrice_adj['A']=['B','C'] matrice_adj['B']=['A','D'] matrice_adj['C']=['A','D'] matrice_adj['D']=['B','C'] # graphe complet d'ordre 4 : matrice_adj['A']=['B','C','D'] matrice_adj['B']=['A','C','D'] matrice_adj['C']=['A','B','D'] matrice_adj['D']=['A','B','C'] # graphe non complet d'ordre 5 : matrice_adj['A']=['B','E'] matrice_adj['B']=['A','C'] matrice_adj['C']=['B','D'] matrice_adj['D']=['C','E'] matrice_adj['E']=['D','A'] """ # graphe complet d'ordre 5 : matrice_adj['A']=['B','C','D','E'] matrice_adj['B']=['A','C','D','E'] matrice_adj['C']=['A','B','D','E'] matrice_adj['D']=['A','B','C','E'] matrice_adj['E']=['A','B','C','D'] nbr_sommets=len(matrice_adj) liste_sommets=list(matrice_adj) liste_sommets.sort() coord=[] speed(0) hideturtle() afficher_message("Voici un graphe d'ordre %d dessiné avec le module Turtle" % nbr_sommets) # chaque ordre de graphe (nombre de sommets) est un cas particulier : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # Graphe d'ordre 2 : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - if nbr_sommets==2: # coordonnées des 2 sommets (une liste de dictionnaires) : coord=[{'x':-200,'y':100},{'x':200,'y':-100}] # dessine les arêtes selon la matrice d'adjacence : # (remarque : le graphe complet d'ordre 2 possède 1 arête) if liste_sommets[1] in matrice_adj[liste_sommets[0]]: # sommet 0 adjacent au sommet 1 ? dessiner_arete(coord[0]['x'],coord[0]['y'],coord[1]['x'],coord[1]['y']) # dessine les 2 sommets dans tous les cas : for i in range(2): dessiner_sommet(coord[i]['x'],coord[i]['y'],liste_sommets[i]) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # Graphe d'ordre 3 : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - elif nbr_sommets==3: # coordonnées des 3 sommets (une liste de dictionnaires) : coord=[{'x':-200,'y':200},{'x':200,'y':200},{'x':0,'y':-200}] # dessine les arêtes selon la matrice d'adjacence : # remarque : le graphe complet d'ordre 3 possède 3 arêtes (2+1) if liste_sommets[1] in matrice_adj[liste_sommets[0]]: # sommet 0 adjacent au sommet 1 ? dessiner_arete(coord[0]['x'],coord[0]['y'],coord[1]['x'],coord[1]['y']) if liste_sommets[2] in matrice_adj[liste_sommets[1]]: # sommet 1 adjacent au sommet 2 ? dessiner_arete(coord[1]['x'],coord[1]['y'],coord[2]['x'],coord[2]['y']) if liste_sommets[0] in matrice_adj[liste_sommets[2]]: # sommet 2 adjacent au sommet 0 ? dessiner_arete(coord[2]['x'],coord[2]['y'],coord[0]['x'],coord[0]['y']) # dessine les 3 sommets dans tous les cas : for i in range(3): dessiner_sommet(coord[i]['x'],coord[i]['y'],liste_sommets[i]) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # Graphe d'ordre 4 : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - elif nbr_sommets==4: # coordonnées des 4 sommets (une liste de dictionnaires) : coord=[{'x':-200,'y':200},{'x':200,'y':200},{'x':-200,'y':-200},{'x':200,'y':-200}] # dessine les arêtes selon la matrice d'adjacence : # remarque : le graphe complet d'ordre 4 possède 6 arêtes (3+2+1) if liste_sommets[1] in matrice_adj[liste_sommets[0]]: # sommet 0 adjacent au sommet 1 ? dessiner_arete(coord[0]['x'],coord[0]['y'],coord[1]['x'],coord[1]['y']) if liste_sommets[2] in matrice_adj[liste_sommets[0]]: # sommet 0 adjacent au sommet 2 ? dessiner_arete(coord[0]['x'],coord[0]['y'],coord[2]['x'],coord[2]['y']) if liste_sommets[3] in matrice_adj[liste_sommets[0]]: # sommet 0 adjacent au sommet 3 ? dessiner_arete(coord[0]['x'],coord[0]['y'],coord[3]['x'],coord[3]['y']) if liste_sommets[2] in matrice_adj[liste_sommets[1]]: # sommet 1 adjacent au sommet 2 ? dessiner_arete(coord[1]['x'],coord[1]['y'],coord[2]['x'],coord[2]['y']) if liste_sommets[3] in matrice_adj[liste_sommets[1]]: # sommet 1 adjacent au sommet 3 ? dessiner_arete(coord[1]['x'],coord[1]['y'],coord[3]['x'],coord[3]['y']) if liste_sommets[3] in matrice_adj[liste_sommets[2]]: # sommet 2 adjacent au sommet 3 ? dessiner_arete(coord[2]['x'],coord[2]['y'],coord[3]['x'],coord[3]['y']) # dessine les 4 sommets dans tous les cas : for i in range(4): dessiner_sommet(coord[i]['x'],coord[i]['y'],liste_sommets[i]) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # Graphe d'ordre 5 : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - elif nbr_sommets==5: """ Pour obtenir les coordonnées des 5 sommets d'un pentagone régulier, on trace une étoile à 5 branches avec le programme suivant qui affiche les coordonnées de chacun de ses 5 sommets grâce à la fonction position() : from turtle import * up() goto(-250,-80) down() speed(0) for i in range(5): print(position()) forward(500) left(144) done() """ # coordonnées des 5 sommets (une liste de dictionnaires) : coord=[ {'x':-155,'y':214}, {'x':155,'y':214}, {'x':250,'y':-80}, {'x':0,'y':-262}, {'x':-250,'y':-80}] # dessine les arêtes selon la matrice d'adjacence : # remarque : le graphe complet d'ordre 5 possède seulement 10 arêtes (4+3+2+1) # mais ici on va faire les 25 tests possibles : for i in range(5): for j in range(5): if i!=j and liste_sommets[j] in matrice_adj[liste_sommets[i]]: # le sommet i est-il adjacent au sommet j ? dessiner_arete(coord[i]['x'],coord[i]['y'],coord[j]['x'],coord[j]['y']) # dessine les 5 sommets dans tous les cas : for i in range(5): dessiner_sommet(coord[i]['x'],coord[i]['y'],liste_sommets[i]) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # Graphe d'ordre supérieur, non géné pour le moment : # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - else: # efface la fenêtre de la tortue : clear() # affiche un message sur la fenêtre de la tortue : afficher_message("Le programme ne gère pas encore un graphe à %d sommets" % nbr_sommets) # affiche certaines variables dans la console : afficher_info() done() # =========================================================================== # Fin du programme principal # ===========================================================================