Cours

MATHÉMATIQUES · Tle TI

Chapitre : Notion de graphes · Leçon 1

Quelques vocabulaires

Graphes, degrés, chaînes, connexité, matrice d’adjacence.

www.ndolomath.com

Cours de Mathématiques : « Quelques vocabulaires », proposé par ndolomathndolomath

Vocabulaire des graphes

💡 Idée principale : Un graphe est formé de sommets reliés par des arêtes (ou des arcs s’il est orienté). On étudie l’ordre, les degrés, les chaînes et cycles, la connexité, les graphes complets, et on code un graphe par sa matrice d’adjacence, dont les puissances comptent les chaînes de longueur donnée.

Ce que tu vas apprendre

Modéliser une situation par un graphe simple ou orienté.
Utiliser le vocabulaire : ordre, degré, chaîne, cycle, graphe connexe, complet, pondéré.
Écrire la matrice d’adjacence d’un graphe et interpréter ses puissances.

Pourquoi cette leçon ?

Réseaux routiers, réseaux sociaux, circuits électriques, organisation d’un emploi du temps : les graphes modélisent toutes les situations où des objets sont reliés entre eux.

Prérequis : vérifie tes bases

Dessine un graphe à 4 sommets où chaque sommet est relié à tous les autres.

Calcule le produit

{(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})}^{2}

Combien de poignées de main échangent 5 personnes qui se saluent toutes ?

Situation problème : Le réseau de bus

Une ville a cinq arrêts de bus principaux $A$ , $B$ , $C$ , $D$ , $E$ . Il existe des lignes directes $A$ – $B$ , $A$ – $C$ , $B$ – $C$ , $B$ – $D$ , $C$ – $E$ , $D$ – $E$ .
Combien de trajets en exactement deux étapes permettent d’aller de $A$ à $D$ ? Comment les compter sans les dessiner un à un ?

www.ndolomath.com

Cours de Mathématiques : « Quelques vocabulaires », proposé par ndolomathndolomath

Activité d’apprentissage

On modélise le réseau par un graphe et sa matrice d’adjacence $M$ .

Dessine le graphe et donne le degré de chaque sommet.
Écris la matrice d’adjacence $M$ (sommets dans l’ordre $A, B, C, D, E$ ).
Calcule $M^{2}$ et lis le coefficient de la ligne $A$ , colonne $D$ .
Réponds à la situation problème.

Graphes et degrés

Un graphe simple est formé de sommets et d’arêtes reliant deux sommets distincts, sans arête multiple. L’ordre est le nombre de sommets ; le degré d’un sommet est le nombre d’arêtes qui en partent. Somme des degrés

= 2 \times

nombre d’arêtes. Un graphe complet

K_{n}

\frac{n (n - 1)}{2}

arêtes.

Exemple à traiter : Existe-t-il un graphe simple à 5 sommets de degrés 4, 3, 3, 2, 1 ? À 6 sommets de degrés 3, 3, 3, 3, 3, 2 ?

R2 · Chaînes, cycles, connexité

Une chaîne est une suite d’arêtes consécutives ; sa longueur est le nombre d’arêtes. Un cycle est une chaîne fermée aux arêtes distinctes. Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne. La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie ; le diamètre est la plus grande distance.

Exemple à traiter : Calcule le diamètre du graphe du réseau de bus.

Matrice d’adjacence

La matrice d’adjacence

M = (m_{i j})

d’un graphe d’ordre

n

a pour coefficient

m_{i j}

le nombre d’arêtes (ou d’arcs) de

i

vers

j

. Le coefficient

(i, j)

M^{k}

est le nombre de chaînes (ou chemins) de longueur

k

i

j

Exemple à traiter : Calcule

M^{3}

pour le réseau de bus et donne le nombre de trajets en 3 étapes de

A

E

www.ndolomath.com

Cours de Mathématiques : « Quelques vocabulaires », proposé par ndolomathndolomath

Erreurs fréquentes

⚠ Graphe orienté

Dans un graphe orienté, la matrice n’est pas forcément symétrique.

⚠ Chaînes et chemins

M^{k}

compte toutes les chaînes, même celles qui repassent par un sommet.

Exercice d’application

Un tournoi oppose 6 équipes, chacune rencontrant toutes les autres une fois. Modélise par un graphe ; combien de matchs ?
Écris la matrice d’adjacence du graphe orienté : $1 \to 2$ , $2 \to 3$ , $3 \to 1$ , $1 \to 3$ . Combien de chemins de longueur 3 vont de 1 à 1 ?
Réponds à la situation problème.

À retenir

Somme des degrés = 2 × arêtes. Connexe : tout couple relié.

(M^{k})_{i j}

= nombre de chaînes de longueur

k

i

j