Notions sur les graphes

Cours – graphe

Delhomme Fabien

27 novembre 2022

Qu’est-ce qu’un graphe ?

Definition (Graphe)
Un graph est un ensemble de sommets reliés par des arrêtes.

1

Exemples : graphe d’un réseau social

On peut représenter des réseaux d’amitiés dans
un graphe.

2

Distance dans un graphe

Definition (Distance dans un graphe)
Deux sommets sont dits à une distance n
lorsqu’il sont séparés d’au plus n arrêtes.

Example
La distance entre Jean et Paul est de 2.

3

Distance dans un graphe

Definition (Distance dans un graphe)
Deux sommets sont dits à une distance n
lorsqu’il sont séparés d’au plus n arrêtes.

Example
La distance entre Jean et Paul est de 2.

3

Rayon dans un graphe

Definition (Rayon dans un graphe)
Le rayon d’un graphe est la plus petite
distance à laquelle puisse se trouver un
sommet de tous les autres.

Calculez un rayon :

• Mettre une étiquette sur chaque somme
qui correspond à la distance maximum
entre ce sommet et un autre sommet du
graphe

• Prendre le minimum de ces étiquettes.

4

Centre(s) dans un graphe

Definition (Centre(s) dans un graphe)
Un centre est un sommet qui admet comme
distance maximum avec tous les autres le
rayon du graphe.

5

Exercices

Calculer le rayon de ce graphe, et déterminer le.s centre.s.

6