0

無向グラフ G はいくつかの頂点グループに分割できます。「u」と「v」が異なるグループにある場合、各頂点ペア (u,v) はエッジを持ちます。そうでなければ、エッジはありません。直観的に、グループを表すために頂点 "g" を使用し、2 つのグループの間にエッジがある場合にエッジ (gi,gj) を追加すると、グラフ G はクリークです。現在、いくつかのそのようなタイプのグラフ G1...Gn があり、一部の Gi の各頂点は、一部の Gj の頂点と同じ ID を持つ場合があります。

下の例のように、グラフ G1...Gn を組み合わせてグラフ G' を取得すると、このタイプの無向グラフの名前は何ですか?

例:グラフ G3 はどのような特性を持つでしょうか?

4

1 に答える 1

1

おそらく、あなたが意味するグループは独立したセットです。ただし、Henrik が指摘したように、独立集合への崩壊は (包含的に最大のものを選択したとしても)、必ずしもクリークを生み出すわけではありません。

于 2012-11-21T10:06:21.147 に答える