Mathématique m1414

Les graphes

Un graphe est un ensemble de liens qui relient des éléments entre eux.

Les liens sont représentés par des lignes que l’on appelle arêtes ou par des arcs.

Les éléments sont représentés par des points que l’on appelle sommets. Les éléments peuvent être des lieux, des personnes, des tâches, etc.

Dans la représentation graphique d'un graphe:

  • Les sommets sont généralement identifiés par une lettre minuscule, une lettre majuscule, un nombre ou un mot.
  • Les arêtes sont généralement nommées à l'aide des lettres désignant ses extrémités dans n'importe quel ordre. 

Voici un exemple de graphe qui traduit une situation bien précise. Les sommets représentent des îles et les arêtes représentent des ponts.

Situation réelle


Graphe

Le graphe complet et connexe

Un graphe complet est un graphe dont chaque sommet est relié directement à tous les autres sommets.

​Graphe complet
Graphe non complet​
d1414i10.PNGd1414i11.PNG

Un graphe est connexe quand tout sommet peut être relié à tout autre sommet par une arête ou une suite d’arêtes. Le graphe connexe est un graphe en un seul morceau.

 

 

L'ordre d'un graphe

L'ordre d'un graphe correspond au nombre de sommets contenus dans un graphe.

d1414i13.PNGd1414i12.PNG
​L'ordre du graphe ci-dessus est de 5.
L'ordre du graphe ci-dessus est de 4. ​

Le degré d'un sommet

Le nombre de fois qu’un sommet est touché par une arête est le degré de ce sommet .

Si plus d’une arête relient deux sommets, ces arêtes sont dites parallèles .

Une boucle est une arête qui lie un sommet à lui-même. Celle-ci compte pour une arête, mais pour 2 degrés.

 



Le degré du sommet C = 4
Le degré du sommet B = 2
Le degré du sommet A = 2
Le degré du sommet E = 2
Le degré du sommet D = 2

Le nombre d’arêtes du graphe est 6.

 

La somme des degrés de tous les sommets d'un graphe est toujours le double du nombre d'arêtes du graphe. Dans l'exemple précédent, il y a 6 arêtes et la somme des degrés de tous ses sommets est 12.

Les vidéos
Les exercices
Les références