Graphes, recherche arborescente et complexité - publié le 19/09/2024
Télécharger
Lire un extrait
Thèmes abordés
Master Informatique, réduction polynomiale, Python, programmation, code informatique, fonction informatique, modéliser un problème, coloration d'un graphe, théorie des graphes, bibliothèque networkX, recherche arborescente, complexité d'un algorithme
Lecture
Résumé
Sommaire
Extraits
sur 12
Résumé du document
Ce document répond à quelques questions problématisées en informatique, tout en implantant les fonctions demandées en langage Python.
Sommaire
Un problème de logique
Un problème de graphe
Une réduction polynomiale du problème de graphe au problème de logique
Un problème de logique
Un problème de graphe
Une réduction polynomiale du problème de graphe au problème de logique
Accédez gratuitement au plan de ce document en vous connectant.
Extraits
[...] Il est important de noter ici qu'il est possible d'utiliser trois couleurs mais l'idée est d'illustrer que deux couleurs suffisent et ce quel que soit le nombre de sommets , avec un entier positif. Question 5 : a. def est_ce_trois_coloration(graphe, couleur): for sommet, voisins in graphe.items(): for voisin in voisins: if couleur[sommet] couleur[voisin]: return False return True b. La complexité de la fonction est de l'ordre de avec le nombre des sommets et le nombre des arrêtes. c. [...]
[...] c'est à dire verifier que les sommets adjaçants du graph n'ont pas la même couleur les paramatéres d'entrées sont le réseau de graph ainsi qu'un dictionnaire de couleurs contenant les sommets comme des clés et les couleurs comme des valeurs La valaeur de retour de cette fonction est booléeanne , elle retourne True si le coloriage est valide et False sinon # Il faut parcourir tout les arrêtes du graphe : une boucle for a été utilisée for v in graph.edges(): # Nous émettons l'hypothése que le coloriage est valide et celui ci sera invalide si # la couleur de deux sommets adjaçants est la même if coloring[u] coloring[v]: return False return True # Si aucune arête n'a des sommets adjacents de même couleur, le coloriage est valide # Développement de la fonction brute force pour résoudre le probléme de tricoloriage 3 COL def bruteForce3col(graph): Essaie de résoudre le problème de 3-coloration par force brute. Teste toutes les combinaisons possibles de coloriages et retourne la première qui est valide. [...]
[...] 2. Les sommets adjacents n'ont pas la même couleur : condition nécessaire mais pas suffisante 3. Il faut au plus quatre couleurs. [...]
[...] Le teste de la fonction sur un graphe carré permet de valider son fonctionnement. Question 6 : - 3-COL n'est pas dans . Aucun algorithme polynomial connu. - 3-COL est dans NP car la solution peut être vérifiée par un algorithme polynomial mais aucun algorithme polynomial ne permet de trouver directement la solution. - 3-COL peut être résolu par des algorithmes en temps exponentiel comme celui que nous avons mis en place pour la question 3. [...]
[...] def reduction(graaphe): clauses = na = len(graaphe) variables = compteur = 1 for sommet in graaphe: for couleur in range(1, variables[(sommet, couleur)] = compteur compteur 1 for sommet in graaphe: clauses.append([variables[(sommet, variables[(sommet, variables[(sommet, for sommet in graaphe: clauses.append([-variables[(sommet, -variables[(sommet, clauses.append([-variables[(sommet, -variables[(sommet, clauses.append([-variables[(sommet, -variables[(sommet, for sommet, voisins in graaphe.items(): for voisin in voisins: if sommet [...]
