# solutions exercices graphes (jeudi matin) ### exercice 1 ############################################################ # 8 au total (les trouver) ### exercice 2 ############################################################ # Il y a six arcs possibles (0 → 1, 1 → 0, 1 → 2, 2 → 1, 2 → 0, 0 → # 2), chacun pouvant être présent ou absent, soit 2^6 = 64 # possibilités au total. ### exercice 3 ############################################################ # dans la classe matrice d'adjacence class Graphe: # ... def afficher(self): for s in range(self.n): print(s, "->", end="") for v in range(self.n): if self.adj[s][v]: print("", v, end="") print() ### exercice 4 ############################################################ ### exercice 5 ############################################################ # dans la classe dictionnaire d'adjacence class Graphe: # ... def degre(self, s): return len(self.adj[s]) def nb_arcs(self): n = 0 for s in self.adj: n += self.degre(s) return n ### exercice 7 ############################################################ # sommet | ensemble # de | vus # départ | au final # -------+-------------- # 0 | { 0, 1, 3, 2 } # 1 | { 1, 2 } # 2 | { 2 } # 3 | { 3, 1, 2 } ### exercice 8 ############################################################ # sommet | dist # départ | au final # -------+---------- # 0 | { 0:0, 1:1, 3:1, 2:2 } # 1 | { 1:0, 2:1 } # 2 | { 2:0 } # 3 | { 3:0, 1:1, 2:2 } ### exercice 9 ############################################################ def est_connexe(g): """le graphe est-il connexe ? (uniquement pour un graphe non orienté)""" ts = g.sommets() if len(ts) == 0: return True s = ts.pop() vus = set() parcours(g, vus, s) for s in ts: if s not in vus: return False return True ### exercice 10 ############################################################ def parcours_ch(g, vus, org, s): """parcours depuis le sommet s, en venant de org""" if s not in vus: vus[s] = org for v in g.voisins(s): parcours_ch(g, vus, s, v) def chemin(g, u, v): """un chemin de u à v, le cas échéant, None sinon""" vus = {} parcours_ch(g, vus, None, u) if v not in vus: return None ch = [] s = v while s is not None: ch.append(s) s = vus[s] ch.reverse() return ch