最大、最大クリーク

Question

私はこのイメージに基づいて練習をしています。私は最大クリークサイズが4であることを発見しました。私はグラフ理論の概念についていくつかの質問を持っています。

クリークは、各頂点のペアが接続されている完全な部分グラフです。 3クリークを数えれば（3,4,5）、（3,4,6）、（3,5,6）、（4,5,6）は3クリークとしてカウントされますか？ ？あるいは、それらが4クリークの一部であるので、それらの部分グラフを省略しなければならない。

すべてのグラフに1つだけ最大クリークがありますか？視覚的に私の心の中でそれを想像して、私は複数の最大クリークを持つことが可能であるように感じる。

1つ以上のノードを持つすべてのグラフに少なくとも1つのクリークが必要かどうかを尋ねる質問の1つです。 2クリーク（ちょうど縁）なのか、それともすべてのクリークが閉じた形になるのでしょうか？

私は3クリークを持たない4クリークのインスタンスを描くように見えないので、4クリークごとに少なくとも1つの3クリークがあると仮定することは安全ですか？このようなことを大規模に確認するにはどうすればいいですか？

Answer 1

まず、あなたが言及した3つのクリークはすべて実際にクリークです。
あなたが言ったように、クリークはすべてのノードが他のすべてのノードに接続されているサブグラフです。あなたの例では、（3,4,5）はクリークであり、（3,4,5,6）も同様です（3）、（3,4）です（あなたの他の質問にも答えます） ）。

最大クリークに関しては、もちろん、あなたはグラフから（3,4,5,6）を取った場合、それを（3 '、4'、5 '、 6 '）、3を3'に接続すると、グラフに2つの4クリークがありますが、5クリークはありません。

また、すべてのサブグラフが他のすべてのノードに接続されているという要求を満たしているため、クリークのサブグラフもクリークです。たとえば、グラフでは（3,4,5,6）は4クリークです。 3つのノードをそこから取ると、3つのクリークを得るでしょう。あなたは2クリークを手に入れます。実際、すべての4クリークに少なくとも1つの3クリークがあるだけでなく、それには4クリークが4つあります（それは4C3です）。

ただし、クリークは2つ以上（時には3つ以上）のノードを持つものとして定義されることがあります。これは、より良い言葉がないため、小さいものは少し些細なものだからです。