Ich gehe davon aus, dass wir 2 beschriftete Graphen G und T haben und der Algorithmus bestimmt, ob G ein Untergraph von T ist und die entsprechenden Eckpunkte im HauptgraphT und dem Untergraph G dieselbe Beschriftung haben sollten
Antworten
Zu viele Anzeigen?
Jeremiah Willcock
Punkte
28941
Dieses Problem wird als "Subgraphen-Isomorphismus" und es ist NP-komplett (und damit wahrscheinlich schwer). Benötigen Sie eine allgemeine Lösung für dieses Problem oder nur für einen bestimmten Graphen? G ? Der zweite Fall ist viel einfacher. Es gibt einige allgemeine Informationen über Algorithmen aquí . Es gibt eine Version eines der Algorithmen (eigentlich für ein allgemeineres Problem) in der Boost Graph Library (siehe Dokumentation aquí ).
phooji
Punkte
9774
Eine allgemeine Antwort auf eine allgemeine Frage: Das Problem, das Sie lösen wollen, ist als "Subgraphen-Isomorphismus" bekannt. Schauen Sie hier für weitere Referenzen: http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem .
