graph - 最大で他のすべての頂点に到達できる頂点の最小セット。片方の端

Question

これはおそらくばかげた質問ですが、グラフから頂点の最小セットを要求する標準的な問題は何ですか。これらの頂点から、他のすべての頂点は、1つのエッジのみを「移動」することで到達できます。実際のアプリケーションは次のようになります。地球上の他のすべての人と1度だけ接続するには、どの人を知る必要がありますか？ありがとう！

Answer 1

これは支配集合問題であり、通常の集合被覆問題と密接に関連していると思います。