Diese Frage ergibt sich aus purer Neugier (sie tauchte auf , als ich darüber nachdachte, eine Saite zu mischen , aber ich bin mir nicht sicher, ob sie tatsächlich verwandt ist), also hoffe ich, dass sie angemessen ist.
Es gibt verschiedene Grafikprodukte, und ich interessiere mich für eines davon hier. Wie komplex ist es zu bestimmen, ob ein Graph zu einem nicht trivialen Produkt isomorph ist? (Für das kartesische Produkt ist wobei der Graph mit einem Eckpunkt ist.)
Ich habe mir die Seiten "Factor Graph" und "Graph Factorization" auf Wikipedia angesehen, aber keine davon scheint in Beziehung zu stehen. Ist dieses Problem unter einem anderen Namen bekannt?
In der Polynomzeit können mehrere Graphprodukte erkannt werden. Wie üblich ist das kartesische Produkt das einfachste, und der kartesische Fall ist auch die Grundlage für die Algorithmen für mehrere andere Produkte. Das Erkennen des lexikografischen Produkts (der Zusammensetzung) entspricht dem Graphisomorphismus.
Ausführlicher:
Sei die Klasse der endlichen einfachen Graphen und Γ 0 die Klasse der endlichen einfachen Graphen, die Selbstschleifen haben können. (Offensichtlich Γ ⊂ Γ 0. )Γ Γ0 & Ggr; ⊂ & Ggr;0
Die Entscheidung, ob ein verbundener Eingabegraph Faktoren in Γ 0 hat, kann in Polynomzeit für die kartesischen und starken Produkte und auch für das direkte Produkt, wenn G nicht bipartit ist, getroffen werden. Die Entscheidung, ob G Faktoren in Γ hat, ist für das kartesische Produkt in Polynomzeit, für das lexikografische Produkt jedoch wahrscheinlich nicht in Polynomzeit. Ich weiß nicht, wie es ist, zu entscheiden, ob G Γ für die direkten und starken Produkte berücksichtigt .G Γ0 G G Γ G Γ
Relevante Ergebnisse von Imrich und Klavžar:
Für das Lexikografieprodukt:
Die Entscheidung, ob ein Graph in Bezug auf das lexikografische Produkt eine Primzahl ist, ist in Bezug auf Turing-Reduktionen gleichbedeutend mit GRAPH ISOMORPHISM.
Der Fall des direkten und starken Produkts mit Faktoren ohne Selbstschleifen scheint in den Referenzen, die ich mir angesehen habe, nicht vorhanden zu sein. Ich würde mich über Hinweise auf Artikel freuen, die diesen Fall diskutieren, oder einen Hinweis darauf, warum er uninteressant ist.
quelle
Es gibt einen linearen Zeitalgorithmus zur Bestimmung der Primfaktoren verbundener Graphen in Bezug auf das kartesische Produkt. Siehe das Papier von Imrich und Peterin.
quelle