Scribd
Importer
87 vues1 page

TD2 Complexite Sujet

Transféré par

Lassina Dembele
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
87 vues1 page

TD2 Complexite Sujet

Transféré par

Lassina Dembele
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

Modèles et Algorithmes pour les Graphes (MAG)

L3 Informatique/MIAGE 2023–2024

TD2 : Complexité des algorithmes


Rappel : Pour chaque algorithme, on peut mettre en évidence une ou plusieurs opérations
qui sont fondamentales au sens où le temps d’exécution est proportionnel au nombre de ces
opérations. Il est alors possible de comparer les algorithmes selon cette mesure simplifiée.

Exercice 1. Représentation des graphes


On considère les graphes suivants :

1 2 1 2

3 4 5 3 4 5

6 7 8 6 7 8

Figure 1 – Graphe G Figure 2 – Graphe F

1. Représenter le graphe G par sa matrice d’adjacence. La matrice est-elle symétrique ?


2. Écrire un algorithme pour calculer le degré de tous les sommets à partir de la matrice
d’adjacence. Quelle est la complexité de cet algorithme ?
3. Représenter le graphe F par sa matrice d’incidence sommets/arcs.
4. Si le graphe F avait une boucle sur le sommet 4, comment modifieriez-vous sa matrice
d’incidence ?
5. Représenter le graphe F par l’ensemble des prédécesseurs.
6. Quelle est la complexité de calculer le degré extérieur et intérieur pour chaque sommet
à partir de cette représentation ?
7. Écrire un algorithme qui permet de passer de la représentation ensemble de prédé-
cesseurs à la représentation ensemble de successeurs. Quelle est sa complexité ?

Vous aimerez peut-être aussi