Lycée Rue Ahmed Amara Le Kef 4ème EG

Habib Gammar
Exercices (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
0 1 0 1
1 0 1 0
est : M =  
1 0 0 1
 
0 0 1 0
1) a) Donner le degré du sommet B du graphe G. 1) Justifier que G est un graphe orienté.

b) G admet-il un cycle eulérien ? Justifier. 2) a) Recopier et compléter le tableau suivant où d + et d − représentent

2) a) Prouver que G admet au moins une chaîne eulérienne. respectivement le nombre d’arêtes sortantes et le nombre d’arêtes rentrante.
b) Donner un exemple de chaîne eulérienne. A B C D
3) Les sommets sont écrits dans l’ordre alphabétique. d+
Donner la matrice M associée au graphe G. d−

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

Exercice 2
c) Justifier que G admet une chaîne orientée eulérienne.
Un graphe orienté G de sommets 1, 2, 3 et 4 est défini par sa matrice
d) Représenter le graphe G et donner un exemple d’une chaîne orientée
0 0 1 1 eulérienne.
1
0 1 0   2 1 0 3
M = 1 1 3 1
0 0 0 1
  3) On donne M = 
3 
1 0 1 0  2 0 2 1
 
1) a) Quel est le nombre d’arcs aboutissant au sommet 3 ? 0 1 1 1

b) Quel est le nombre d’arcs issus du sommet 3 ? a) Combien de chaînes orientées de longueur 3 relient-elles le sommet B au
sommet C ?
2) Dessiner le graphe G.
b) Donner toutes les chaînes orientées de longueur 3 reliant B à C.
3) Donner deux chemins de longueur 3 allant du sommet 2 au sommet 1.

www.mathsplus.12r.org
 Lycée Rue Ahmed Amara Le Kef 4ème EG
Habib Gammar
Exercices (Les Graphes)
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 1) Préciser le degré de chacun des sommets de G.
3) Répondre par Vrai ou Faux : 2) Montrer qu’il est possible d’emprunter tous les tronçons de route en
a) G est un graphe connexe. parcourant une et une seule fois chacun d’eux.
b) G admet un cycle eulérien. 3) Le facteur peut-il partir du central C et d’y revenir en empruntant une fois
c) G admet une chaîne eulérienne. 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