Affectation des algo

# Affectation des algo ###### tags: `organisation` ## Algorithmes - Suppression/Duplication/Matrice - Conversion adjacence -> incidence - calcul degrés entrant/sortant - Liste de voisins - Plus court chemin - Arborescence de poid minimum - Anti arborescence - Coloration - Stables/cliques - PERT - Gestion des flots - Problème du voyageur de commerce - Chaines eulériennes - Chaine hamiltonienne ## Membre du groupe ### Guillaume - Arborescence de poids minimum Entrée : Graphe G Pour chaque Sommet Prendre le plus petit poids d'arc entrant et le soustraire à chaque poids d'arc entrant Fin pour Créer un nouveau Graphe contenant tous les sommets et les arcs de poids 0 (si plusieurs arcs de poids 0 pour un sommet choisir arbitrairement) Sortie : une Arborescence (Graphe) - Anti arborescence Inversion du sens des arcs + application de l'algo d'arborescence. ### Camille - PERT ``` Algorithme: PERT Entrée: nom et durée des tâches, contraintes d'antériorité Sortie: graphe avec date au plus tôt et au plus tard, tâche et chemin critique Pour tous sommet s Pout tout sommet t Si s est un antécédent de t, ajouter t aux successeurs de s. Fin Pour Fin Pour Créer un sommet "départ" et lui affecter la valeur 0 comme date au plus tôt. Pour toute tâche t n'ayant aucune contrainte d'antériorité Créer le sommet t et un arc a allant de départ vers t. Affecter à a la durée de t. La date au plus tôt de t est égale à la durée de t. Fin Pour Tant qu'il existe une tâche non traitée Pour toute tâche t ayant une unique contrainte d'antériorité sur une tâche x déjà traitée Créer le sommet t et un arc a allant du sommet x vers s. Affecter à a la durée de t. La date au plus tôt de t est égale à la date au plus tôt de x plus la durée de t. Fin Pour Pour tout tâche t ayant plus d'une contraînte d'antériorité sur des tâches x1, x2, ..., xn toutes déjà traitées Si la postériorité du xi ayant la valeur au plus tôt la plus élevée est égal à 1, alors Créer le sommet t et un arc allant du sommet xi ayant la date au plus tôt la plus élevée au nouveau sommet. Créer un arc fictif entre chaque sommet antérieur et le sommet xi. Affecter à a la durée de t. La date au plus tôt de t est égale à la date au plus tôt de x plus la durée de t. Sinon Créer un noueau sommet x1 + x2 ... + xn = SS Créer un arc fictif entre chaque sommet antérieur et le sommet SS. Affecter au nouveau sommet SS la valeur de la date au plus tôt du sommet xi le plus grand. Créer un nouveau sommet t et un arc a allant du sommet SS au sommet t. Affecter à a la durée de t. La date au plus tôt de t est égale à la date au plus tôt de SS plus la durée de t. Fin Pour Fin Tant que Créer un sommet "arrivée", créer un arc fictif entre tous les sommets n'ayant aucun successeurs et ce sommet. Affecter à arrivée la valeur de la date au plus tôt la plus élevée, comme date au plus tôt et au plus tard. Pour chaque sommet s la date au plus tard de s est égale à la date au plus tard la moins élevée de ses successeurs moin s la valeur de l'arc les rejoignant. Fin Pour ``` ### Hugo - Gestion des flots ### Salsa - Liste de voisins ( compléxité au dans le pire des cas O(Nb de sommets - 1)) Entrées: Sommet S, Graphe G Sorties: Liste de voisin du Sommet S Variable: Liste On initialise une liste L a NULL. Pour toutes les colonnes de la ligne de sommet S de la matrice d'adjcence : Si il existe un arc entre le sommet S et un sommet de la matrice: On ajoute à la liste L, le nom du sommet de la colonne. FinSi FinPour Return Liste L ### Sébastien - Calcul degrés entrant/sortant Entrées: Sommet S, Graphe G Sorties: Degrés entrant, Degrés sortant, Nombre de voisins Variable: Successeur, Predecesseur, Nombre de voisins On initialise le successeur et le predeceseur a 0, ainsi que le nombre de voisin a 0. Pour toutes les ligne et les colonnes de la matrice d'adjcence jusqu'a la fin. Si il existe un arc entre le sommet S et un sommet de la matrice: On augmente le nombre de voisin pour le sommet ainsi que le nombre de successeurs. Fin Si Si il existe un arc entre un sommet de la matrice et le sommet S On augmente le nombre de voisin pour le sommet ainsi que le nombre de predecesseurs. Fin Si Fin Pour - Conversion adjacence -> incidence Entrées: Matrice d'ajacence MA Sortie: Matrice d'incidence MI de taille n*m avec m le nombre d'arc dans le graphe et n le nombre de sommet Pour toutes les lignes de MA Pour toutes les colonnes de MA Si il existe un arc entre le sommet S et un sommet voisin T On ajoute un arc dans la matrice d'incidence Alors on met a 1 entre S et T 2 Et -1 entre T et S Fin Si Fin Pour Fin Pour ### Alexandre - Plus court chemin Floyd-Warshall: Entrée: Matrice d'adjacence A correpondante au graphe, Matrice pere MP Sortie: Matrice avec les distances et la matrice pere MP remplie ``` On copie la matrice MA dans la matrice MA' pour tout les sommets K de la matrice pour toute les lignes S de la matrice pour toute les colonnes T de la matrice On compare les chemins direct (entre S et T) et les chemins utilisant k comme intermediaire (S-K et K-T). Si le chemin intermediaire est plus court que le chemin direct on le remplace dans la matrice MA' et on K devient le sommet pere de T dans la matrice MP Fin pour Fin pour Fin pour ``` Ford-Bellman: Entrée: Le graphe G sans cycle absorbant, un sommet choisis, les poids des arcs. Sortie: Tableau des distance(TD) entre S et tout les autres sommets T. Tableau des chemins(TC) entre S et tout les autre sommet T. ``` Pour tout les sommets T On met la case du TD a l'infini Fin pour On met la case S du TD a 0 On repete un nombre de fois egal au nombre de sommet Pour tout les arcs (T, U) de G La distance dans le TD a la case U est egal au minimum entre la valeur deja presente dans cette case et la valeur dans la case T + le poids de l'arc (T, U). Fin pour Si il n'y a eu aucun changement de valeur lors du dernier passage on arrete l'algorithme. Fin repetition ``` ### Théo - Coloration ``` Algorithme : DSATUR Entree : Liste L des sommets du graphe G Sortie : Liste des sommets et leur couleur associée --------------------------------------------------------------------- L = Ordonner L par ordre décroissant de degrés S = Sommet de degré maximum dans L Colorer S avec la couleur 1 Tant que tous les sommets de L ne sont pas colorés : S_0 = Sommet avec le DSAT le plus important dans L (Si égalité prendre le sommet de degrés maximum) Colorer S_0 avec la plus petite couleur possible (absente de son voisinage) Fin Tant que Retouner la liste des sommets et de leur couleur associée ``` Fonction de calcul de DSAT : ``` DSAT(S)= nombre de couleurs différentes dans les sommets adjacents à S ``` - Stables/cliques - Stables : On utilise DSATUR - Clique : On inverse le graphe et on applique DSATUR ``` Algorithme : Inversion de graphe Entree : Matrice M d'ajacence Sortie : Matrice W d'adjacence du graphe inversé --------------------------------------------------------------------- Parcourir la matrice M: Remplacer 1 par 0 Remplacer 0 par 1 sauf sur la diagonale Renvoyer W matrice inverse de M ``` ### Amandine - Chaine eulérienne ``` Algorithme : EULERIEN Entrée : Sommet S, Graphe G Sortie : Liste de sommets formant une chaine Eulérienne (vide ou non) --------------------------------------------------------------------- Si S est isolé Retourne le circuit sous forme de liste. Fin Si Sinon Sauvegarde du circuit qui contient le sommet S. Sauvegarde du graphe G' qui prends la valeur de G sans le circuit qui contient le sommet S. Parcours des sommets du circuit qui contient le sommet S : Concaténation du circuit qui contient le sommet S + ALGORITHME EULERIEN sur G' et le sommet parcouru. Fin Sinon ``` - Chaine hamiltonienne O(n2) ? ``` Algorithme : HAMILTONIEN Entrée : Graphe G Sortie : Liste de sommets formant une chaine Hamiltonienne (vide ou non) Variable : Sommet S ------------------------------------------------------------------------ Parcours de la matrice du graphe horizontalement et verticalement : Si tout les sommets sont marqué Retourne la liste de sommets. Fin Si Si S est isolé et tout les sommets ne sont pas marqués Retourne une liste vide. Fin Si Si S non marqué Marque le sommet. Fin Si Si le sommet S+1 parcouru horizontalement est successeur du sommet S sur lequel on se trouve verticalement et non marqué Marque le sommet successeur S+1. Concaténation de la liste de sommet avec ce même sommet S+1. Continue le parcours de la matrice depuis ce sommet S+1. Fin Si Fin Boucle ``` ### Vincent - Problème du voyageur de commerce. ``` Algorithme : LITTLE Entréee : Graphe G, Arbre A Sortie : Arbre binaire avec le coût total pour chaque feuille de l'arbre Variable : entier T ------------------------------------------------------------------------ Si la matrice du graphe est nulle Renvoie A Sinon Parcours de la matrice du graphe horizontalement et verticalement : Si il n'y a pas d'arc de poids nul à partir du sommet Cherche l'arc de poids le plus faible et on soustrait son poids à tous les arcs partant de ce sommet Ajoute son poids dans T Fin Si Racine de A prend la valeur T Pour chaque arc de poids nul dans notre matrice Calcul du regret associé (Ajout du poids le plus faible de la ligne et de la colonne autre que l'arc sélectionné) Fin Pour On sélectionne l'arc avec le plus grand regret Création de deux feuilles Fils gauche prend la valeur du parent plus le regret (cas trajet exclu) Fils droit prend en récursif l'algorithme de Little avec l'arbre A et la matrice du graphe sans l'arc choisi (cas trajet inclus) Fin Si ``` ### Truc a ne pas oublier dans le cdc: - Manque certaines complexité - Faire la conclusion - voir les info sur les modules (a appronfondir potentiellement) -