Terminale ES 2016-2017
Kartable
Terminale ES 2016-2017
I

Les graphes non orientés

A

Les principes élémentaires

Graphe

On appelle graphe un ensemble de points et de lignes reliant certains de ces points. Les points sont appelés sommets du graphe, les lignes arêtes du graphe.

-

Ordre d'un graphe

L'ordre d'un graphe désigne le nombre de ses sommets.

-

L'ordre de ce graphe est 6.

Sommets adjacents

Deux sommets d'un graphe reliés par une arête sont dits adjacents.

-

Les sommets 2 et 3 sont adjacents.

Les sommets 2 et 4 ne sont pas adjacents.

Deux sommets peuvent être reliés par plusieurs arêtes.

Degré d'un sommet

Le degré d'un sommet désigne le nombre d'arêtes dont ce sommet est l'origine.

-
  • Le degré du sommet 1 est 4.
  • Le degré du sommet 6 est 2.

Somme des degrés et nombre d'arêtes

La somme des degrés des sommets d'un graphe non orienté est égale au double du nombre d'arêtes que comporte ce graphe.

-
Sommet123456Somme des degrés
Degré42321214

Le nombre d'arêtes de ce graphe est 14÷2=7.

Matrice associée

La matrice associée (ou matrice d'adjacence) à un graphe d'ordre n est une matrice à n lignes et n colonnes, où le terme ai,j est égal au nombre d'arêtes partant du sommet i pour aller jusqu'au sommet j.

-

La matrice associée à ce graphe est :

M=011011101000110100001001100000100100

Sous-graphe

Un sous-graphe est une partie d'un graphe : il ne comporte que certains sommets du graphe initial ainsi que les arêtes reliant ces sommets.

Graphe complet

Un graphe est dit complet si tous ses sommets sont deux à deux adjacents.

-

Le graphe ci-dessus est complet.

B

Les chaînes

Chaîne

Une chaîne est une liste ordonnée de sommets où chaque sommet est adjacent au précédent et au suivant.

-

Le chemin 1 − 2 − 3 − 4 est une chaîne reliant le sommet 1 à 4.

Par contre, 1 − 5 − 6 − 4 n'est pas une chaîne.

Longueur d'une chaîne

La longueur d'une chaîne désigne le nombre de ses arêtes.

-

La chaîne 1 − 2 − 3 − 4 est une chaîne de longueur 3.

Distance entre deux sommets

La distance entre deux sommets est égale à la longueur de la chaîne la plus courte reliant ces deux sommets.

-

La distance entre les sommets 1 et 4 est 2.

Diamètre d'un graphe

Le diamètre d'un graphe est la plus grande distance entre deux sommets.

-

Le diamètre du graphe est la distance entre les sommets 5 et 4, c'est-à-dire 3.

Chaîne fermée

Une chaîne fermée est une chaîne dont le premier sommet est identique au dernier sommet.

-

La chaîne 1 − 2 − 3 − 1 est fermée.

Cycle

Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.

-

La chaîne 1 − 2 − 3 − 4 − 6 − 1 est un cycle.

Chaîne eulérienne

Une chaîne eulérienne est une chaîne formée de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.

-

5 − 1 − 6 − 4 − 3 − 2 − 1 − 3 est une chaîne eulérienne.

Cycle eulérien

Un cycle eulérien est un cycle formé de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.

-

1 − 3 − 2 − 7 − 3 − 5 − 4 − 6 − 2 − 1 est un cycle eulérien.

Graphe connexe

Un graphe est dit connexe si pour tout couple de sommets, il existe une chaîne reliant ces deux sommets.

Le graphe ci-dessous n'est pas connexe : le sommet 5 est isolé.

-

Théorème d'Euler

  • Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède aucun, ou exactement deux sommets de degré impair.
  • Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède que des sommets de degré pair.

Si un graphe connexe possède exactement deux sommets de degré impair notés A et B, alors toute chaîne eulérienne de ce graphe part de A et termine en B ou part de B et termine en A.

Il existe des algorithmes permettant de déterminer une chaîne eulérienne (ou un cycle eulérien selon les cas).

Nombre de chaînes de longueur p

On considère la matrice Mp, puissance p -ième de la matrice M associée à un graphe d'ordre n. Son terme mi,j est égal au nombre de chaînes de longueur p partant du sommet i vers le sommet j.

-

La matrice associée à ce graphe est :

M=011011101000110100001001100000100100

On trouve :

M3=257146524212742511125024411200621400

Il existe donc une unique chaîne de longueur 3 reliant le sommet 5 à 3 (5 − 1 − 2 − 3).

De même, il existe deux chaînes de longueur 3 reliant le sommet 2 à lui même (2 − 1 − 3 − 2 et 2 − 3 − 1 − 2).

II

Les graphes étiquetés et les graphes pondérés

A

Les graphes étiquetés

Graphe étiqueté

On appelle graphe étiqueté un graphe dont chacune des arêtes est associée à une étiquette. Une étiquette peut correspondre à un texte ou à un nombre.

-
B

Les graphes pondérés

Graphe pondéré

On appelle graphe pondéré un graphe étiqueté dont les étiquettes sont toutes des nombres positifs.

L'étiquette d'une arête est alors appelée poids de l'arête.

-
C

Plus courte chaîne

Poids d'une chaîne

Le poids d'une chaîne d'un graphe pondéré est la somme des poids des arêtes qui forment cette chaîne.

-

Le poids de la chaîne 7 − 6 − 1 − 2 est : 20+8+10=38.

Plus courte chaîne

On appelle plus courte chaîne entre deux sommets une chaîne de poids minimum reliant ces deux sommets.

-

La plus courte chaîne reliant le sommet 7 à 3 est 7 − 6 − 5 − 3 de poids 28.

On peut déterminer la plus courte chaîne à l'aide de l'algorithme de Dijkstra.

III

Les graphes orientés

A

Définition

Graphe orienté

Un graphe orienté est un graphe dont les arêtes ont un sens.

-
Le terme ai,j de la matrice associée à un graphe orienté est égal au nombre d'arêtes d'origine i et d'extrémité j.
-

La matrice associée à ce graphe est : M=0100010100100100001100010.

B

Les graphes probabilistes

Graphe probabiliste

Un graphe probabiliste est un graphe orienté pondéré où, pour chaque sommet, la somme des poids des arêtes sortantes est égale à 1.

-

Etat

Dans un graphe probabiliste, chaque sommet correspond à un état.

Etat probabiliste

L'état probabiliste d'un graphe probabiliste est la loi de probabilité sur l'ensemble des états. Cette loi est présentée sous la forme d'une matrice ligne, où chaque terme est égal à la probabilité de l'état correspondant.

Matrice de transition

La matrice de transition d'un graphe probabiliste d'ordre n est une matrice à n lignes et n colonnes, où le terme ai,j est égal au poids de l'arête d'origine i et d'extrémité j ou à 0 si cette arête n'existe pas.

-

La matrice de transition de ce graphe est : 0,70,150,30,85.

Etat probabiliste à l'instant n

Soit M la matrice de transition d'un graphe probabiliste d'ordre n, et soit P0 l'état initial.
La matrice ligne Pk de l'état probabiliste à l'instant k est égale à :

Pk=P0×Mk

L'état stable du graphe, s'il existe, est la matrice ligne Pkk est le plus petit entier naturel tel que Pk=Pk+1.

Quand il existe, l'état stable vérifie l'équation X=XM d'inconnue XM est la matrice de transition.

Cet état stable est indépendant de l'état initial.

Si M est la matrice de transition d'un graphe probabiliste d'ordre 2 ou 3 et si aucun coefficient de M n'est nul, le graphe probabiliste admet un état stable.

-

La matrice de transition de ce graphe est : 0,70,150,30,85.

C'est donc une matrice d'ordre 2 dont aucun coefficient n'est nul.

Ce graphe admet donc un état stable.

pub

Demandez à vos parents de vous abonner

Vous ne possédez pas de carte de crédit et vous voulez vous abonner à Kartable.

Vous pouvez choisir d'envoyer un SMS ou un email à vos parents grâce au champ ci-dessous. Ils recevront un récapitulatif de nos offres et pourront effectuer l'abonnement à votre place directement sur notre site.

J'ai une carte de crédit

Vous utilisez un navigateur non compatible avec notre application. Nous vous conseillons de choisir un autre navigateur pour une expérience optimale.