小規模なグラフの中で最長の道順

Question

これは私のクラスから得た問題です（私は宿題がないことを保証します）。私は今までそれについて熟考しています。最大25のノードと25のエッジを持つグラフが表示されます。さらに、各ノードの次数は3以下になります。このグラフでは、最長のパスを検索します。しかし、1つのグラフだけでなく、15,000のグラフを受け取るだけでなく、1秒間に最長のパスをすべて見つける必要があります。誰も私にこの問題の解決策（またはより良い、ただのヒント）をくれてもらえますか？どうもありがとうございました！

情報：
- ノードは再訪できますが、唯一の制約はエッジです。
- グラフはエッジによって与えられます。最初の行にはノードと辺の数が記述されており、その後の行は辺を表し、各辺は整数のペアを表します。
- エッジの重み付けが解除されています。
- 唯一の答えはパスの長さであり、パス自体ではありません。
- これは重要なことです。グラフが必ずしも接続されているとは限りません。

Answer 1

「ノードを再訪することができる」ことを知った後、これはいくつかの点でトリックの問題であることに気付きました。これらの一見信じられないほどの時間的制約を満たすために、あなたが実際に必要とするのは、このようなパスを構築するためのアルゴリズムではありません（通常、トレイル、頂点を再利用できる場合はBTW）そのコンポーネントのすべてまたはほとんどすべてのエッジが単一のトレールに含まれるかどうかを素早く検出する方法です。

ここに私のヒントがあります：ケーニヒスベルクには7つの橋があることをご存知でしたか？不可解なようですが、私は周りにいくつかの簡単な検索が正しい方向にあなたを指します、とあなたはすぐにすばやくコンポーネントですべてエッジがの一部を形成することができるかどうかを検出するための方法を見つけるだろうと思うかもしれない;-)

同じ道。 （上記の質問に対する答えが「いいえ」のときに含まれるエッジの数を把握するには、何か考えが必要です。）