📂グラフ理論

完全グラフ

定義

グラフ $G$ の全ての 誘導された サブ グラフ $H$ が次を満たすとき、完全グラフという。 $$\chi (H) = \omega (H)$$

---

• $\chi (H)$ はグラフ $H$ の クロマチック数だ。
• $\omega (H)$ はグラフ $H$ の クリーク数だ。

説明

グラフ理論の世界は、多くの数学の分科がそうであるように、途方もなく広い、正直もう少し広いと言いたい。グラフで頂点とエッジを定義する方法があまりにも多様だからだ。路線グラフはもちろん、区間グラフのように、グラフである必要がなかったものでもグラフはグラフである。

ただ、それが価値があるかどうかは別の問題だ。グラフの研究で価値があると考えられる場合は、グラフ彩色や連結性、距離的性質などに関する内容が最も簡単に思いつくだろう。単にグラフが定義されただけでは、大きな注目を浴びるのは難しい。

完全グラフは、グラフ彩色に特に興味を持つ意味で、完璧なグラフと見なすことができる。すべてのグラフ $H$ は、クリーク数 $\omega (H)$ に対して当然 $$\omega (H) \le \chi (H)$$ どんなグラフでも、サブクリーク $K_{n}$ が存在するなら、当然 $n-1$ 色で彩色できないからだ。完全グラフは、不等号が適用される場合を除外したもので、クリーク以外は必ずより少ない色で彩色できる。

純粋なグラフ理論は組み合わせ論の一つの分野と見なされ、組み合わせの問題では、このような完全グラフのような概念が必ず登場する。