Chapitre 7. Théorie des graphes

Un graphe est un couple G = (X, E) constitué d’un ensemble X, non vide et fini, et d’un ensemble E de paires d’éléments de X. Les éléments de X sont les sommets du graphe G, ceux de E sont les arêtes du graphe G. Un graphe est orienté si les arêtes ont une direction, c’est-à-dire si les couples d’éléments de E sont des listes ordonnées telles que (i, j) ∈ E n’est pas équivalent à (j, i) ∈ E. Ici seuls des graphes non orientés, c’està-dire dont les paires d’éléments de X sont des ensembles non ordonnés ({i, j} ∈ E), sont considérés.
Par exemple, le graphe complet à n sommets Kn est le graphe de sommets X = {1, 2, …, n} ayant comme arêtes les parties à deux éléments de X. En particulier, K4 = (X, E) où X = {1, 2, 3, 4} et E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} }.
— graphes non orientés
— représentation comme dictionnaire
— utilisation des frozensets
— matrice d’adjacence
— recherche de chemins et de triangles
— fonction récursive
Une façon de représenter un graphe G est de le faire avec un dictionnaire dont les clefs sont les sommets et la valeur associée à chaque clef x ∈ X est un ensemble contenant les voisins de x.a) Construire sous forme de dictionnaire les graphes suivants : b) Écrire une fonction complet(n) qui construit comme dictionnaire le graphe complet Kn.c) Un graphe donné sous forme de dictionnaire contient l’information plusieurs fois.
Écrire une fonction corriger(graphe) permettant de rajouter les éléments manquants de sorte que pour tout sommet x, si y appartient à…