エッジを分割したウォークに分割する

無向グラフ$ G =(V、E)$と$ k $頂点$ S = s_1、 ldots、s_k $、$ T = t_1、
ldots、t_k $の2つのシーケンスを考えてみましょう。 $ k $ walkの集合は$(S、T)$ –
walkパーティションと呼ばれます。

  1. 散歩は$ E $の端にパーティションを形成し、
  2. $ i $ th歩行が$ s_it _ { pi(i)} $ – 歩行となるような、置換$ pi:[k] ~ [k]
    $が存在します。 (A $ st $ -walkは頂点$ s $で始まり頂点$ t $で終わる歩行です)

以下の問題を考える。

$ k $ -walkパーティション

     

入力:グラフ$ G $と$ k $頂点$ S $と$ T $の2つのシーケンス。

     

出力: $ G $に$(S、T)$ウォークパーティションが存在します。

この問題は研究されていますか?私は$ k $が定数のときに興味があります。 $ k = 1 $のときは、$ s_1 $〜$
t_1 $のオイラーの軌跡があるかどうかをチェックするのと同じです。

ベストアンサー

    新しいソースを作成して$ s_1、 ldots、s_k $に接続し、新しいシンクを作成して$ t_1、 ldots、t_k
    $に接続します。

  • すべてのエッジの容量は$ 1 $、コストは$ -1 $です。

  • この問題は、最小コストフローの問題の特殊なケースです。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です