円テーブルの2者座席配置

Question

女性と男性の2つのグループがあるとします。各女性には、興味のある男性がいます。私たちは、二部グラフの中でエッジとしての関心を表します。

ここでは、あなたがテーブルを回った場合など、すべての人をセットアップしようとしています。それぞれの座席は、座席のペアは、カップルが接続で占有されます。例えば、テーブルの周りを時計回りに回すと、座席には次の座席に座っている男性に興味のある女性がいるかもしれません。これは次の座席に座っている女性の関心事でもあります。各テーブルには少なくともk人のゲストが必要です。

私はこれらの要件を満たすために、最大フローを使用してアルゴリズムを設計しようとしていますし、私は実際にいくつかのアイデアをいただければ幸いです

Answer 1

この問題はNP困難一般的です。 2nノードのグラフがあり、サイズが2nのテーブルが1つしかないとします。さて、グラフがハミルトニアンサイクルを持っている場合にのみ、あなたが望むように誰もがテーブルの周りに座る方法があります。二部グラフのハミルトニアンサイクル問題はNP困難なので、問題はNP困難です。その結果、指数関数的に大きなグラフを作成しない限り、この特定の問題を解決するためにmax-flowを使用する良い方法があるとは思えません。