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

GRAPHES - EXERCICES CORRIGES. Compilation réalisée à partir d'exercices de BAC TES On a représenté par le graphe ci-dessous les sommets B C

Graphes Pour la Terminale ES

18 oct. 2002 1.3 Quelques exercices suppl ementaires . ... 1.4.3 Chaines eul eriennes dans les graphes orient es . . . . . . . . . . . . . . . . . . 12.

Baccalauréat ES spécialité Index des exercices avec des graphes

On oriente et on pondère le graphe G ci-dessus pour qu'il représente un réseau les planches est illuminée par un très grand nombre de spots qui.

Cours exercices TES spé Chapitre 1 Graphes Année 2008-2009

T ES Spé chapitre1. Chapitre 1 Résolution de problèmes à l'aide de graphes. Thème 1. Graphes non orientés & Matrices associées.

Introduction à la théorie des graphes

Les graphes en Terminale ES. 34. Exercices. 35. Solutions des exercices Exercice. G = (X A) est un graphe orienté

TD n°2 - Terminale ES Spé Les Graphes Graphes pondérés et

Exercice 2. Asie 2016 - partie 3 (c). On oriente et on pondère le graphe G ci-dessus pour qu'il représente un réseau d'irrigation.

Théorie des graphes et optimisation dans les graphes Table des

Exercice : Dessiner un graphe non orienté complet à 4 sommets. Opérations sur les matrices d'adjacence : le test de l'existence d'un arc ou d'une arête ...

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

Exercice : Trouver le nombre chromatique c du graphe ci-contre. On a : ? = 4 donc c ? 5. Les points A B et C forment un sous graphe complet d'ordre

Exercices de bac sur les graphes (feuille no 1 )

suivant des salles S A

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

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 :

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.

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_dbs20.pdfusesText_26

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

Page 1 sur 9 Terminale ES Spé : Graphes

1. VOCABULAIRE DE BASE

Exemple :

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

A B C D E F

Chaque poisson est représenté par un point.

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

Définitions :

Exemple :

Page 2 sur 9 Terminale ES Spé : Graphes

Propriété :

La somme S des degrés da du graphe.

S = 2 a.

Exemple :

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

On a : a = 18 2 = 9.

Exercice :

Chaque joueur est représenté par un sommet.

On aurait : S = 5 3 = 15.

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

Définition :

Exemple :

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é :

Remarque :

Page 3 sur 9 Terminale ES Spé : Graphes

Définition :

Remarque :

Définition :

Exemple :

Sommet Couleur Remarque

B (2) (1) interdite

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

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

Le nombre chromatique est 4.

Propriété :

Le complet n est n.

Page 4 sur 9 Terminale ES Spé : Graphes

Méthode :

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-

Propriété :

LQIpULHXURXpJDOjquotesdbs_dbs20.pdfusesText_26