Cours
MATHÉMATIQUES · 1re D
Chapitre : Introduction à la théorie des graphes · Leçon 1

Présentation du concept de graphe

Sommets, arêtes, degrés et vocabulaire des graphes.
www.ndolomath.com
Cours de Mathématiques : « Présentation du concept de graphe », proposé par ndolomathndolomath
Concept de graphe
💡 Idée principale : Un graphe est formé de sommets reliés par des arêtes. Il modélise des réseaux : routes entre villes, amitiés entre personnes, matchs d’un tournoi. On définit l’ordre, le degré d’un sommet, les sommets adjacents, les graphes complets, les chaînes et les cycles.
Ce que tu vas apprendre
  1. Modéliser une situation par un graphe.
  2. Connaître le vocabulaire : sommets, arêtes, ordre, degré, sommets adjacents, boucle, graphe simple, graphe complet.
  3. Reconnaître une chaîne, un cycle, un graphe connexe.
Pourquoi cette leçon ?
Le réseau routier entre les villes du Cameroun, les liaisons entre les ordinateurs d’un lycée, un réseau social : ces structures se dessinent et s’étudient avec des graphes.
Prérequis : vérifie tes bases
1
Combien de poignées de main s’échangent 4 personnes qui se saluent toutes ?
2
Dessine 5 points et relie-les tous deux à deux.
3
Que signifie « relier » deux villes sur une carte routière ?
Situation problème : Le réseau routier

On s’intéresse à cinq villes : Yaoundé (Y), Douala (D), Bafoussam (B), Édéa (E) et Kribi (K). Il existe une route directe entre Y et D, Y et B, Y et E, D et B, D et E, E et K, D et K.
Comment représenter clairement ce réseau ? Quelle ville est la plus reliée ? Peut-on aller de Bafoussam à Kribi ?

www.ndolomath.com
p1
Cours de Mathématiques : « Présentation du concept de graphe », proposé par ndolomathndolomath
Activité d’apprentissage

On représente chaque ville par un point et chaque route directe par un trait.

  1. Dessine le graphe de ce réseau.
  2. Compte, pour chaque ville, le nombre de routes qui en partent.
  3. Trouve un trajet de B vers K. Existe-t-il un trajet qui part de Y et y revient en passant par trois autres villes sans repasser par une route ?
  4. Réponds à la situation problème.
R1
Graphe et vocabulaire
Un graphe (non orienté) est formé d’un ensemble de sommets et d’un ensemble d’arêtes reliant deux sommets. L’ordre est le nombre de sommets. Deux sommets reliés par une arête sont adjacents. Une boucle relie un sommet à lui-même. Un graphe simple n’a ni boucle ni arête multiple.
Exemple à traiter : Modélise par un graphe le tournoi où 5 équipes A, B, C, D, E ont joué : A–B, A–C, B–D, C–D, D–E. Donne son ordre.
R2 · Degré et graphe complet
Le degré d’un sommet est le nombre d’arêtes qui en partent (une boucle compte deux fois). Un graphe est complet si deux sommets quelconques sont adjacents ; le graphe complet d’ordre n est noté Kn.
Exemple à traiter : Dessine K4 et K5 ; donne le degré de chaque sommet et le nombre d’arêtes.
www.ndolomath.com
p2
Cours de Mathématiques : « Présentation du concept de graphe », proposé par ndolomathndolomath
R3
Chaînes, cycles, connexité
Une chaîne est une suite d’arêtes consécutives reliant deux sommets ; sa longueur est son nombre d’arêtes. Un cycle est une chaîne fermée dont les arêtes sont distinctes. Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne.
Exemple à traiter : Dans le graphe du réseau routier, donne une chaîne de longueur 3 de B à K et un cycle passant par Y. Le graphe est-il connexe ?
Erreurs fréquentes
⚠ Dessin et graphe
Deux dessins différents peuvent représenter le même graphe : seules les liaisons comptent.
⚠ Degré d’une boucle
Une boucle ajoute 2 au degré du sommet.
Exercice d’application
  1. Dans une classe, 6 élèves : Ali connaît Bella et Chantal ; Bella connaît Chantal et Dieudonné ; Éric connaît Fanta. Modélise par un graphe. Est-il connexe ?
  2. Combien d’arêtes possède le graphe complet K10 ?
  3. Réponds à la situation problème.
À retenir
Graphe : sommets + arêtes. Degré : nombre d’arêtes issues du sommet. Kn : tous les sommets adjacents. Connexe : deux sommets toujours reliés par une chaîne.
www.ndolomath.com
p3
Préparation du PDF…