Algorytm wyszukiwania zbędnych krawędzi na wykresie lub drzewie

Question

Czy istnieje ustalony algorytm znajdowania zbędnych krawędzi na wykresie?

Na przykład, chciałbym zauważyć, że A-> D i a-> e są zbędne, a następnie pozbyć się z nich, jak to:

=>

EDIT: Strilanc był na tyle miły, że czytał dla mnie. "Redundantny" był zbyt mocnym słowem, ponieważ w powyższym przykładzie ani a-> b ani a-> c nie jest uważane za zbyteczne, ale a-> d jest.

Answer 1

Chcesz obliczyć najmniejszy wykres, który zachowuje osiągalność wierzchołków.

To się nazywa transitive reduction wykresu. Artykuł Wikipedii powinien zacząć od właściwej drogi.

Answer 2

Podrys wykresu bez "zbędnych krawędzi" nazywany jest "spanning tree" tego wykresu. Dla dowolnego wykresu możliwe są drzewa wieloprzęsłowe.

Tak więc, aby pozbyć się zbędnych krawędzi, wystarczy znaleźć dowolne drzewo opinające wykres. Możesz użyć dowolnego algorytmu depth-first-search lub breadth-first-search i kontynuować wyszukiwanie do momentu odwiedzenia każdego wierzchołka na wykresie.

Answer 3

Sprawdź to: Minimum Spanning Tree

Answer 4

Kilka sposobów, aby zaatakować, ale najpierw będziesz musiał zdefiniować problem nieco bardziej precyzyjnie. Po pierwsze, wykres, który tu masz, jest acykliczny i skierowany: czy to zawsze będzie prawdą?

Następnie należy zdefiniować, co rozumiemy przez "nadmiarowy brzeg". W tym przypadku zaczynasz od wykresu, który ma dwie ścieżki a-> c: jedna do b i jedna do drugiej. Z tego wnioskuję, że przez "zbędny" masz na myśli coś takiego. Niech G = < V e> się wykres z V zestawu wierzchołków i E ⊆ V × V zestaw krawędzi. To trochę wygląda jakbyś definiując wszystkie krawędzie z v _i do v _j krótsza od najdłuższej krawędzi jako „zbędne”. Najłatwiej byłoby użyć pierwszego wyszukiwania w głębi, wyliczyć ścieżki, a gdy znajdzie się nowy, który jest dłuższy, zapisz go jako najlepszego kandydata.

Nie mogę sobie wyobrazić, czego chcesz. Możesz mi powiedzieć?

Answer 5

myślę najprostszy sposób na to, że rzeczywiście wyobrazić, jak to będzie wyglądać w prawdziwej pracy, wyobraź sobie, jeśli masz stawy, jak

(A-> B) (B-> C) (A- > C) wyobrazić, gdy odległość pomiędzy pobliżu wykresach jest równa 1, dlatego

(A-> B) = 1 (B-> C) = 1 (A-> C) = 2.

Możesz więc usunąć połączenie (A-> C).

Innymi słowy, zminimalizuj.

To tylko mój pomysł, jak o tym pomyśleć na początku. W sieci są różne artykuły i źródła, możesz na nie spojrzeć i wejść głębiej.

zasobów, które pomogą Ci:

Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP

Graph Data Structure and Basic Graph Algorithms

Google Books, On finding minimal two connected Subgraphs

Graph Reduction

Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs

Answer 6

miałem podobny problem i skończyło się go rozwiązać w ten sposób:

Moja struktura danych jest wykonana z dependends słownika, z identyfikatorem węzła do listy węzłów, które zależą od niego (tj swoich zwolenników w. DAG). Zauważ, że działa tylko dla DAG - to jest skierowany, acykliczny wykres.

Nie obliczałem dokładnej złożoności, ale połknąłem mój wykres kilku tysięcy w ułamku sekundy.

_transitive_closure_cache = {} 
def transitive_closure(self, node_id): 
    """returns a set of all the nodes (ids) reachable from given node(_id)""" 
    global _transitive_closure_cache 
    if node_id in _transitive_closure_cache: 
     return _transitive_closure_cache[node_id] 
    c = set(d.id for d in dependents[node_id]) 
    for d in dependents[node_id]: 
     c.update(transitive_closure(d.id)) # for the non-pythonists - update is update self to Union result 
    _transitive_closure_cache[node_id] = c 
    return c 

def can_reduce(self, source_id, dest_id): 
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)""" 
    for d in dependents[source_id]: 
     if d.id == dest_id: 
      continue 
     if dest_id in transitive_closure(d.id): 
      return True # the dest node can be reached in a less direct path, then this link is redundant 
    return False 

# Reduce redundant edges: 
for node in nodes:  
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]