[PDF] sur 9 Terminale ES Spé : Graphes 1. VOCABULAIRE DE BASE a

View - Download sur 9 Terminale ES Spé : Graphes 1. VOCABULAIRE DE BASE a

Previous PDF

Next PDF

Page 1 sur 9 Terminale ES Spé : Graphes

1. VOCABULAIRE DE BASE

a. Graphe

Exemple :

A ; B ; C ; D ; E et F sont 6 poissons.

Dans le tableau ci-dessous, une croix indique que les poissons ne peuvent pas cohabiter dans le même

aquarium.

A B C D E F

A B C D E F Représenter la situation par un schéma (G) où :

Chaque poisson est représenté par un point.

2 poissons qui ne peuvent pas cohabiter sont reliés.

Définitions :

i. Le schéma (G) est un graphe. ii. Les points A ; B ; C ; D ; E et F sont les sommets du graphe. iii. ordre iv. Les segments reliant deux sommets sont des arêtes. v. Deux sommets sont adjacents vi. Le degré s dont ce sommet est une extrémité. vii. Un sommet est isolé viii. Un sous graphe relient ces sommets. ix. Un sous graphe (G1) de (G) est stable x. Un sous graphe (G2) de (G) est complet lorsque ses sommets sont deux à deux adjacents.

Exemple :

" Poissons » D A B C E F (G) D A F (G1) est un sous graphe stable de (G) A B C E (G2) est un sous graphe complet de (G)

Page 2 sur 9 Terminale ES Spé : Graphes

b.

Propriété :

La somme S des degrés da du graphe.

S = 2 a.

Exemple :

" Poissons »

Soit S la somme des degrés et a le nombre :

On a : a = 18 2 = 9.

Exercice :

Peut-entre 5 joueurs de telle sorte que chaque participant joue 3 parties ?

Chaque joueur est représenté par un sommet.

On aurait : S = 5 3 = 15.

Par conséquent, on aurait : a = 15 2 = 7,5 !

c. Matrice associée à un graphe

Définition :

n.

La matrice associée au graphe (G) est la matrice à n lignes et à n colonnes où le terme aij situé à

de la ligne i et de la colonne j est égal i et j.

Exemple :

" Poissons » La matrice associée au graphe (G) est la matrice : M =

0 1 1 0 1 0

1 0 1 0 1 1

1 1 0 0 1 1

0 0 0 0 0 0

1 1 1 0 0 1

0 1 1 0 1 0

Propriété :

La matrice associée à un graphe est symétrique.

Remarque :

iée à un graphe

Page 3 sur 9 Terminale ES Spé : Graphes

2. a.

Définition :

Colorer un graphe consiste à affecter une couleur à chacun de ses sommets de telle sorte que deux

sommets adjacents ne portent pas la même couleur.

Remarque :

n, on peut toujours le colorer en utilisant n couleurs distinctes. b. Nombre chromatique

Définition :

Le nombre chromatique graphe est le plus petit nombre de couleurs permettant de le colorer.

Exemple :

" Poissons »

Sommet Couleur Remarque

A (1)

B (2) (1) interdite

C (3) (1) et (2) interdites

D (1)

E (4) (1), (2) et (3) interdites

F (1)

Le nombre chromatique est 4.

c.

Propriété :

Le complet n est n.

D A B C E F (G) (1) (2) (3) (1) (2) (3) (1) (2) (4)

Page 4 sur 9 Terminale ES Spé : Graphes

d. Algorithme glouton

Méthode :

possible, une couleur déjà utilisée, celle affectée du plus petit numéro.

Exemple :

Colorer le graphe (G) ci-contre :

Sommet Degré Couleur

E 3 (1)

O 3 (2)

R 3 (3)

L 2 (1)

N 2 (2)

Z 1 (1)

Remarque :

Par exemple, en colorant le graphe ci-

couleurs, alors que le nombre chromatique est 2. e. Encadrement du nombre chromatique

Propriété :

LQIpULHXURXpJDOjquotesdbs_dbs47.pdfusesText_47

[PDF] Matrices, valeurs propres et vecteurs propres

[PDF] matriochka signification

[PDF] matrix hair careers

[PDF] mattek sands blessure

[PDF] mattek sands blessure wimbledon

[PDF] mattek sands genou

[PDF] mattek sands knee

[PDF] mattek-sands wimbledon

[PDF] Maturation de l’ARN prémessager en ARN messager : l’épissage

[PDF] Mature d'un mot

[PDF] mature definition

[PDF] mature hairline

[PDF] mature meaning

[PDF] maupassant

[PDF] Maupassant " Madame Baptiste " ( début)