II. Vocabulaire sur les graphes

Introduction

Exemple 1

On peut modéliser des réseaux informatiques par une structure appelée graphe. Dans cet exemple, les lettres A, B et C représentent des routeurs et les lignes entre eux représentent leurs connexions.

Exemple 2

On peut également utiliser des graphes pour représenter les relations entre utilisateurs de réseaux sociaux. Considérons un réseau social sur lequel :
- A est ami avec B, C et D
- B est ami avec A et D
- C est ami avec A, E et D
- D est ami avec tous les autres abonnés
- E est ami avec C, D et F
- F est ami avec E et D

Représenter ce réseau social sous la forme d’un graphe.

A. Définitions et vocabulaire

Définition

Un graphe G est un couple G = (V,E) avec V un ensemble de sommets, représentés par des points, et E un ensemble d’arêtes, représentées par des lignes (V pour Vertex, soit sommet en anglais, E pour Edge, soit arête).

Vocabulaire :

• l’ordre d’un graphe est le nombre de ses sommets,
• 2 sommets sont dit adjacents s’ils sont reliés par une arête,
• le degré d’un sommet est le nombre d’arêtes issues de ce sommet.

Exemples

1. Le graphe de l’exemple 1 est d’ordre 3, et chacun de ses sommets est adjacent aux deux autres et donc de degré 2.

2. Quel est l’ordre du graphe représentant le réseau social d’introduction (exemple 2) ? Quels sommets sont adjacents et quel est le degré de chacun d’entre eux ?

Vocabulaire

• On appelle chaîne toute suite d’arêtes dont l’extrémité de l’une (sauf la dernière) est l’origine de la suivante. Sa longueur correspond au nombre d’arêtes.
• On appelle cycle une chaîne fermée dont toutes les arêtes sont distinctes.

Exemple 3

Identifier une chaîne de longueur 3 :
Identifier un cycle :

B. Les différents types de graphes

B.I. Graphes non-orientés

Définition

Un graphe non-orienté est un graphe dont les arêtes n’ont pas de sens.

Cela signifie que, pour un graphe G = (V,E) avec V = {A,B,C}, les éléments (A,B) et (B,A) sont identiques. C'est le cas de l'exemple 1.

B.II. Graphes orientés

Définition

Un graphe orienté est un graphe dont les liens, les arcs, ont un sens.

Cela signifie que, pour un graphe G = (V,E) avec V = {A,B,C}, les éléments (A,B) et (B,A) sont distincts.

Exemple 6

Imaginons un site web composé de 3 pages nommées A, B et C et représenté ci-contre :
- sur A sont présents des liens vers B et C,
- sur B est présent un lien vers C.

Vocabulaire

Soit (A,B) un arc de G :
- A est appelé le prédécesseur de B,
- B est appelé le successeur de A.
- Un chemin est une suite d’arcs dont l’extrémité de l’un (sauf la dernière) est l’origine du suivant.

B.III. Graphes pondérés

Définitions

On dit qu’un graphe est pondéré quand ses arêtes ou ses arcs sont couplés avec des nombres. Ceux-ci sont appelés des poids.

On associe un chemin dans un graphe pondéré à un poids en effectuant la somme des poids de ses différentes arêtes.

Exemple 7 :

Un réseau routier représentant les connexions entre villes, avec comme poids le nombre de km les séparant.

Donner différents chemins possibles pour aller de G à E et leur poids associé.