Partie 4 : Graphes¶

Programme officiel (B.O.)¶

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés.	Modéliser des situations sous forme de graphes. Écrire les implémentations correspondantes d'un graphe : matrice d'adjacence, liste de successeurs/prédécesseurs. Passer d'une représentation à une autre.	On s'appuie sur des exemples concrets : réseau social, réseau routier, Internet.

1. Définition¶

1.1 Qu'est-ce qu'un graphe ?¶

Un graphe est constitué de :

sommets (ou nœuds) : les éléments du graphe ;
arêtes (graphe non orienté) ou arcs (graphe orienté) : les liaisons entre sommets.

1.2 Graphe non orienté¶

Les liaisons sont symétriques : si A est relié à B, alors B est relié à A.

    A --- B
    |   / |
    |  /  |
    C --- D

1.3 Graphe orienté¶

Les liaisons ont un sens : A → B ne signifie pas forcément B → A.

    A ──→ B
    ↑   ↙ |
    |  /   ↓
    C ←── D

1.4 Vocabulaire¶

Terme	Graphe non orienté	Graphe orienté
Liaison	Arête	Arc
Voisin	Adjacent	Successeur / Prédécesseur
Nombre de liaisons d'un sommet	Degré	Degré entrant / degré sortant
Chemin fermé	Cycle	Circuit
Tous les sommets accessibles	Connexe	Fortement connexe

1.5 Graphe pondéré¶

Un graphe pondéré associe un poids (coût, distance, durée) à chaque arête ou arc.

    A ─5─ B
    |     |
    3     2
    |     |
    C ─4─ D

2. Exemples concrets¶

Situation	Sommets	Arêtes/Arcs	Orienté ?	Pondéré ?
Réseau routier	Villes	Routes	Non (ou oui pour sens uniques)	Oui (km)
Réseau social (amitié)	Personnes	Relations d'amitié	Non	Non
Réseau social (abonnement)	Personnes	« suit »	Oui	Non
Internet	Routeurs	Liens physiques	Non	Oui (débit)
Web	Pages	Liens hypertextes	Oui	Non
Plan de métro	Stations	Lignes	Non	Oui (temps)

3. Matrice d'adjacence¶

3.1 Principe¶

Un tableau 2D où la case \((i, j)\) vaut 1 si les sommets \(i\) et \(j\) sont reliés, 0 sinon.

Pour le graphe non orienté A-B-C-D ci-dessus :

        A  B  C  D
    A [ 0, 1, 1, 0 ]
    B [ 1, 0, 1, 1 ]
    C [ 1, 1, 0, 1 ]
    D [ 0, 1, 1, 0 ]

matrice = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

3.2 Propriétés¶

Graphe non orienté : la matrice est symétrique (\(M[i][j] = M[j][i]\)).
Graphe orienté : la matrice n'est pas forcément symétrique.
Graphe pondéré : on remplace 1 par le poids et 0 par \(\infty\) (ou None).
Espace mémoire : O(n²) où n est le nombre de sommets.

3.3 Avantages et inconvénients¶

Avantage	Inconvénient
Vérifier si deux sommets sont voisins en O(1)	Occupe O(n²) de mémoire
Simple à implémenter	Gaspillage si le graphe a peu d'arêtes

4. Liste d'adjacence¶

4.1 Principe¶

Un dictionnaire où chaque sommet est associé à la liste de ses voisins (ou successeurs pour un graphe orienté).

graphe = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D"],
    "D": ["B", "C"]
}

4.2 Graphe orienté¶

graphe_oriente = {
    "A": ["B"],
    "B": ["D"],
    "C": ["A"],
    "D": ["C"]
}

4.3 Graphe pondéré¶

graphe_pondere = {
    "A": [("B", 5), ("C", 3)],
    "B": [("A", 5), ("D", 2)],
    "C": [("A", 3), ("D", 4)],
    "D": [("B", 2), ("C", 4)]
}

4.4 Avantages et inconvénients¶

Avantage	Inconvénient
Économe en mémoire pour les graphes peu denses	Vérifier si deux sommets sont voisins en O(degré)
Parcourir les voisins d'un sommet est rapide

5. Passage d'une représentation à l'autre¶

5.1 Matrice → Liste d'adjacence¶

def matrice_vers_liste(matrice, sommets):
    graphe = {}
    for i in range(len(sommets)):
        voisins = []
        for j in range(len(sommets)):
            if matrice[i][j] == 1:
                voisins.append(sommets[j])
        graphe[sommets[i]] = voisins
    return graphe

5.2 Liste d'adjacence → Matrice¶

def liste_vers_matrice(graphe, sommets):
    n = len(sommets)
    matrice = [[0] * n for _ in range(n)]
    index = {s: i for i, s in enumerate(sommets)}
    for sommet in graphe:
        for voisin in graphe[sommet]:
            matrice[index[sommet]][index[voisin]] = 1
    return matrice

sommets = ["A", "B", "C", "D"]
mat = [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]
print(matrice_vers_liste(mat, sommets))
# {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C']}

6. Mesures sur un graphe¶

6.1 Degré d'un sommet¶

def degre_matrice(matrice, sommet):
    return sum(matrice[sommet])

def degre_liste(graphe, sommet):
    return len(graphe[sommet])

6.2 Nombre d'arêtes¶

def nb_aretes(matrice):
    total = sum(matrice[i][j] for i in range(len(matrice))
                for j in range(len(matrice)))
    return total // 2

6.3 Implémentation avec une classe¶

class Graphe:
    def __init__(self, sommets):
        self.sommets = sommets
        self.adjacence = {s: [] for s in sommets}

    def ajouter_arete(self, s1, s2):
        self.adjacence[s1].append(s2)
        self.adjacence[s2].append(s1)

    def voisins(self, s):
        return self.adjacence[s]

    def degre(self, s):
        return len(self.adjacence[s])

    def nb_aretes(self):
        return sum(len(v) for v in self.adjacence.values()) // 2

    def __str__(self):
        lignes = []
        for s in self.sommets:
            lignes.append(f"{s} → {self.adjacence[s]}")
        return "\n".join(lignes)

g = Graphe(["A", "B", "C", "D"])
g.ajouter_arete("A", "B")
g.ajouter_arete("A", "C")
g.ajouter_arete("B", "C")
g.ajouter_arete("B", "D")
g.ajouter_arete("C", "D")
print(g)
print(f"Degré de B : {g.degre('B')}")    # 3
print(f"Nombre d'arêtes : {g.nb_aretes()}")  # 5

À retenir¶

Concept	Description
Graphe	Sommets reliés par des arêtes (non orienté) ou des arcs (orienté)
Matrice d'adjacence	Tableau 2D, symétrique pour un graphe non orienté. O(n²) mémoire
Liste d'adjacence	Dictionnaire sommet → liste de voisins. Économe en mémoire
Degré	Nombre de voisins d'un sommet
Graphe pondéré	Chaque arête porte un poids (distance, coût)
Conversion	On peut passer d'une représentation à l'autre