Längster Pfad in kleiner Grafik mit kleinem Grad

Question

Dies ist ein Problem, das ich von meiner Klasse habe (ich versichere Ihnen, es ist keine Hausaufgabe). Ich denke immer noch darüber nach. Sie erhalten eine Grafik mit höchstens 25 Knoten und 25 Kanten. Zusätzlich wird jeder Knoten einen Grad von höchstens 3 haben. Die Aufgabe besteht darin, den längsten Pfad in diesem Graphen zu finden. Sie erhalten jedoch nicht nur 1 Grafik, sondern 15.000 Grafiken, und Sie müssen den längsten Pfad in allen von ihnen in 1 Sekunde finden. Könnte mir bitte jemand eine Lösung (oder noch besser, nur einen Hinweis) zu diesem Problem geben? Vielen Dank!

Info:
- Knoten können erneut besucht werden, die einzigen Einschränkungen sind die Kanten.
- Die Graphen sind durch die Kanten gegeben. So gibt die erste Zeile an, wie viele Knoten und Kanten es gibt, und die Zeilen danach stellen die Kanten dar, jede Kante durch ein Paar Ganzzahlen.
- Die Kanten sind nicht gewichtet.
- Die einzige Antwort ist die Länge des Pfades, nicht der Pfad selbst.
- Dies könnte wichtig sein: Der Graph ist nicht notwendigerweise verbunden.

Answer 1

Nachdem ich sah, dass "Knoten können wieder besucht werden", erkannte ich, dass dies in gewisser Weise eine Trickfrage ist. Um diese scheinbar unglaublichen Zeitbeschränkungen zu erfüllen, brauchen Sie hier eigentlich keinen Algorithmus zur Konstruktion eines solchen Pfades (normalerweise trail, BTW, wenn Vertices wiederverwendet werden können), sondern für jede verbundene Komponente des Graphen. eine Möglichkeit, schnell zu erkennen, ob alle oder fast alle Kanten in dieser Komponente in einer einzelnen Spur enthalten sein können.

Also hier ist mein Tipp: Wussten Sie, dass es in Königsberg sieben Brücken gibt? ;-)

Das mag kryptisch erscheinen, aber ich denke, einige schnelle Suche wird Sie in die richtige Richtung weisen, und Sie werden bald einen Weg finden, um schnell zu erkennen, ob alle Kanten in einer Komponente bilden können gleiche Spur. (Sie müssen mehr darüber nachdenken, wie viele Kanten enthalten sein können, wenn die Antwort auf die obige Frage "Nein" lautet.)