Existe-t-il un algorithme approprié pour résoudre le problème de la suppression des arêtes ?

Question

Il existe un graphe orienté (pas nécessairement connecté) dans lequel un ou plusieurs nœuds sont considérés comme des sources. Tout nœud accessible depuis l'une des sources est considéré comme "allumé". Supposons maintenant que l'une des arêtes soit supprimée. Le problème consiste à déterminer les nœuds qui étaient précédemment éclairés et qui ne le sont plus.

Une analogie avec le système électrique d'une ville peut être envisagée, je suppose.

Answer 1

Il s'agit d'un problème de "joignabilité dynamique des graphes". Le document suivant devrait être utile :

Un algorithme d'accessibilité entièrement dynamique pour les graphes dirigés avec un temps de mise à jour presque linéaire. Liam Roditty, Uri Zwick. Théorie de l'informatique , 2002.

Cela donne un algorithme avec des mises à jour en temps O(m * sqrt(n)) ( amorti ) et des requêtes en temps O(sqrt(n)) sur un graphe éventuellement cyclique (où m est le nombre d'arêtes et n le nombre de nœuds). Si le graphe est acyclique, il est possible d'améliorer cette méthode en obtenant des mises à jour en O(m) temps ( amorti ) et des requêtes en temps O(n/log n).

Il est toujours possible de faire mieux que cela compte tenu de la structure spécifique de votre problème, ou en échangeant de l'espace contre du temps.

Answer 2

Si, au lieu de simplement "allumé" ou "non allumé", vous conserviez un ensemble de nœuds à partir desquels un nœud est alimenté ou allumé, et considériez un nœud dont l'ensemble est vide comme "non allumé" et un nœud dont l'ensemble est non vide comme "allumé", alors la suppression d'une arête impliquerait simplement de retirer le nœud source de l'ensemble du nœud cible.

EDIT : J'ai oublié ceci : Et si vous enlevez le dernier nœud éclairé de l'ensemble, traversez les arêtes et enlevez le nœud que vous venez de "déséclairer" de leur ensemble (et éventuellement traversez à partir de là aussi, et ainsi de suite)

EDIT2 (reformulation pour tafa) : Tout d'abord, j'ai mal lu la question initiale et je pensais qu'elle indiquait que pour chaque nœud, on savait déjà s'il était allumé ou non, ce qui, après relecture, n'a pas été mentionné.

Toutefois, si pour chaque nœud de votre réseau vous stockez un ensemble contenant les nœuds par lesquels il a été éclairé, vous pouvez facilement parcourir le graphe à partir de l'arête supprimée et corriger toutes les références éclairées/non éclairées. Par exemple, si nous avons des nœuds A, B, C, D comme ceci : (tentative boiteuse d'art ascii)

A -> B >- D
 \-> C >-/

Au nœud A, vous enregistrerez qu'il s'agit d'une source (donc éclairée par elle-même), et dans les nœuds B et C, vous enregistrerez qu'ils ont été éclairés par A, et dans le nœud D, vous enregistrerez qu'il a été éclairé à la fois par A et par C.

Supposons ensuite que nous supprimions l'arête de B à D : en D, nous supprimons B de la liste des sources éclairées, mais il reste éclairé car il est toujours éclairé par A. Supposons ensuite que nous supprimions l'arête de A à C après cela : A est retiré de l'ensemble de C, et donc C n'est plus éclairé. Nous parcourons ensuite les arêtes qui proviennent de C, et nous retirons C de l'ensemble de D, qui n'est plus éclairé non plus. Dans ce cas, nous avons terminé, mais si l'ensemble était plus grand, nous continuerions simplement à partir de D.

Cet algorithme ne visitera jamais que les nœuds directement concernés par la suppression ou l'ajout d'une arête et, à ce titre (hormis le stockage supplémentaire nécessaire à chaque nœud), il devrait être proche de l'optimum.

Answer 3

Est-ce que c'est votre devoir ?

La solution la plus simple consiste à effectuer un DFS ( http://en.wikipedia.org/wiki/Depth-first_search ) ou un BFS ( http://en.wikipedia.org/wiki/Breadth-first_search ) sur le graphe original à partir des nœuds sources. Vous obtiendrez ainsi tous les nœuds éclairés d'origine.

Retirez maintenant le bord en question. Refaire le DFS. Vous pouvez voir les nœuds qui restent allumés.

Produire les nœuds qui apparaissent dans la première série mais pas dans la seconde.

Il s'agit d'un algorithme asymptotiquement optimal, puisque vous effectuez deux DFS (ou BFS) qui prennent O(n + m) temps et espace (où n = nombre de nœuds, m = nombre d'arêtes), ce qui domine la complexité. Il faut au moins o(n + m) temps et espace pour lire l'entrée, donc l'algorithme est optimal.

Maintenant, si vous voulez supprimer plusieurs Ce serait intéressant. Dans ce cas, nous parlerions de structures de données dynamiques. Est-ce que c'est ce que vous vouliez ?

EDIT : Prise en compte des commentaires :

• non connectées n'est pas un problème, puisque les nœuds des composantes connectées inaccessibles ne seront pas atteints au cours de la recherche.
• il existe une méthode intelligente pour effectuer le DFS ou le BFS à partir de tous les nœuds en même temps (je décrirai le BFS). Il suffit de les placer tous au début de la pile/queue.

Pseudo-code pour un BFS qui recherche tous les nœuds accessibles à partir de n'importe quel nœud de départ :

Queue q = \[all starting nodes\]
while (q not empty)
{
   x = q.pop()
   forall (y neighbour of x) {
      if (y was not visited) {
         visited\[y\] = true
         q.push(y)
      }
   }
}

Remplacez la file d'attente par une pile et vous obtenez une sorte de DFS.

Answer 4

Quelle est la taille et le degré d'interconnexion des graphiques ? Vous pourriez stocker tous les chemins allant des nœuds sources à tous les autres nœuds et rechercher les nœuds pour lesquels tous les chemins menant à ce nœud contiennent l'une des arêtes de suppression.

EDIT : Extension de cette description

Effectuer un DFS à partir de chaque nœud source. Garder une trace de tous les chemins générés vers chaque nœud (sous forme d'arêtes, et non de sommets, de sorte que nous n'avons besoin de connaître que les arêtes concernées, et non leur ordre, ce qui nous permet d'utiliser une carte bitmap). Comptabiliser, pour chaque nœud, le nombre de chemins entre la source et le nœud.

Itérer maintenant sur les chemins. Supprimez tout chemin qui contient le(s) bord(s) supprimé(s) et décrémentez le compteur de ce nœud. Si le compteur d'un nœud est décrémenté à zéro, c'est qu'il était allumé et qu'il ne l'est plus.

Answer 5

Je conserverais les informations sur les nœuds sources connectés sur les arêtes lors de la construction du graphe (par exemple, si l'arête est connectée aux sources S1 et S2, sa liste de sources contient S1 et S2) et je créerais les nœuds avec les informations sur les arêtes d'entrée et les arêtes de sortie. Lorsqu'une arête est supprimée, mettre à jour les arêtes de sortie du nœud cible de cette arête en tenant compte des arêtes d'entrée du nœud. Traverser tous les nœuds cibles des arêtes mises à jour en utilisant DFS ou BFS. (Dans le cas d'un graphe à cycle, envisager le marquage). Lors de la mise à jour du graphe, il est également possible de trouver des nœuds sans aucune arête ayant une connexion source (nœuds éclairés->non éclairés). Cependant, ce n'est pas une bonne solution si vous souhaitez supprimer plusieurs arêtes en même temps, car cela peut vous obliger à parcourir les mêmes arêtes encore et encore.