特定のエッジを削除する最小カーディナリティグラフパーティション
Aug 21 2020
解決したい計算上の問題があります。それがすでに文学で研究されているのか、もしそうなら、どのような名前で研究されているのかはわかりません。文献へのポインタやアルゴリズムの提案をいただければ幸いです。
入力：接続された無向グラフG =（V、E）で、特定のエッジに「不良」のラベルが付けられています。
出力：1）パーティションの誘導部分グラフのすべてが接続され、2）誘導部分グラフのいずれにも不良エッジが含まれないようなVの最小カーディナリティパーティション。
ありがとう！
回答
1 PålGD Aug 21 2020 at 03:46
すべてのエッジが不良エッジである場合に何が起こるかを見てみてください。
私が尋ねたら、質問は何でしょうか：
グラフを赤、緑、青などの3つのパーティションに分割して、すべてのエッジについて、各エッジの端点の「色」が「色」になるようにすることはできますか。
（隣接していないすべての頂点の間に「適切な」エッジを追加して、グラフを完全なグラフにしましょう。）