Chapitre 6 - Partie 2 : Graphes et représentations

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