Scribd
Importer
124 vues3 pages

Exercices de Graphes et Optimisation 2023

Ce document contient plusieurs exercices sur les graphes et l'optimisation. Les exercices portent sur la détermination des propriétés de graphes, le calcul d'arbres couvrants minimums et le calcul de plus courts chemins.

Transféré par

Montassar Zarai
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
124 vues3 pages

Exercices de Graphes et Optimisation 2023

Ce document contient plusieurs exercices sur les graphes et l'optimisation. Les exercices portent sur la détermination des propriétés de graphes, le calcul d'arbres couvrants minimums et le calcul de plus courts chemins.

Transféré par

Montassar Zarai
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Ecole Nationale d’Electronique et des

A. U : 2022-2023
Télécommunications de Sfax

Matière : Graphes et Optimisation

Enseignant : Boukthir HADDAR Auditoire : 2 LTIC

EXERCICES DE REVISION

Exercice 1

Soit le graphe 𝐺 suivant :

1) Ce graphe est-il complet ? connexe ?

2) Déterminer le degré de chaque sommet.

3) Déduire le nombre d’arrêtes de ce graphe.

4) Déterminer la suite graphique associée à ce graphe.

5) Est-t-il possible de partir d’un sommet et d’y revenir en empruntant chaque arrête une
fois et une seule ?

6) Est-t-il possible de partir d’un sommet, de franchir chaque arrête une fois et une seule
et de terminer en un autre sommet ?

7) Le graphe 𝐺 ci-dessus est-il Hamiltonien ? Expliquez.

8) Proposer un encadrement du nombre chromatique du graphe 𝐺 ci-dessus.

9) Colorer le graphe 𝐺.

1
Exercice 2

Sept élèves, désignés par A, B, C, D, E, F et G se sont rendus à la bibliothèque le même jour.


Le tableau suivant précise « qui a rencontré qui » (la bibliothèque étant petite, deux élèves
présents au même moment se rencontrent nécessairement…).

De combien de places assises doit disposer la bibliothèque pour que chacun ait pu travailler
correctement au cours de cette journée ?

Exercice 3

Soit la matrice A suivante :

0 3 ∞ 5 ∞ ∞
3 0 5 2 4 ∞
∞ 5 0 ∞ 4 3
𝐴=
5 2 ∞ 0 4 4
∞ 4 4 4 0 2
(∞ ∞ 3 4 2 0)

1) Tracer le graphe associé à la matrice 𝐴.


2) Trouver l’arbre couvrant minimum pour ce graphe à l’aide de l’algorithme de Prime.

Exercice 4

Trouver l’arbre couvrant minimum pour ce graphe à l’aide de l’algorithme de Prime puis
l’algorithme de Kruskal.

2
Exercice 5

Décomposez le graphe G ci-dessous en niveaux (sans retracer le graphe) puis appliquez


l’algorithme de Bellman pour obtenir les plus courts chemins du sommet a vers tous les autres
sommets, si le graphe ne contient pas un circuit absorbant.

Exercice 6

Appliquez l’algorithme de Bellman-Ford pour obtenir les plus courts chemins du sommet a
vers tous les autres sommets du graphe G ci-dessous.

Vous aimerez peut-être aussi