Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir 1 linma1691 LINMA Théorie des graphes Devoir Composantes Fortement Connexes Dans ce devoir nous explorons une notion liée à la connexité pour les graphes dirigés les composantes fortement connexes ou strongly connected components aka SCCs Votre obj

LINMA Théorie des graphes Devoir Composantes Fortement Connexes Dans ce devoir nous explorons une notion liée à la connexité pour les graphes dirigés les composantes fortement connexes ou strongly connected components aka SCCs Votre objectif est de résoudre le problème qui suit Pour vous y aider on explique ce que sont les SCCs et référons à un algorithme e ?cace permettant de les calculer Composantes Fortement Connexes SCCs Dans un graphe dirigé une composante fortement connexe est un ensemble de noeuds tel que pour toutes paires de noeud u et v dans l ? ensemble il existe un chemin de u à v et de v à u de plus l ? ensemble de noeuds est maximal pour cette propriété Notez que cette relation entre noeuds u et v est ré exive transitive et symétrique On peut donc à partir de tout graphe déduire une partition de ses noeuds en SCCs Et de là en déduire un nouveau graphe dirigé o? chaque noeud est une composante fortement connexe dans le graphe original Un exemple avec une graphe orienté et sa décomposition en SCCs puis le graphe des SCCs A B C Un algorithme e ?cace parmi d ? autres pour calculer ces SCCs est celui de Kosaraju De nombreuses références librement accessibles décrivent cet algorithme Aussi vous êtes libre d ? utiliser un autre algorithme pour calculer les SCCs ou même de ne pas utiliser le concept de SCC du tout si vous ne le jugez pas nécessaire pour résoudre le problème de la section suivante https fr wikipedia org wiki Composantefortementconnexe CAttention l ? algorithme de Kosaraju est souvent décrit et implémenté via des appels récursifs Malheureusement ceux-ci s ? avèrent ine ?caces Il faudra donc corriger ce défaut dans vos implémentations Rumeurs Contexte Vous voulez disperser dans LLN la rumeur qu ? une tyrolienne va être construite entre la place des sciences et la place de l ? université De plus vous voulez disperser cette rumeur en la donnant de manière directe à un minimum de kots Pour ce faire vous disposez d ? informations sur quels kots partagent les rumeurs avec quels kots Notez que cette relation n ? est pas forcément symétrique Par exemple il se pourrait que si le Kotangente apprend la rumeur alors le Babbelkot et l ? Akapella l ? apprendront aussi mais que l ? Akapella ne partage la rumeur qu ? avec le Babbelkot et pas avec le Kotangente Dans cet exemple à kots une solution optimale est de donner la rumeur au Kotangente qui la partagera avec les deux autres On vous demande d ? écrire une fonction solve qui détermine le nombre minimal de kots avec qui il faut partager directement la rumeur de façon à ce que tous les kots en aient ?nalement vent Input de la fonction solve Une liste d ? adjacence d ? un graphe dirigé décrivant la dispersion des rumeurs La longueur n de la liste d ? adjacence est le nombre de kots