cours terminale ES enseignement de spécialité

Introduction à la théorie des graphes

I - Graphes premières définitions

De manière générale, un graphe est un ensemble de sommets et d'arêtes (ou arcs) reliant ces sommets.
Il existe différents types de graphes, orientés ou non, ou autorisant plusieurs arcs entre deux sommets.

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Graphe G1

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Graphe G2

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Graphe G3

Graphe : L'illustration svg n'est pas visible par votre navigateur.

Graphe G4

1 - Définitions

Un graphe non orienté G=SA est déterminé par la donnée de deux ensembles :

  • un ensemble fini non vide S dont les éléments sont appelés sommets ;
  • un ensemble A de paires de sommets appelées arêtes.

Si S=x1x2xn est l'ensemble des sommets d'un graphe G, une arête a de l'ensemble A s'écrit a=xixjxi et xj sont les extrémités de a.
Les sommets xi et xj sont alors adjacents dans le graphe G et on dit qu'ils sont incidents avec l'arête a.
Lorsque les deux extrémités sont confondues xi=xj l'arête s'appelle une boucle.
Deux arêtes sont dites parallèles lorsqu'elles ont mêmes extrémités.

ordre d'un graphe

On appelle ordre d'un graphe le nombre (n) de sommets de ce graphe.

exemple

Les graphes G1 et G2 sont d'ordre 4 ; le graphe G3 est d'ordre 5 et le graphe G4 est d'ordre 7.

graphe simple

Un graphe est dit simple si deux sommets distincts sont joints par au plus une arête et s'il est sans boucle.


graphe orienté

Un graphe peut être orienté, une arête est alors appelée un arc. Un arc est défini par un couple ordonné xixj de sommets.


remarque

À tout graphe orienté, on peut associer un graphe simple.

Par exemple sur un plan de ville où sont indiquées les rues en sens uniques, un piéton ne tiendra pas compte de l'orientation pour se déplacer.

Au graphe orientéGraphe orienté : L'illustration svg n'est pas visible par votre navigateur.on associe le graphe simpleGraphe orienté : L'illustration svg n'est pas visible par votre navigateur.

sous graphe

Il arrive que dans certains problèmes on ait besoin de considérer une partie d'un graphe :

G'=S'A' est un sous-graphe de G=SA si S' est un sous ensemble de S et A' un sous ensemble de A tel que les extrémités des arêtes de A' sont des sommets de S'.
Si A' est constitué de l'ensemble des arêtes de A ayant pour extrémités les sommets de S' alors on dit que G'=S'A' est le sous-graphe engendré par S'.

exemple

Graphe G : L'illustration svg n'est pas visible par votre navigateur.Sous graphe : L'illustration svg n'est pas visible par votre navigateur.Sous graphe : L'illustration svg n'est pas visible par votre navigateur.
Graphe GG1 est un sous graphe de GG2 est le sous graphe de G engendré par S3S4S5S6S7

graphe complet

Un graphe complet Kn est un graphe simple d'ordre n1 dont tous les sommets sont deux à deux adjacents.

Graphe complet K3 : L'illustration svg n'est pas visible par votre navigateur.Graphe complet K4 : L'illustration svg n'est pas visible par votre navigateur.Graphe complet K4 planaire : L'illustration svg n'est pas visible par votre navigateur.Graphe complet K5 : L'illustration svg n'est pas visible par votre navigateur.
K3Deux représentations du K4K5

2 - Degré d'un sommet

On appelle degré d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois). Ce degré vaut 0 si le sommet est isolé.

exemple

Graphe G : L'illustration svg n'est pas visible par votre navigateur.

Dans le graphe ci-contre, les degrés des sommets sont :

SommetsS1S2S3S4S5S6S7
Degrés2423210

degré d'un sommet dans un graphe orienté

Soit s un sommet d'un graphe orienté G.

  • On note d+s le degré extérieur du sommet s, c'est-à-dire le nombre d'arcs ayant s comme extrémité initiale.
  • On note d-s le degré intérieur du sommet s, c'est-à-dire le nombre d'arcs ayant s comme extrémité finale.

Le degré du sommet s est : ds=d+s+d-s

exemple

Graphe orienté : L'illustration svg n'est pas visible par votre navigateur.

Dans le graphe ci-contre, les degrés des sommets sont :


remarque

Dans un graphe orienté, la somme des degrés extérieurs et la somme des degrés intérieurs sont égales au nombre d'arcs.
Si on note a le nombre d'arcs d'un graphe orienté alors d+s=d-s=a.

Par exemple si dans une réunion on échange des cadeaux, le nombre de cadeaux offerts est égal au nombre de cadeaux reçus, c'est le nombre de cadeaux échangés.

théorème

La somme des degrés de tous les sommets d'un graphe est égale à deux fois le nombre d'arêtes de ce graphe ; c'est donc un nombre pair.

démonstration

Lorsqu'on additionne les degrés des sommets, une arête est comptée deux fois, une fois pour chaque extrémité.

exemple

Est-il possible de tracer cinq segments sur une feuille, de telle manière que chaque segment en coupe exactement trois autres ?

On modélise la situation à l'aide d'un graphe d'ordre 5 dont les sommets représentent les segments. Deux sommets sont adjacents si les deux segments ont une intersection.

Ainsi, il faudrait tracer un graphe d'ordre 5 dont tous les sommets seraient de degré 3. Ce qui est impossible puisque la somme des degrés de tous les sommets d'un graphe est un nombre pair.

corollaire

Dans un graphe, le nombre de sommets impairs est un entier pair.

démonstration

Soit p la somme des degrés des sommets pairs et m la somme des degrés des sommets impairs.
m+p est égal à la somme des degrés des sommets c'est donc un nombre pair comme p est un nombre pair, on en déduit que m est un nombre pair.
Or une somme d'entiers impairs est paire si, et seulement si, il y a un nombre pair de termes.
Par conséquent, le nombre de sommets impairs est un entier pair.

proposition

Dans un graphe simple d'ordre n>1, il existe deux sommets distincts si et sj ayant le même degré.

démonstration

Soit G un graphe simple d'ordre n>1. Le degré d'un sommet s quelconque du graphe G est un entier ds tel que : 0dsn-1.

Supposons que les degrés des sommets soient différents.
Les degrés des n sommets sont les entiers 01n-1 et il existe un sommet si de degré 0 et un sommet sj de degré n-1.

Or si dsj=n-1 cela signifie qu'il est adjacent à tous les sommets du graphe et en particulier au sommet si donc dsi1. Ce qui est en contradiction avec dsi=0.

3 - Représentation matricielle d'un graphe

Soit G=SA un graphe d'ordre n dont les sommets sont numérotés de 1 à n.
La matrice d'adjacence de G est égale à la matrice carrée M=mi,j de dimension n×n où le terme mi,j est égal au nombre d'arêtes d'extrémités les sommets si et sj.
Dans le cas d'un graphe orienté, mi,j est égal au nombre d'arcs ayant pour origine le sommet si et pour extrémité finale le sommet sj.

exemples

  1. Graphe orienté G1 : L'illustration svg n'est pas visible par votre navigateur.

    La matrice d'adjacence du graphe orienté G1 est MG1=1100100011000010


  2. Graphe simple G2 : L'illustration svg n'est pas visible par votre navigateur.

    La matrice d'adjacence du graphe simple G2 est MG2=0110101011010010


remarques

  1. La matrice d'adjacence d'un graphe non orienté est symétrique.

  2. La diagonale de la matrice d'adjacence d'un graphe simple ne comporte que des 0.

  3. La demi somme de tous les coefficients de la matrice d'adjacence d'un graphe non orienté est égale au nombre d'arêtes de ce graphe.

  4. La somme de tous les coefficients de la matrice d'adjacence d'un graphe orienté est égale au nombre d'arcs de ce graphe.

    • La somme des coefficients de la ligne i est égale au nombre de successeurs du sommet si.
    • La somme des coefficients de la colonne i est égale au nombre de prédécesseurs du sommet si.

4 - Graphes isomorphes

Deux graphes isomorphes ont la même structure : peu importe la façon dont ils sont dessinés, il est possible de déplacer les sommets pour que l'un soit la copie conforme de l'autre.

exemple

Considérons les trois graphes ci-dessous :

Graphe A : L'illustration svg n'est pas visible par votre navigateur.Graphe B : L'illustration svg n'est pas visible par votre navigateur.Graphe C : L'illustration svg n'est pas visible par votre navigateur.

Les trois graphes ont le même ordre (6), le même nombre d'arêtes (6) et les sommets des trois graphes sont tous de degré 3.

Or dans B il y a deux sous graphes complets d'ordre 3 ce qui n'est pas le cas pour les graphes A et C. Donc B n'est pas isomorphe à A et C.

Montrons que les graphes A et C sont isomorphes.

Graphe A : L'illustration svg n'est pas visible par votre navigateur.Graphe A : L'illustration svg n'est pas visible par votre navigateur.

Les sommets étant numérotés comme indiqué ci-dessus les deux graphes ont la même matrice d'adjacence : MA=MC=010101101010010101101010010101101010.
Donc les graphes A et C sont isomorphes.

remarques


suivant>> Chaîne, cycle

[ Accueil ]


Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.