The Maths Tailor

THE MATHS TAILOR

1. Le vocabulaire des graphes

1.1. Définitions de base

Définition—Graphe non orienté

- On appelle graphe non orienté un ensemble de points, appelés sommets, reliés par des lignes, appelées arêtes.
- L'ordre du graphe est le nombre de sommets.
- Le degré d'un sommet est le nombre d'arêtes partant de ce sommet.
- Deux sommets reliés par une arête sont adjacents.
- Une boucle est une arête dont les deux extrémités ont le même sommet.

Définition—Graphe complet et graphe simple

- Un graphe est dit complet si deux sommets quelconques sont adjacents.
- Un graphe est dit simple s'il ne possède ni boucle, ni arête multiple (plusieurs arêtes entre deux mêmes sommets).

Proposition—Somme des degrés

La somme des degrés de tous les sommets d'un graphe est égale au double du nombre d'arêtes.

Démonstration : Chaque arête est comptée exactement deux fois lorsqu'on fait la somme des degrés, une fois pour chaque sommet.

Démonstration bientôt disponible

Méthode—Appliquer la propriété de la somme des degrés

Exemple a) Un hectogone (polygone à 100 côtés) avec toutes ses diagonales forme un graphe. Combien possède-t-il de segments ?

En chaque sommet, le graphe possède 99 arêtes. La somme des degrés est

99 \times 100 = 9900

. Le graphe possède

9900 \div 2 = 4950

arêtes.

Exemple b) Cinq joueurs souhaitent organiser un tournoi où chaque joueur rencontre trois autres. Est-ce possible ?

La somme des degrés serait

3 + 3 + 3 + 3 + 3 = 15

, donc le graphe aurait

15 \div 2 = 7, 5

arêtes. Impossible — ce tournoi n'est pas réalisable.

1.2. Chaînes, cycles et connexité

Définition—Chaîne, cycle et connexité

Dans un graphe non orienté :
- Une chaîne est une succession d'arêtes mises bout à bout.
- La longueur d'une chaîne est le nombre d'arêtes qui la composent.
- Une chaîne est fermée si ses extrémités coïncident.
- Un cycle est une chaîne fermée dont les arêtes sont toutes distinctes.
- Un graphe

G

est connexe si chaque couple de sommets est relié par une chaîne.

Graphes

1. Le vocabulaire des graphes

1.1. Définitions de base

1.2. Chaînes, cycles et connexité

1. Le vocabulaire des graphes

1.1. Définitions de base

1.2. Chaînes, cycles et connexité