Algorithmus zum Beschneiden von Knoten im Netzwerk, erreichen maximale Anzahl von Isolaten (Python networkx)

Question

Ich habe Netzwerke (groß & klein), die ich beschneiden muss, bis nur noch Isolate übrig sind. Ich möchte die Anzahl der Isolate maximieren. Gibt es einen Algorithmus, um dies zu tun? auch wenn es komplexer ist? (Zum Beispiel auf dem Boden kann es ebenso verbundene Knoten wird)

dieses einfache Beispiel betrachten:

import networkx as nx 
G = nx.DiGraph() 
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8), 
(1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ]) 

Hier ist die optimale Lösung löscht Knoten 1,3,4,11 und 12

Answer 1

Das klingt wie Sie die Maximum Independent Set (die NP-hard für allgemeine Graphen) berechnet werden soll. (Wikipedia erwähnt auch den Namen Vertex Packing).

Netzwerkx hat eine approximation algorithm.

Vielleicht ist eine Annäherung nicht genug für Sie (und ich denke, dass es keine vorgebaute Alternative gibt).

Laut dem obigen Wikipedia-Link gibt es einen genauen Algorithmus in igraph.

Denken Sie auch daran, dass dieser Approximationsalgorithmus für allgemeine Graphen ist, so dass es sehr wahrscheinlich sein könnte, dass es bessere Ansätze für Bäume gibt.

Edit: (Ohne Prüfung) This SO-answer presents an algorithm for trees (und die Frage ist ein mögliches Duplikat).