graph

Fragen
Graph bezieht sich auf eine Grafik (z. B. ein Diagramm oder ein Diagramm), die die Beziehung zwischen zwei oder mehr Variablen anzeigt. Verwenden Sie für die diskrete mathematische Struktur, die aus Vertices und Kanten besteht, das Graph-Theorie-Tag.
2
Antworten

Lösen einer Erweiterung des kürzesten Hamilton-Pfads

Ich habe über eine Erweiterung des Shortest Hamiltonian Path (SHP) -Problems nachgedacht und konnte keine Lösung finden. Ich weiß, dass es NP-komplett ist, aber ich dachte, ich würde hier nach Ideen fragen, da ich das Problem nicht einfach nur b...
06.11.2012, 08:29
2
Antworten

Was ist der einfachste Weg, ein Control Flow-Graph für eine Methode in Python zu generieren?

Ich schreibe ein Programm, das versucht, zwei Methoden zu vergleichen. Ich möchte Control Flow Graphs (CFG) für alle übereinstimmenden Methoden generieren und entweder eine topologische Sortierung zum Vergleich der beiden Graphen verwenden.    ...
01.06.2011, 16:59
1
Antwort

Algorithmus zum Erzeugen eines Zufallsnetzwerks

Was ist der beste Algorithmus zum Generieren eines zufälligen einfachen (nicht parallelen Kanten oder selbst-Schleifen) ungerichteten Graphen mit einer gegebenen Anzahl von Knoten, wobei jeder Knoten eine Anzahl von Kanten hat, die nicht kleiner...
24.06.2015, 19:00
3
Antworten

Wie erkennt man, ob das gegebene Diagramm einen Zyklus hat, der alle Knoten enthält? Hat der vorgeschlagene Algorithmus irgendwelche Fehler?

Ich habe einen verbundenen, nicht gerichteten Graphen mit N Knoten und 2N-3 Kanten. Sie können den Graphen so betrachten, wie er auf einem vorhandenen Ausgangsgraphen aufgebaut ist, der 3 Knoten und 3 Kanten hat. Jeder Knoten wird dem Diagramm h...
06.04.2013, 19:44
8
Antworten

Nicht-rekursive Tiefensuche (DFS) unter Verwendung eines Stapels

Ok, das ist mein erster Beitrag auf Stack Overflow. Ich lese seit einiger Zeit und bewundere die Seite wirklich. Ich hoffe, dass dies akzeptabel ist. Also habe ich die ganze Zeit über Intro to Algorithms (Cormen. MIT Press) gelesen und bin dabei...
26.04.2012, 22:29
3
Antworten

Maximaler Fluss in dynamischen Diagrammen

Ich suche nach einem schnellen Algorithmus, um den maximalen Fluss in dynamischen Graphen zu berechnen (Hinzufügen / Löschen eines Knotens mit zugehörigen Kanten zum Graphen). d. h. wir haben einen maximalen Fluss in G, jetzt wird ein neuer Knot...
26.01.2012, 10:09
2
Antworten

Minimale Schnittmengen zwischen begrenzten Teilgraphen finden

Wenn eine Spielkarte in Untergraphen partitioniert wird, wie kann man Kanten zwischen Untergraphen minimieren? Ich habe ein Problem. Ich versuche, A * durch ein Grid-basiertes Spiel wie Pacman oder Sokoban zu durchsuchen, aber ich muss "Geheg...
06.04.2010, 10:04
0
Antworten

Verwenden Sie das Argument 'pos' in Rgraphviz, um die Knotenposition zu fixieren

Basierend auf dieser Frage Automatische Krümmung eines arc, wenn es sich mit einem anderen überlappt , versuche ich das Attribut pos in einem RGraphviz plot zu setzen. Kann jemand zeigen, wie das pos -Attribut korrekt verwendet wird...
21.08.2017, 16:27
1
Antwort

Gibt es eine Datenstruktur für DAGs, die effiziente Bearbeitungen unterstützt?

Ich suche nach einer Datenstruktur, die alle DAG speichert, aber effizient (dh sublinear in der Anzahl der Kanten / Scheitelpunkte) erkennen kann, ob das Hinzufügen einer Kante einen Zyklus erzeugen würde (und somit einen Bruch verhindern würde)...
25.10.2011, 17:46
3
Antworten

Gibt Tarjans SCC-Algorithmus eine topologische Sortierung des SCC?

Ich habe SCC und Algorithmen über sie studiert, und ich habe gesehen, dass Leute fast immer erwähnen, dass der Algorithmus von Kosaraju den SCC findet und sie auch in einer (umgekehrten) topologischen Reihenfolge sortiert. Meine Frage ist: Fi...
23.09.2015, 22:25