Les graphes sont une manière, en informatique, de représenter des données avec des liens. Par exemple (on appellera ce graphe le graphe 1) :

I. Présentation générale

Par exemple, dans le graphe orienté suivant (le graphe 2), les voisins de H sont J et I.

Par exemple :

• dans le graphe 1, et ;
• dans le graphe 2, , et .

II. Chemins, cycles et connexité

Par exemple, AB, BD, DE est un chemin :

Par exemple, HI, IG, GK, KH est un cycle :

Le graphe 1 est connexe. En revanche, le graphe suivant n'est pas connexe :

III. Représentation informatique

Il y a plusieurs manières de représenter les graphes en Python. On va en voir deux principales.

a) Représentation par liste d'adjacence

L'idée ici est de stocker, pour chaque sommet, l'ensemble de ses voisins. Dans le cas des graphes non orientés, on stockera en général les connexions dans les deux sens.

Par exemple, pour le graphe 1, la liste d'adjacence du sommet A est :

['B', 'C', 'E']

Ensuite, on va regrouper toutes ces listes d'adjacence dans un dictionnaire, pour avoir la représentation suivante :

g = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B'],
    'D': ['B', 'E'],
    'E': ['A', 'D']
}

La fonction afficher_graphe (du module affichage du site) dessine un graphe donné par listes d'adjacence :

from affichage import afficher_graphe

afficher_graphe(g)
print(g['B'])        # les voisins de B
print(len(g['B']))   # le degré de B

g = {
    'G': ['H', 'I', 'K'],
    'H': ['I', 'J'],
    'I': ['G'],
    'J': ['K', 'H'],
    'K': ['H'],
    'L': []
}

b) Matrice d'adjacence

Dans le cas de la matrice d'adjacence, on va toujours numéroter les sommets de à .

On va alors se donner une matrice de taille , et à la position , on va placer si l'arête existe, et sinon.

Dans le cas du graphe 1 (avec les sommets A, B, C, D, E numérotés de 0 à 4) :

g = [[0, 1, 1, 0, 1],
     [1, 0, 1, 1, 0],
     [1, 1, 0, 0, 0],
     [0, 1, 0, 0, 1],
     [1, 0, 0, 1, 0]]

print(g[0][1])   # 1 : il y a une arête entre A (0) et B (1)
print(g[2][3])   # 0 : il n'y en a pas entre C (2) et D (3)
print(sum(g[1])) # le degré de B

g = [[0, 1, 1, 0, 1, 0],
     [0, 0, 1, 1, 0, 0],
     [1, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 1, 0],
     [0, 1, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0]]

IV. Pondération

a) Applications

Les graphes se retrouvent un peu partout en informatique :

• pour tout ce qui est carte : une carte de transports en commun est un graphe, par exemple ;
• internet, à deux niveaux :
  • l'architecture physique d'internet est un grand graphe, avec des serveurs, des routeurs et des terminaux reliés par de la fibre optique, des ondes, etc. ;
  • le web : les pages web, et les liens entre elles, sont bien représentées par des graphes.

Dans tous ces exemples, des algorithmes sur les graphes (on en étudiera quelques-uns) sont utilisés. Par exemple, la recherche d'itinéraire de votre appli de carte préférée, le programme qui décide comment acheminer votre message WhatsApp, ou encore les moteurs de recherche (Google).

Dans beaucoup de ces applications, toutes les arêtes ne sont pas égales. Par exemple, un trajet en train peut prendre deux fois plus longtemps qu'un autre.

b) Graphes pondérés

Pour représenter ces différences, on va introduire la pondération.

Voici par exemple quelques villes et le temps de trajet en train entre elles :

c) Implémentation des graphes pondérés

Liste d'adjacence : on peut stocker les poids directement dans la liste d'adjacence, en mettant des couples (voisin, poids) au lieu des simples voisins :

g = {
    'Caen': [('Rennes', 3.5), ('Tours', 3.0), ('Paris', 2.0)],
    'Rennes': [('Caen', 3.5), ('Paris', 2.0)],
    'Paris': [('Caen', 2.0), ('Rennes', 2.0), ('Tours', 1.3), ('Lyon', 2.0)],
    'Tours': [('Caen', 3.0), ('Paris', 1.3), ('Lyon', 3.0)],
    'Lyon': [('Paris', 2.0), ('Tours', 3.0)]
}

afficher_graphe(g)
for (voisin, poids) in g['Caen']:
    print("De Caen à", voisin, ":", poids, "h")

Matrice d'adjacence : on peut mettre le poids de l'arête à la place de , et utiliser une valeur qui n'est pas dans les poids à la place de (par exemple , ou, si ce n'est pas une option, ). Ici, les sommets sont numérotés dans l'ordre Caen, Rennes, Paris, Tours, Lyon.

g = [[-1.0, 3.5, 2.0, 3.0,-1.0],
     [ 3.5,-1.0, 2.0,-1.0,-1.0],
     [ 2.0, 2.0,-1.0, 1.3, 2.0],
     [ 3.0,-1.0, 1.3,-1.0, 3.0],
     [-1.0,-1.0, 2.0, 3.0,-1.0]]

Exercices

def nb_aretes(g):
    total = 0
    for s in g:
        total += len(g[s])
    return total // 2

def matrice_vers_listes(M):
    n = len(M)
    return [[j for j in range(n) if M[i][j] == 1] for i in range(n)]

def degre_max(g):
    meilleur = None
    for s in g:
        if meilleur is None or len(g[s]) > len(g[meilleur]):
            meilleur = s
    return meilleur