En terminale

• Graphes: définitions
• Graphe et dictionnaires Python
• Matrice d'adjacence
• Exercices

Nous avons déjà étudié les arbres. Les arbres sont un cas particulier de graphe. Dans un graphe, les sommets peuvent être reliés à autant de noeuds que nécessaire et il peut comporter des boucles: en partant de certains noeud on est capable de revenir sur le noeud de départ. Les arêtes peuvent avoir une valeur numérique, un poids, on parle alors d'arbre valué. Selon la nature du graphe, les arêtes peuvent avoir un sens et des poids différents selon le sens, on parlera alors d'arcs.

Tentons d'être un peu plus rigoureux. On vient de dire qu'un arbre est constitué de sommets et d'arêtes. Si on note S l'ensemble de tous les sommets qui le composent et A l'ensemble de ses arêtes alors on dit que notre graphe G est tel G= (S,A). Le graphe est défini par ses sommets et ses arêtes.

Si les arêtes qui relient les sommets n'ont pas de sens, on dit que le graphe est non orienté. On peut indiférement aller du sommet A vers B que de B vers A.

Si les arêtes ont un sens, on alors employer le mot arc. On parlera alors de graphe orienté. On pourra par exemple pouvoir aller de A vers B mais pas l'inverse. Dans le cas d'un graphe orienté valué on peut aussi avoir des poids différents selon l'arc. Par exemple 10 pour aller de A vers B, mais 8 pour aller de B vers A. Imaginez deux villes qui dans un sens sont reliées par l'autoroute mais pas dans l'autre. Le temps mis dans un sens ne sera pas celui mis dans l'autre.

Un chemin est une suite de sommets tel qu'il existe une arête reliant chacun de ses sommets.

Un graphe est connexe s'il existe toujours un chemin pour relier deux sommets.

Un cycle est une séquence d'au moins trois sommets où le sommet de départ=sommet d'arrivé et tous les autres sommets sont différents. On revient au point de départ.

On peut maintenant redéfinir nos arbres avec le vocabulaire des graphes. Un arbre est un graphe connexe, sans cycle, dont un sommet est particulier: la racine.

Un graphe est dit complet si l'on peut aller directement d'un sommet à un autre.

Les graphes se retrouvent dans de très nombreux domaines. Organiser une tournée de distribution de lettres, cheminement d'un colis, trajet d'une ville à un autre (train, avion, voiture, mélange de tout ça, optimiser sur le temps, sur le prix, sur le coût écologique), métro, réseaux d'ordinateur, distribution du travail à des personnels, réseaux sociaux, les liens sur les sites web. On s'intéressera aussi au problème des 7 ponts de Konigsberg qui a donné naissance à la théorie des graphes en 1741 lorsqu'Euler se promenait dans la ville de Konigsberg appelée aujourd'hui (Kaliningrad).

Il est assez facile de définir un graphe avec des dictionnaires.

graph_dico = {
	    "a": {"a":0,"b": 5, "c": 2},
	    "b": {"a": 4,"b":0},
	    "c": {"a":2,"d": 9, "f":4,"e":6,"c":0},
	    "d": {"c": 7, "a": 3,"d":0},
	    "e": {"a": 1, "b":6,"e":0},
	    "f": {"d": 8,"f":0,}
	}

Dans cette notation Python on voit très clairement les successeurs d'un sommet (appelé descendants dans un arbre). Les successeurs d'un sommet sont les sommet adjacents auxquels on peut accéder directement. Par contre, pour trouver les prédécesseurs, il faut regarder toutes les lignes. Les prédécesseurs d'un sommet sont les sommet adjacents qui mènent directement à ce sommet. Ici on voit que les prédécesseurs de "b" sont "a" et "e".

Généralement on utilise une matrice d'adjacence pour représenter un graphe, qu'il soit orienté ou non.

Une matrice de dimension n x p peut être vue comme un tableau de n lignes et p colonnes. Ce tableau étant complété de nombres appelés les coefficients de la matrice. On notera m_ij le coefficient de la ligne i et de la colonne j de la matrice m.

Dans le cadre des graphes nous aurons des matrices carrées c'est à dire de dimension n x n.

Dans une matrice d'ajacence A, l'élément A_ij indique si l'on peut aller du sommet i vers le sommet j et la valeur de l'arc si le graphe est valué.

Dans le cas d'un graphe non valué, on placera des 0 et 1, ou tout simplement des booléens dans cette matrice.

Si le graphe est non orienté, la matrice sera symétrique : m_ij=m_ji.

Dans le cas de notre exemple graph_dico, cela donne:

graph_dico = {
	    "a": {"a":0,"b": 5, "c": 2},
	    "b": {"a": 4,"b":0},
	    "c": {"a":2,"d": 9, "f":4,"e":6,"c":0},
	    "d": {"c": 7, "a": 3,"d":0},
	    "e": {"a": 1, "b":6,"e":0},
	    "f": {"d": 8,"f":0,}
	}

 0   5   2  -1  -1  -1
 4   0  -1  -1  -1  -1
 2  -1   0   9   6   4
 3  -1   7   0  -1  -1
 1   6  -1  -1   0  -1
-1  -1  -1  -1   8  -1

J'ai mis des -1 lorsque les sommets ne sont pas liés car dans mon exercice les valeurs sont positives.

Dans cette notation matricielle, il est facile de trouver les successeurs. Il suffit de lire en ligne. Pour trouver les prédécesseurs, on lit en colonne.

On en conclut donc qu'il est facile de construire une matrice d'adjacence si l'on connait les successeurs ou les prédécesseurs.

1. blabla
2. blabla