GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
GRAPHES - EXERCICES CORRIGES. Compilation réalisée à partir d'exercices de BAC TES. Exercice n°1. Un groupe d'amis organise une randonnée dans les Alpes.
TD no 1
Exercice 2 Dans un graphe non orienté il y a toujours deux sommets de même degré. Exercice 3 Le complémentaire d'un graphe non Corrigé du TD no 1.
TD Graphe 1 corrigé : Vocabulaire Option informatique
TD Graphe 1 corrigé : Vocabulaire. Option informatique. I Exemples de graphes. Le graphe de Kneser KGnk a pour sommets les sous-ensembles de taille k de {0
IUP Miage FI2-FE2 – Théorie des graphes le 27 septembre 2004 TD
TD no1 et sa correction. 1. Un graphe G d'ordre 7 corrigé : on sait que la somme des degrés des sommets d'un graphe est égal au double de son nombre.
TD dalgorithmique avancée Corrigé du TD : Graphe et Tri topologique
Corrigé du TD : Graphe et Tri topologique. Jean-Michel Dischler. Un tri topologique d'un graphe orienté acyclique G = (S A) est un ordre linéaire des
Séries TD Corrigés
Théorie de graphes. 2ème année LMD. Université de Batna 2. Département d'Informatique. Séries TD Corrigés. Exercice 1 : Trois enseignants P1 P2
Algorithmes et structures de données avancées : TD 7(corrigé)
Algorithmes et structures de données avancées : TD 7(corrigé). Graphes - Matrice d'Adjacence Exercice 7.1 Matrice d'adjacence pour un graphe non-orienté.
Correction TD 10
1) Dessiner le graphe potentiel-tâches et calculer les dates au plus tôt les dates au plus tard et le chemin critique. 2) Dessiner un graphe PERT simplifié
Théorie des Graphes - TD n°1
Théorie des Graphes – TD 1 Un graphe d'intervalles est composé des sommets 1…n tel que il y a une arête entre un sommet i et j ... Corrigé Exercice 1.
TD 2 graphe corrigé : représentations et parcours Option informatique
TD 2 graphe corrigé : représentations et parcours. Option informatique. I Représentations des graphes. 1. Écrire des fonctions mat_of_list : int list array
[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir d'exercices de BAC TES Exercice n°1 Un groupe d'amis organise une randonnée dans les Alpes
[PDF] Introduction à la théorie des graphes Solutions des exercices
Exercice 4 Comme Holmes dessinons un graphe avec les sommets A B C E F G et H Dans ce graphe on relie deux sommets i et j si les suspectes i et j
TD Exercices corrigés théorie de graphe - ExoCo-LMD
22 jui 2020 · TD Exercices corrigés théorie de graphe * SÉRIES_TD_TG pdf 1 4 Mo téléchargé 9349 fois * SOL_TD_TG pdf 1 55 Mo téléchargé 3415 fois
[PDF] TD Graphe 1 corrigé : Vocabulaire Option informatique
TD Graphe 1 corrigé : Vocabulaire Option informatique I Exemples de graphes Le graphe de Kneser KGnk a pour sommets les sous-ensembles de taille k de {0
[PDF] TD 2 graphe corrigé : représentations et parcours Option informatique
TD 2 graphe corrigé : représentations et parcours Option informatique I Représentations des graphes 1 Écrire des fonctions mat_of_list : int list array
Theorie des Graphes - coursexercicesexamens - Univdocs
Telecharger des cours et examens corrigesexercices corrigestravaux dirigés pdf resumedes polycopie documents de module Theorie des Graphes
[PDF] Éléments de théorie des graphes
Exercice 1 (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être diviseur
[PDF] Livret dexercices Théorie des Graphes et Recherche Opérationnelle
29 août 2016 · Soit le graphe muni d'une valuation des arcs Sachant qu'il existe un chemin de A à J donnez la séquence de nœuds formant le chemin entre A et
[PDF] Exercices dexamen sur les graphes (niveau L3) avec corrigés
Exercices d'examen sur les graphes (niveau L3) avec corrigés 1) Exploration d'un graphe Pour ce graphe non orienté à 14 sommets les voisins de chaque
TD d'algorithmique avancee
Corrige du TD : Graphe et Tri topologique
Jean-Michel Dischler
Untri topologiqued'un graphe oriente acycliqueG= (S;A) est un ordre lineaire des sommets deGtel que siGcontient l'arc (u;v),uappara^t avantv. Le tri topologique d'un graphe peut ^etre vucomme un alignement de ses sommets le long d'une ligne horizontale tel que tous les arcs soient orientes
de gauche a droite. Attention: le tri topologique d'un graphe oriente acyclique n'est pas forcement unique. 1. Prop osezun tri top ologiquedu graphe de la gure 1. 5 6231
4
78994 5 1 2 3 6 8 7
7 9 1 4 2 5 8 3 6 7 4 5 9 1 2 8 3 6 Figure1 { Exemple de graphe oriente acyclique avec trois de ses tris topologiques possibles. 2. Mo diezl'algorithme de parcours en profond eurvu en cours p ourqu'il calcule p ourc haquenud usa date de n de traitementn[u] (la date a laquelle lui et ses ls ont ete traites). PP(G) pourchaque sommetudeGfairecouleur[u] Blanc pourchaque sommetudeGfaire sicouleur[u] =BlancalorsVisiter-PP(G,u,couleur)Visiter-PP(G,s,couleur)
couleur[s] Gris pourchaque voisinvdesfaire sicouleur[v] =BlancalorsVisiter-PP(G,v,couleur) couleur[s] Noir temps temps+ 1 n[s] temps 3. Quel lien p ouvez-vousfaire en treles dates de n de traitemen tet un tri top ologique? Si le grapheGcontient l'arc(u;v), le traitement deuniraapresle traitement dev, et on aura donc n[u]>n[v]. Trier les sommets par date de n de traitements decroissantes nous fournit donc un tri topologique du graphe. La gure 2 presente le graphe de la gure 1 ou les nuds ont ete annotes avec des ns de date de traitement lors d'un parcours en profondeur (<< racines >> successives : nuds 1, 9, 4 et 7). On retrouve alors le troisieme des tris topologiques de la gure 1. 1 5 6231
4 789
5 4 2 78
1 936
Figure2 { Graphe annote par les dates de n de traitement d'un parcours en profondeur. 4. Prop osezun algorithme de tri top ologique.Quel est sa complexit e? On commence par parcourir le graphe en profondeur avec l'algorithme de la question 2, puis on trie les sommets par date de n decroissante. La complexite de l'ensemble est donc celle du parcours O(jSj+jAj)plus celle du triO(jSjlog(jSj)), soitO(jSjlog(jSj) +jAj). 5. Am eliorezv otrealgorithme p ourqu'il s oitde complexit elin eaire. PP(G)
SoitPune pile initialement vide
pourchaque sommetudeGfairecouleur[u] Blanc pourchaque sommetudeGfaire sicouleur[u] =BlancalorsVisiter-PP(G,u,couleur,P) tant quenonPile-Vide(P)faire u Depiler(P)Afficher(u)
Visiter-PP(G,s,couleur,P)
couleur[s] Gris pourchaque voisinvdesfaire sicouleur[v] =BlancalorsVisiter-PP(G,v,couleur,P) couleur[s] NoirEmpiler(P,s)
On stocke dans une pile les elements dans l'ordre dans lequel leur traitement se termine. On retirera les elements de la pile dans l'ordre inverse de celui dans lequel ils ont ete inseres (une pile fonctionne toujours sur le mode << premier entre, dernier sorti >>). Utiliser une pile plut^ot que simplement les dates de n de traitement nous evite d'avoir a trier ces dates (ce qui nous co^uteraitO(jSjlog(jSj)). L'algorithme complet a ici un co^ut deO(jSj+jAj)(le parcours est de co^utO(jSj+jAj)et la pile contientjSjelements, donc les depiler est de co^utO(jSj)). 6. Prop osezun autre algorithme de tri top ologique,bas ecette fois- cisur le fait qu'un sommet de degre entrant nul peut ^etre place en t^ete d'un tri topologique. Quelle est la complexite de cet algorithme? La gure 3 presente le second algorithme de tri topologique. Un sommet qui est place dans la le, est un sommet dont tous les predecesseurs ont deja ete ordonnes : on peut donc le placer a son tour dans l'ordre sans risquer de violer un arc. La complexite de l'ensemble est une fois de plus enO(jSj+jAj). 2Tri-Topologique(G= (S;A))
SoitFune le initialement vide
pourchaque sommetudeGfaire degre(u) degre entrant deu sidegre(u) = 0alorsInsertion(F,u) tant quenonFile-Vide(F)faire u Suppression(F)Afficher(u)
pourchaque voisinvdeufaire degre(v) degre(v)1 sidegre(v) = 0alorsInsertion(F,v)Figure3 { Deuxieme algorithme de tri topologique.
3quotesdbs_dbs45.pdfusesText_45[PDF] olt 2 pdf
[PDF] code des obligations travail suisse pdf
[PDF] indu ppa plus de 25 ans
[PDF] olt 1 pdf
[PDF] delai prescription indu caf
[PDF] loi sur le travail suisse licenciement
[PDF] loi sur le travail suisse pause
[PDF] indu caf prime d'activité
[PDF] loi sur le travail suisse pdf
[PDF] indu rsa prescription
[PDF] indu prime d'activité + 25 ans
[PDF] freinage par induction exercice corrigé
[PDF] induction électromagnétique exercices corrigés pdf
[PDF] cadre mobile dans un champ magnétique
