グラフ理論入門 ４ 極値問題

４　極値問題

4.1　テュランの定理

• 極値問題
  
  • ある特別な性質を持つ最大または最小のグラフは何かを問う問題のこと。
  • ここで言う、「最大」とは、通常、与えられた頂点数に対して、もっとも多い辺を有するグラフを指す。
• 位数(order)
  
  • グラフGの頂点の個数のこと。
• サイズ(size)
  
  • グラフGの辺の個数のこと。
• 誘導分布グラフ(induced subgraph)
  
  • Gの部分グラフで、V(G)のある部分集合Wと、両端点がWの中にあるようなGの辺全体から得られるものを言う。
• テュラングラフ(Tn,k)
  
  • 与えられたnとkに対して、n頂点のグラフがKk+1と同型な部分グラフを含まないとき、k部グラフに置き換えることが可能であるが、そのような、k部グラフをテュラングラフと呼ぶ。

4.2　ケージ

• g-ケージ
  
  • 内周gを持つ最小の3-正則グラフのこと。

4.3　ラムゼー理論

• ラムゼー数(Ramsey number,r(m,n))
  
  • r(m,n)個の頂点を持つ完全グラフの任意の2色辺彩色が、赤Kmかまたは青Knのいずれかを含む、という性質に関する最小数である。実際に知られているラムゼー数は少ない。