完全グラフ

ウィキペディア

完全グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/11 08:32 UTC 版)

完全グラフ（かんぜんグラフ、英: complete graph）は、任意の 2 頂点間に枝があるグラフのことを指す。$n~$ 頂点の完全グラフは、$K_{n}~$で表す。また、完全グラフになる誘導部分グラフのことをクリークという。サイズ $n$ のクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランと言う。