あなたがそれらをフォローすると、グラフの残りの部分に到達するために残したノードに戻らなければならないという性質を持つエッジを見つける。

Question

私は複数の営業マンと一緒に旅行セールスマンの問題に取り組んでいます。あるポーランド人のセールスマンがそのポケットに入ると、それが大きすぎる仕事をしない限り、そこに別のポートが入ることはありません。 "ポケット"の入り口を見つけてマークしたい（これは問題です）。最初の1つ。

これらはすべてリアルネットワークのあらゆる場所にあります。 のようにこの方法でに入ると、別の方法がないので、同じ方法ですぐに出てくる必要があります。いくつかの内部構造、ループ、ブランチがあるかもしれませんが、あなたが入った場所を除いて都会に戻る方法はありません。

私はサブポケットは気にしません、私はちょうどノードのリストそのうちの1つは都市の大半であり、他のものはすべて、上述のように主要道路ネットワークに接続されたこれらのポケットです。

私はosmnxから提供されているMultiDiGraphに取り組んでいます。

Answer 1

開始点は、グラフを分割するエッジのセットであるcutです。あなたはサイズ1の "最小限のカット"を探しています。

ストリートマップとして接続されているものについては、Karger'sアルゴリズムが必要になると思います。これは、重複して接続されたノードの集合を単一のノードに畳み込むことによって、間接的に最小の切断点を探索し、最終的に比較的わずかな単一エッジ接続が残るまで行う。ここから、切れ目を見つける方が簡単です。