4.G.Ex.Graphes .pdf


Nom original: 4.G.Ex.Graphes.pdfTitre: 4.G.Ex.GraphesAuteur: Habib Gammar

Ce document au format PDF 1.6 a été généré par PDFCreator Version 0.9.7 / GPL Ghostscript 8.63, et a été envoyé sur fichier-pdf.fr le 01/05/2014 à 10:22, depuis l'adresse IP 185.26.x.x. La présente page de téléchargement du fichier a été vue 794 fois.
Taille du document: 424 Ko (2 pages).
Confidentialité: fichier public


Aperçu du document


Lycée Rue Ahmed Amara Le Kef
Habib Gammar

Exercices

4ème EG

(Les Graphes)

1/2

Exercice 1

Exercice 3

Soit le graphe G ci-contre :

On considère un graphe G de sommets A, B, C et D dont la matrice associée

1) a) Donner le degré du sommet B du graphe G.

0 1 0 1
1 0 1 0

est : M = 
1 0 0 1


0 0 1 0
1) Justifier que G est un graphe orienté.
2) a) Recopier et compléter le tableau suivant où d + et d − représentent

b) G admet-il un cycle eulérien ? Justifier.

respectivement le nombre d’arêtes sortantes et le nombre d’arêtes rentrante.

2) a) Prouver que G admet au moins une chaîne eulérienne.
b) Donner un exemple de chaîne eulérienne.

A

C

D

d+

3) Les sommets sont écrits dans l’ordre alphabétique.

d−

Donner la matrice M associée au graphe G.

b) Le graphe G admet-il un cycle orienté eulérien ?

Exercice 2
Un graphe orienté G de sommets 1, 2, 3 et 4 est défini par sa matrice
0
1
M =
0

1

B

0 1 1
0 1 0 
0 0 1

0 1 0

1) a) Quel est le nombre d’arcs aboutissant au sommet 3 ?

c) Justifier que G admet une chaîne orientée eulérienne.
d) Représenter le graphe G et donner un exemple d’une chaîne orientée
eulérienne.
 2 1 0 3
1 1 3 1
3

3) On donne M = 
 2 0 2 1


0 1 1 1
a) Combien de chaînes orientées de longueur 3 relient-elles le sommet B au
sommet C ?

b) Quel est le nombre d’arcs issus du sommet 3 ?
2) Dessiner le graphe G.
3) Donner deux chemins de longueur 3 allant du sommet 2 au sommet 1.

b) Donner toutes les chaînes orientées de longueur 3 reliant B à C.

www.mathsplus.12r.org

Lycée Rue Ahmed Amara Le Kef
Habib Gammar

Exercices

(Les Graphes)

4ème EG
2/2

Exercice 4

Exercice 5

On considère le graphe G ci-dessous

Un facteur doit, dans sa journée, prendre le courrier du central C et se rendre
à six localités de la ville qu’on note A 1 , A 2 , A 3 , A 4 , A 5 et A 6 .
Les tronçons de route qu’il peut emprunter sont représentés par les arêtes du
graphe G ci-dessous.
Sur chaque arête est indiquée la longueur, en mètres, du tronçon
correspondant.

1) Recopier le tableau suivant et le compléter :
Sommet

1

2

3

4

5

6



Degré
2) Ecrire dans chaque cas, la réponse exacte parmi les trois propositions.
a) L’ordre du graphe est :

2

4

7

b) Le nombre d’arêtes du graphe est :

7

1

22

c) Le nombre chromatique du graphe est :

3

4

7

3) Répondre par Vrai ou Faux :
a) G est un graphe connexe.
b) G admet un cycle eulérien.
c) G admet une chaîne eulérienne.

1) Préciser le degré de chacun des sommets de G.
2) Montrer qu’il est possible d’emprunter tous les tronçons de route en
parcourant une et une seule fois chacun d’eux.
3) Le facteur peut-il partir du central C et d’y revenir en empruntant une fois
et une seule tous les tronçons de route ?
4) Déterminer le plus court chemin menant du central C à la localité A 5 .
www.mathsplus.12r.org


4.G.Ex.Graphes.pdf - page 1/2


4.G.Ex.Graphes.pdf - page 2/2



Télécharger le fichier (PDF)


4.G.Ex.Graphes.pdf (PDF, 424 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


4 g ex graphes
serie02 gra
serie graphes
theorie de graphe
serie graphe
theorie des graphes