Correction de la série Graphes Bac Eco Gestion .pdf


Nom original: Correction de la série Graphes Bac Eco-Gestion.pdf
Auteur: mak

Ce document au format PDF 1.5 a été généré par Conv2pdf.com, et a été envoyé sur fichier-pdf.fr le 25/01/2014 à 00:57, depuis l'adresse IP 197.1.x.x. La présente page de téléchargement du fichier a été vue 1743 fois.
Taille du document: 349 Ko (3 pages).
Confidentialité: fichier public


Aperçu du document


Prof :Khammour.Khalil
Année Scolaire :2013/2014

Série d’exercices :
Graphes(Correction)

4ème Eco-Gestion
Tél :27509639

Exercice n°1 :
1) b)
2) a)
3) c)
4) d)
5) d)
6) c)
7) b)
8) c)
9) c)
10)
11)
12)
13)
14)

d)
a)
a)
a)
b)

Exercice n°2 :
1) a)

Sommets
Degré de sommets de graphe

B
2

C
4

D
4

F
5

N
3

T
4

(Rappel : le degré d’un sommet est égal au nombre d’arêtes dont ce sommet est
l’extrémité)
b) Justifier que le graphe est connexe.
Ce graphe est connexe car tous les sommets peuvent être reliés entre eux par (au
moins) une chaine.
Par exemple, la chaîne BCDNTF contient tous les sommets.
2) L’existence d’un parcours permettant au groupe de passer chaque chemin est liée à
l’existence d’une chaîne eulérienne.
Puisque deux sommets exactement sont de degré impair et que les autres sont de
degré pair, le théorème d’Euler nous permet d’affirmer l’existence d’une telle chaîne
eulérienne, donc d’un tel parcours.
Par exemple, le trajet F-B-C-F-N-T-F-D-C-T-D-N répond au problème.
3) a) Le sommet ayant le plus grand degré est le sommet F, de degré 5.
Le cours nous affirme qu’alors n 5 +1, c’est-à-dire n 6 .
Mr:Khammour.Khalil

Tél:27509639

De plus, le sous-graphe FCTD, d’ordre 4, étant complet, on aura n
moins 4 couleurs pour le colorier).
b)
Sommet
Degré
Couleur
F
5
Rouge
C
4
Vert
D
4
Bleu
T
4
Noir
N
3
Vert
B
2
Noir
 Le nombre chromatique de ce graphe est donc égal à 4

4 (il faudra au

4) On utilise l’algorithme du plus court chemin de Dijkstra pour déterminer une chaîne
qui minimise la distance du trajet entre B et N.
B C
D
F
T
N
Sommet
sélectionné
0
B(0)
0+12=12(B 0+15=15(B)
C(12)
12+3=15(C) 12+2=14(C) 12+4=16(C)
D(14)
14+5=19(D)
14+3=17(D) 14+12=26(D) T(17)
T(16)
17+8=25(T)
16+7=23(T) N(23)
Exercice n°3 :
Le 1er et le 3ème graphe peuvent associés à la matrice, avec les numérotations :

Le deuxième ne possède pas de sommet de degré égal à 4 (« 2 »)

Mr:Khammour.Khalil

Tél:27509639

Mr:Khammour.Khalil

Tél:27509639


Aperçu du document Correction de la  série  Graphes  Bac Eco-Gestion.pdf - page 1/3

Aperçu du document Correction de la  série  Graphes  Bac Eco-Gestion.pdf - page 2/3

Aperçu du document Correction de la  série  Graphes  Bac Eco-Gestion.pdf - page 3/3




Télécharger le fichier (PDF)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00218295.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.