Formation I.S.N.

Qu'est-ce qu'un graphe ?

Définition et terminologie

On appelle graphe la donnée d'un ensemble de points appelés sommets et d'un ensemble de lignes appelées arêtes qui relient certains sommets entre eux.

Le nombre de sommets d'un graphe s'appelle l'ordre du graphe.

Deux sommets reliés entre eux par une arête sont dits adjacents.

Le degré d'un sommet est le nombre d'arêtes issues de ce sommet.

Un sommet qui n'est adjacent à aucun autre sommet du graphe est dit isolé.



Un graphe est dit complet si deux sommets quelconques distincts sont toujours adjacents.

Autrement dit, tous les sommets sont reliés deux à deux par une arête.



Exemple de graphes
Exemple 1

Le graphe ci-contre est d'ordre 5 car il possède 5 sommets

Les sommets A et B sont adjacents

Les sommets D et E ne sont pas adjacents

Le sommet C est isolé

Exemple 2 Le graphe ci-contre est complet d'ordre 3
Exemple 3 Le graphe ci-contre est complet d'ordre 4

Différents types de graphes

Un graphe peut être orienté ou non-orienté.



Dans un graphe non-orienté, chaque arête peut-être parcourue dans les deux sens.

Exemple 4

Dans un graphe orienté, chaque arête ne peut-être parcourue que dans un seul sens indiqué par une flèche.

Exemple 5

Un graphe (orienté ou non-orienté) peut contenir des boucles c'est-à-dire une arête dont l'origine et l'extrémité correspondent au même sommet (on a par exemple une boucle B sur la représentation précédente).

Propriété de la somme des degrés

On considère un graphe non orienté à \( n \) sommets. Soit \( d_i \) le degré du sommet \( i \), \( 1 \leqslant i \leqslant n \). Soit A le nombre d'arêtes du graphe.

On a \( \;\; A = \frac{1}{2} \sum\limits_{\substack{i=1}}^{n}{d_i} \)

Autrement dit, le nombre d'arêtes est égal à la moitié de la somme des degrés des sommets

Ce résultat s'explique assez facilement: en ajoutant les degrés de chaque sommet (c'est à dire le nombre d'arêtes issues de ce sommet), on comptabilise deux fois chaque arête (une fois avec le sommet d'une extrémité et une seconde fois avec le sommet de l'autre extrémité de l'arête). D'où le résultat.

Il découle de cette propriété que la somme des degrés des sommets est nécessairement paire et donc que le nombre de sommets de degré impair est pair.