【グラフ理論】トゥラングラフとは？ トゥラングラフの定義・性質について解説
こんにちは！半沢です！
今回の記事ではグラフ理論におけるトゥラングラフ(Turán graph)について解説したいと思います。
トゥラングラフはある大きさのクリークを持たないグラフの中で，辺の数が最大となるようなグラフです。
この記事ではトゥラングラフの定義・性質について書いていきたいと思います。
ぜひ読んでいってください。
トゥランの定理
トゥラングラフの名称は，トゥランの定理を証明したPál Turánさんにちなみます。
そのためトゥランの定理を一応ここで確認しておきましょう。
トゥランの定理
\(p\text{-}\)クリーク\(\,(p\geq 2)\,\)を持たない\(\,n\,\)点からなる，単純グラフの辺の数\(\,|E|\,\)について
が成り立つ。
※今回の記事ではトゥラングラフの紹介に重点を置きたいので，\(p\text{-}\)クリークの説明はWikipediaをご参照ください。
またトゥランの定理の証明は省略します(気になる方は参考図書\([2]\)を読むと良いでしょう)。
トゥラングラフは「この不等式の上界ギリギリを与えるグラフは何か？」という問いの答えになっています。
どうしてそのようになるのかを次章で直感的に理解しましょう。
トゥラングラフ(Turán graph)
導入
\(n\,\)点からなる\(\,p\text{-}\)クリークを含まないグラフの中で
辺の数ができるだけ多くなるようなものを構成することを直感的に考えましょう。
\(p\text{-}\)クリークさえ含まなければよいので，まずは\(\,(p-1)\text{-}\)クリークをどんどん作っていくのが良いでしょう。
\(n\,\)を\(\,(p-1)\,\)で割ったときの商を\(\,r\,\)，余りを\(\,s\,\)とすると
下図のように\(\,r\,\)個の\(\,(p-1)\text{-}\)クリーク\(\,K_{p-1}^{1},\ldots,K_{p-1}^{r}\,\)と，余りを集めた\(\,s\text{-}\)クリーク\(\,K_{s}\,\)ができます(図は\(\,r=3\,\)の場合)。
後の説明のために各クリーク内の点に番号を，上図のように番号をつけましょう。
さらに辺を増やそうとすると，できたクリーク\(\,K_{p-1}^{1},\ldots,K_{p-1}^{r},K_s\,\)の間に辺を付け加えれば良いですね。
そこで\(\,K_s\,\)と他のクリークの間に，条件を満たすように辺を付け加えていきましょう。
※ここで\(\,K_{p-1}^{1}\,\)ではなく\(\,K_s\,\)内の点を考えた理由は，
\(K_{p-1}^{1}\,\)から始めても良いのですが，そうすると後々\(\,K_s\,\)内の点を考えるときに説明がやや面倒になるからです(実際にやってみると分かります)。
\(K_s\,\)内の番号\(\,1\,\)の点\(\,s_1\,\)が\(\,K_{p-1}\,\)内のすべての点と辺を持ってしまうと，
\(s_1\,\)と\(\,K_{p-1}^{1}\)の点で\(\,p\text{-}\)クリークができてしまいます。
そこで下図のように点\(\,s_1\,\)を，\(\,K_{p-1}^{1}\,\)内の番号が\(\,1\,\)である点\(\,k_1\,\)以外の点と辺で結ぶと，条件を満たしたまま辺を追加することができます。
続いて\(\,K_s\,\)内の番号\(\,2\,\)の点\(\,s_2\,\)について考えましょう。
同様の理由で条件を満たすには，点\(\,s_2\,\)は\(\,K_{p-1}^{1}\,\)内のどれか一点とは辺を持たないようにしなければなりません。
また仮に点\(\,s_2\,\)は点\(\,k_1\,\)との辺は持たないとし，それ以外の番号の点と\(\,s_2\,\)を結ぶとすると
点\(\,s_1,s_2\,\)と\(\,K_{p-1}^{1}\,\)の\(\,k_1\,\)以外の点で\(\,p\text{-}\)クリークができてしまいます。
つまり点\(\,s_2\,\)と辺を持たない点は点\(\,k_1\,\)以外から選ぶ必要があります。
そこで点\(\,s_2\,\)と，\(\,K_{p-1}^{1}\,\)内の番号が\(\,2\,\)である点\(\,k_2\,\)以外の点と辺で結ぶようにしましょう。
同様に\(\,K_s\,\)内の他の点についても，自分の番号と一致しない\(\,K_{p-1}^{1}\,\)内の点と結ぶようにして辺を増やすことができます。
さらに同様にしてクリーク\(\,K_s\,\)とクリーク\(\,K_{p-1}^{1},\ldots,K_{p-1}^{r}\,\)間の辺も付け加えることができます。
さらにさらに同様にしてクリーク\(\,K_{p-1}^{1},\ldots,K_{p-1}^{r}\,\)間の辺も付け加えることができます。
このような操作で得ることのできるグラフをトゥラングラフと呼びます。
そのためトゥラングラフが\(\,p\text{-}\)クリークを持たないグラフの中で，辺の数の最大値を与えることは，直感的にはイメージしやすいですね。
ただし本当に最大値を与えるのかどうかは示していませんので，注意してください。
次節で改めて厳密にトゥラングラフの構成方法を定義していきましょう。
定義・性質
定義
\(n\,\)点からなる完全\(\,(p-1)\,\)部グラフ\(\,K_{n_1,n_2,\ldots,n_{p-1}}\,\)で
任意の自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\leq 1\,\)となるようなものを
トゥラングラフと呼び，\(\,T(n,p-1)\,\)補足\([1]\)で表す。
この定義と導入で説明した構成方法とのつながりを説明します。
まず導入では\(\,(p-1)\text{-}\)クリークを作っていくために，\(\,(p-1)\text{-}\)クリーク\(\,K_{p-1}^{1},\ldots,K_{p-1}^{r}\,\)と余りを集めた\(\,s\text{-}\)クリーク\(\,K_{s}\,\)を構成し，それらに\(\,1,2,\ldots,p-1\,\)と番号を付けました。
これは任意の自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\leq 1\,\)となるように\(\,n\,\)点を\(\,(p-1)\,\)部に分けていったことに対応します。
番号\(\,1\,\)のグループ，番号\(\,2\,\)のグループ，\(\ldots\)，番号\(\,(p-1)\,\)のグループと分けられていることを確認してください。
そしてその後，辺を結んでいった作業が完全\(\,(p-1)\,\)部グラフの辺の結び方と対応します。
同じ番号，つまり同じグループに属する点は辺で結ばなかったことを思い出してください。
このようにしてトゥラングラフは定義されるわけですね。
トゥラングラフ\(\,T(n,p-1)\,\)は次の性質を持ちます。
- \(\,T(n,p-1)\,\)は\(\,p\text{-}\)クリークを持たない。
- \(\,T(n,p-1)\,\)の辺の数は，\(\,n\,\)を\(\,(p-1)\,\)で割った余りを\(\,s\,\)とすると，
\(\biggl(1-\dfrac{1}{p-1}\biggr)\dfrac{n^2-s^2}{2}+ {}_sC_2\)である。
- \(\,T(n,p-1)\,\)は\(\,p\text{-}\)クリークを持たないグラフの中で，辺の数の最大値を与える。
1.は構成方法から明らかで，2.は補足\([2]\)で証明します。
3.は続編で証明しています。
具体例
実際にいくつかのトゥラングラフ\(\,T(n,p-1)\,\)を眺めてみましょう。
まとめ
今回の記事ではトゥラングラフを解説いたしました。
トゥラングラフの最大性の証明を書いた続編もあるので，良ければそちらも読んでみてください。
もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。
ここまで読んでいただき，ありがとうございました。
補足
\([1]\,T(n,p-1)\,\)の表式について
定義・性質で定義した\(\,T(n,p-1)\,\)という表式を用いるには
\(n,p-1\,\)が定まったとき，トゥラングラフが本当に存在し一意的かということが問題になります(well-defined性)。
よって下のことを証明しておきます。
自然数の組\(\,(n,p-1)\,\)が一つ定められると
\(n\,\)点からなる完全\(\,(p-1)\,\)部グラフ\(\,K_{n_1,n_2,\ldots,n_{p-1}}\,\)で
任意の自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\leq 1\,\)となるようなものが存在し，一意に定まる。
ここからは表記の簡略化のために\(\,q=p-1\,\)とおきます。
[証明] \([1]\) 存在性
\(n,q\,\)は自然数なので，割り算により
\(n=rq+s\,\)かつ\(\,0\leq s\lt q\)となるような非負整数\(\,r,s\,\)が存在する。
この\(\,r,s\,\)を用いて完全\(\,q\,\)部グラフ\(\,K_{\underbrace{r+1,\ldots,r+1}_{s個},\underbrace{r,\ldots,r}_{(q-s)個}}\,\)を条件を満たすグラフとして取ることができるので，示された。
\([2]\) 一意性
任意の，条件を満たすグラフ\(\,K_{n_1,n_2,\ldots,n_{p-1}}\,\)を取ってくる。
このとき任意の自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\leq 1\,\)という条件から\(\,n_1,n_2,\ldots,n_{p-1}\,\)の最小値を\(\,r\,\)とおくと，
\(\,n_1,n_2,\ldots,n_{p-1}=r,r+1\,\)である。
そこで\(\,n_i=r\,\)となる\(\,n_i\,\)の個数を\(\,0\lt k\leq q\,\)とおくと，
\(\,K_{n_1,n_2,\ldots,n_{p-1}}=K_{\underbrace{r+1,\ldots,r+1}_{q-k個},\underbrace{r,\ldots,r}_{k個}}\,\)と書き換えられる。
ここで点の個数について\(\,(r+1)(q-k)+rk=n\,\)，
すなわち\(\,n=rq+(q-k)\,\)が成り立つ。
\(\,0\lt k\leq q\,\)より\(\,0\leq q-k \lt q\,\)なので，割り算の一意性から\(\,r,k\,\)は一意に決まる。
故に\(\,K_{\underbrace{r+1,\ldots,r+1}_{q-k個},\underbrace{r,\ldots,r}_{k個}}\,\)も一意に決まるので，題意は示された。\(\quad\square\)
\([2]\)トゥラングラフの辺の数の証明
補足\([1]\)と同様に\(\,q=p-1\,\)とおき，
\(\,n\,\)を\(\,q\,\)で割ったときの商，余りをそれぞれ\(\,r,s\,\)と書くことにしましょう。
すると\(\,T(n,p-1)=K_{\underbrace{r+1,\ldots,r+1}_{s個},\underbrace{r,\ldots,r}_{(q-s)個}}\,\)と書けることが分かりました。
よって\(\,K_{\underbrace{r+1,\ldots,r+1}_{s個},\underbrace{r,\ldots,r}_{(q-s)個}}\,\)の辺の数を求めていきます。
一般に完全\(\,q\,\)部グラフ\(\,K_{n_1,n_2,\ldots,n_{q}}\,\)グラフの辺の数が
\(|E(K_{n_1,n_2,\ldots,n_{q}})|=\displaystyle \sum_{i>j}^{q} n_in_j\)
ですので(握手補題などで簡単に証明できます)，これを式変形していけばよいですね。
ただし点の個数についての式\(\,(r+1)s+kr=n\,\)や
割り算の式\(\,n=rq+s\,\)に注意して式変形を行いましょう。
すると
となり，証明できます。\(\quad\square\)
参考図書
- \([1]\) “クリーク (グラフ理論) – Wikipedia”.Wikipedia.2024-05-24更新.https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AA%E3%83%BC%E3%82%AF_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96).2024-07-22参照
- \([2]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.285-289.
