この記事は、執筆陣より平山が第74回灘校文化祭 (2020年・オンライン開催) に寄せて数学研究部の部誌として執筆した きほんの「き」から始めるグラフ理論 ～数学オリンピックの視点から～ の移植・改訂版となります。今後も継続的に加筆・修正が施される可能性があります。
0. はじめに
早速ですが、「グラフ」という単語を聞いて皆さんはどのような概念を想像しますか？明鏡国語辞典第二版 (大修館書店) には以下のような定義がなされています：
- 観察・比較を容易にするために、二つ以上の数量や関数の関係を図に表したもの
これにはいわゆる「棒グラフ」や「円グラフ」、あるいは座標平面上に直線や曲線を表現したものが含まれるでしょう。しかし今回我々が扱う「グラフ」はこれらとはかなり異なる概念です。
今回考える「グラフ」として最も身近な対象の一つに鉄道の路線図があります。路線図には実際の形状や距離などが正確には表現されていません。それでも我々が困らないのは、「それぞれの駅 (頂点) がどのように路線 (辺) で結ばれているか」が最も重要な情報だからです1。こうした「つながり方」に着目して抽象化された図形が今回扱う「グラフ」です。
言語的に定義をすると、グラフ (graph) とは有限個の頂点 (vertex) と有限本の辺 (edge) からなる図形です2。ただし各辺は $2$ つの頂点 (同じでも構わない) を結ぶものとします。この一見単純で抽象的な対象に様々な情報を乗せていくことで多彩な結果が展開されるのがグラフ理論であり、その汎用性の高さから組み合わせ論において重要な立ち位置を占めています。
ところでこのグラフ理論ですが、タイトルにもある通り数学オリンピックにおいても題材となることが少なくありません。一つ例を見てみましょう。この問題は本編で再び扱います。
$17$ 人の人がそれぞれ他の全員と手紙をやり取りしている。それらの手紙は $3$ つの言語でやり取りされており、同じ $2$ 人の間でやり取りされる手紙は常に同じ言語で書かれている。このとき、互いに同じ言語で手紙をやり取りしている $3$ 人組が存在することを示せ。
数学オリンピックでグラフ理論が題材となっている問題は上のように適当な設定付けが行われていることが多く、題意を理解する上で直接的にグラフ理論の知識が求められることは基本的にありません。しかしながらグラフ理論の知識を有していると見通しが良くなるケースが殆どです。不思議なことに数学オリンピックにおけるグラフ理論は、いわゆる競技プログラミングなどにおけるそれと比べて遥かに開拓が進んでいない印象があり、全体的に難易度も過大評価されているように見えます。したがって一定の訓練を積めば、ある程度の難問でも物にできるチャンスがある分野と言えましょう。
基本的に一切の前提知識を仮定せず記述していくので、ある程度の心得があるという方は適宜スキップしてください。
1. 基本的な用語
まずは大前提となる基本的な用語の定義を列挙します3。
- ある辺が結ぶ頂点を端点 (endpoint) と呼びます。ある頂点がある辺の端点であるときこれらは接続している (incident) と言います。
- ある $2$ つの頂点を結ぶ辺が存在するとき、これらは隣接している (adjacent) と言います。またある$2$つの辺が端点を共有しているときこれらを隣接している (adjacent) と言います4。
- ある辺の両端点が等しいとき (自己)ループ (loop) と呼びます。またある $2$ 頂点間に複数の辺が存在するとき多重辺 (multiple edges) と呼びます。ループも多重辺も含まないグラフを単純 (simple) と言います。
以下、特に断りがない限り単に「グラフ」と言えば有限・単純・無向なものを指すものとします。
- グラフ $G$ について、その頂点集合を $V(G)$、辺集合を $E(G)$ で表すものとします。
- $2$つのグラフ $G$ と $G’$ について、$V(G’)\subseteq V(G)$ かつ $E(G’)\subseteq E(G)$ であるとき、$G’$ を $G$ の部分グラフ (subgraph) と呼びます5。特に、「$G$ の辺であって両端点が $V(G’)$ に属するもの全体」が $E(G’)$ に一致するとき、$G’$ を誘導部分グラフ (induced subgraph) と呼びます6。
- ある頂点に接続する辺の数を次数 (degree) と呼びます。すべての頂点の次数が $k$ で等しいグラフを $k$-正則 (regular) と呼びます。特に、任意の $2$ 頂点間に辺が存在する $n$ 頂点の (単純) グラフを完全グラフ (complete graph) と呼び、$K_{n}$ で表します。これは $(n-1)$-正則です。
以下の命題は定義より明らかですが非常に重要なもので、問題を解く上で意外な盲点になることもあります。
- 隣接する頂点を辿って出来る経路のうち7、経由する辺の重複を許さないものを路 (trail)、さらに経由する頂点の重複も許さないものを道 (path) と呼びます。また始点と終点が一致する路を閉路 (cycle)と呼びます8。ある道に含まれる辺の本数を長さ (length)と呼びます。
$(2)$ あるグラフにおいて頂点 $A$ と $B$、$B$ と $C$ の間にそれぞれ道が存在するとき、$A$ と $C$ の間にも道が存在する。
- あるグラフの任意の $2$ 頂点を結ぶ道が存在するとき連結 (connected) と言い、そうでないとき非連結 (disconneted) と言います。あるグラフ $G$ の連結な部分グラフ $G’$ であって、$G’$ を部分グラフとする連結な $G$ の部分グラフが $G’$ しか存在しないものを $G$ の連結成分 (connected component) と呼びます9。
- 連結グラフ(あるいは同じ連結成分)において、ある $2$ 頂点間を結ぶ道の長さの最小値を距離 (distance) と呼びます。
- 取り除くと連結成分の数が増えるような辺を橋 (bridge) と呼びます。
何がグラフとみなせるか？
冒頭で述べた通り、グラフ理論を背景とする数学オリンピックの問題のステートメントのほとんどはグラフ理論の用語で記述されていません。多くは日常感のある設定に置き換えられており、代表的なものとしては人間関係 (友人である・同じグループである etc.) や交通網 (航空網・高速道路 etc.) などが挙げられます。
しかしながら、一見グラフに関係するようには全く見えないが実はグラフとみなせる状況も数多く存在し、これはグラフ理論の醍醐味の一つと言えるかもしれません。一例としてはマス目です。
$m,n$ を正整数とする。$m\times n$ のマス目において、次の条件をみたすように各マスを黒または白に塗る：任意の黒マスについて、隣接する(一辺を共有する)黒マスは奇数個である。このとき黒マスの総数は偶数であることを示せ。
一般にマス目に対して、各マスを頂点とし隣接する $2$ マス間に辺を張ったグラフを考えることがしばしばあります。上の例題は黒マスについてこのグラフを考え、握手の補題 (系1.2.) を適用することで直ちに示されます。
他にもより奇抜なグラフの構築を求められることはしばしばあります。そもそも設定がC分野ではないかもしれません。(ネタバレにはなりますが) 例えば以下は誰しもがA分野の問題だと思うでしょう (練習問題として再掲します)。
$n$ を正の偶数とする。$n$ 個の (相異なるとは限らない) 実数 $a_{1},\cdots,a_{n}$ について、$1\lt |a_{i}-a_{j}|\lt 2$ をみたす組 $1\leq i\lt j\leq n$ の個数の最大値を求めよ。
逆にグラフのように見えるが別なる視点から捉え直した方が良い問題も無論あります。
このように分野をクロスオーバーする問題は、ともすれば大外れした方針に嵌まり込んでしまう危険性もありますが、数学オリンピックの面白さの一つでもあります。地道に実験と考察を重ねて手がかりをつかみましょう。
練習問題
連結グラフにおいて最長のパスが $2$ つ存在するとき、これらはある共通の頂点を経由することを示せ。
連結グラフの辺 $e$ について、$e$ が橋であることは $e$ を含む閉路が存在しないことと同値であることを示せ。
グラフ $G$ に対して、ある $2$ 頂点の間に辺が存在しないとき新たに辺を張り、元々存在した辺を消去して得られるグラフ $\overline{G}$ を補グラフ (complement graph) と呼ぶ。$G$ が非連結ならば $\overline{G}$ は連結であることを示せ。
$n\geq 3$ を整数とする。各頂点に $1\sim n$ の番号が振られた $n$ 頂点の連結グラフであって、以下の条件をみたすものが存在することを示せ：隣接する頂点の番号の総和が頂点によらず等しい。
$V(G)$ の部分集合 $D$ が支配的 (dominating) であるとは、任意の頂点 $v\in V(G)\setminus D$ について $v$ と隣接する頂点 $w\in D$ が存在することである。任意のグラフ $G$ について支配的な集合は奇数個であることを示せ。
区分線形関数 $f:[0,1]\to\mathbb{R}_{\geq 0}$ は $f(0)=f(1)=0$ をみたす。$2$ 点 $P,Q$ が初めそれぞれ座標 $(0,0),(1,0)$ におり、$2$ 点の $y$ 座標が常に一致するように曲線 $y=f(x)$ 上を連続に動く。適切に動くことで $2$ 点は出会えることを示せ。
$m\times n$ のマス目において、各マスが黒または白で塗られている。いま「あるマスを指定し、自身及び隣接するマスすべての白黒を反転させる」という操作を何回か行う。すべてのマスの白黒が反転した状態を作ることは可能か？
2. きほんの「木」
$(1)$ $G$ は閉路を持たない
$(2)$ $G$ はちょうど $n-1$ 辺からなる
$(3)$ $G$ の任意の $2$ 頂点について、これらを結ぶ道が一意に存在する
$(4)$ $G$ の辺はすべて橋である (すなわち $G$ からどの辺を取り除いても非連結となる) 10
$(1)\Longrightarrow (2)$：$n$ 個の頂点のみがある状況から辺を $1$ 本ずつ加えることを考えると、閉路を持たないという条件から辺を $1$ 本加えるごとに連結成分の個数はちょうど $1$ ずつ減少する。同様の過程より逆も従う。
定理2.2.の条件の一つ (すなわちすべて) を満たすような連結グラフを木 (tree) と呼びます。以下の系は定理2.2.の証明よりただちに得られますが、系2.3.は不等式評価などで盲点になりがちですし、系2.4.も決して完全に自明ではありません。
これらの性質をみたすグラフが「木」と呼ばれる所以を探りましょう。ある頂点を選び、それが一番「上」にあるとします。このとき、定理2.2.(3)を考慮すると、$2$ 頂点の間に「上下」の関係を考えることが出来ます11。ここで一番「上」に定めた頂点を根 (root) と呼び、このような木を特に根付き木 (rooted tree) と呼びます12。木は任意の頂点を根として根付き木とみなすことができ、この操作によって扱いが良くなることが多いです。
$2$ 頂点 $u,v$ が隣接しており、かつ $u$ の方が $v$ より根に近いとき、$u$ は $v$ の親 (parent)、$v$ は $u$ の子 (child) と言います。一般に $v$ と根を結ぶ経路上に $u$ があるとき、$u$ は $v$ の祖先 (ancestor)、$v$ は $u$ の子孫 (descendant) と言います。
(根以外で) 次数 $1$ の頂点を葉 (leaf) と呼びます。「子を持たない」とも表現できます。補題2.1.より葉は必ず存在します。
深さ優先探索 (DFS)
根付き木の重要な応用例の一つとして深さ優先探索 (depth-first search) を紹介します。情報科学の用語ですが、その発想自体は数学オリンピックにも無用ではありません13。これは一般のグラフの頂点を全探索するアルゴリズムの一つです。
まず根付き木に対するDFSは定式的に以下のように表現されます。頂点 $u$ に対し操作 $op(u)$ を以下で定めると、根 $r$ について $op(r)$ によって全ての頂点を一度ずつ経由できることが確認できます。これがDFSです。
- $op(u)$：$u$ の子 $v$ それぞれについて $op(v)$ を順に行う。ただし $u$ が葉のとき何もしない。
より噛み砕いて言語化すると以下のようになります。実際に適当な根付き木を描いて追ってみましょう14 15。
- 根からスタートし、適当な子を選びながら下れるだけ下る。
- 葉に到達したら、一つずつ後戻りする。
- 訪れていない子が存在するとき、そこから適当な子を選びながら下れるだけ下る。
- 2.と3.を繰り返し、根に再び戻ってきたら終了する。
この方法を応用して、一般のグラフに対してもDFSを考えることが出来ます。
- 適当な頂点からスタートし、隣接する頂点であって過去に訪れていないものを適当に選びながら進めるだけ進む。
- 進める頂点が無くなったら、一つずつ後戻りする。
- 隣接する頂点であって過去に訪れていないものが存在するとき、1.に戻る。
- 最初にスタートした頂点に再び戻ってきたら終了する。
上の手順で明らかに全ての頂点を経由します。ここで途中で通った辺集合に着目すると、連結で閉路を含まないことから木、すなわち全域木をなしていることがわかります。DFSは全域木を取得する最も単純なアルゴリズムの一つでもあります。
ここでは取り扱いませんが、同様のアルゴリズムに幅優先探索 (breadth-first search) があります。これはある頂点から見た「深さ」が等しい頂点をすべて同時に見ていくことで探索を行います。DFSとBFSにはそれぞれの長所があります。
練習問題
$n$ 頂点のグラフのいくつかの辺を赤く塗る。任意の頂点で接続する赤い辺を奇数本に出来るか？
$2010$ 個の島とそれらを繋ぐ $2009$ 本の橋が木をなしている。それぞれの島が $1$ 通の手紙をいずれかの島 (自身でも良い) に送付したところ、以下が成立した：
- 島 $A$ と $B$ が隣接しているとき、$2$ 島の手紙の送付先は隣接しているか同一である
このとき「自分自身に手紙を送った島」または「互いに手紙を交換した隣接する $2$ 島」の存在を示せ。
無限に広がるマス目のうち、連結な $2007$ 個以上のマスからなる集合を恐竜と呼ぶ。特に恐竜が原始的とは、二つ以上の恐竜に分割されないことを言う。原始的な恐竜に含まれるマス数の最大値を求めよ。
$n$ 頂点からなる単純 (外周が自己交差しない) 多角形 $P$ について、以下の条件をともにみたす対角線の存在を示せ：
- $P$ の内部に完全に含まれる
- 二つに分けられた外周それぞれが $n/3-1$ 個以上の頂点を含む (対角線の端点を除く)
3. 辺彩色
辺彩色 (edge coloring) とは、読んで字の如くグラフの辺をいくつかの色を用いて塗り分けることです。ここで (当然ですが) それぞれの辺全体は同じ色で塗るものとします。一般的に「辺彩色」と言えば「隣接する辺は異なる色で塗る」という制約が課されることがほとんどですが、ここではこの制約を課した辺彩色を特に最適辺彩色と呼んで区別するものとします。
Ramseyの定理
Ramseyの定理とは辺彩色における最も根本的な主張の一つで、一般には以下のように記述されます16 17。
ここでは最も単純な結果である18 以下の定理について $2$ 通りの証明を与えます。いずれの証明も汎用性が高く、より複雑な問題にも容易く応用できるアイディアを含んでいます。なお「Ramseyの定理」で単に以下を指すこともあります。
最適辺彩色
あるグラフを出来るだけ少ない種類数の色で最適辺彩色することを考えます。グラフ $G$ を最適辺彩色するために必要な色の種類数の最小値を $\gamma(G)$ で表し、これを求めたいです。まず最もシンプルなケースとして以下が考えられます。
この場合は明らかですが、実際には木のみならず、一般に二部グラフについても同様の主張が成立することが知られています。$\gamma(G)\geq\Delta$ は定義より明らかですが、二部グラフならば常に等号が成立する事実は十分な驚きをもって迎えられます。
さらに一般のグラフについても類似の主張が成立します。一般的にかなり高い効率で最適辺彩色が可能ということです。
証明はこちらのPDFなどを参照してください。残念ながら具体的に $\Delta$ なのか $\Delta+1$ なのかを一般的に判定することは困難ですが、一部のケースについては確定させることが出来ます。例えば完全グラフ $K_{n}$ などは良い演習になるでしょう (練習3-1)。解答は同じPDFに掲載されています。
練習問題
完全グラフ $K_{n}$ を最適辺彩色するのに必要な色の種類数の最小値、すなわち $\gamma(K_{n})$ を求めよ。
$K_{25}$ の各辺を赤または青で塗る。同色の辺からなるクリーク $K_{3}$ の個数の最大値を求めよ。
$17$ 人の人がそれぞれ他の全員と手紙をやり取りしている。それらの手紙は $3$ つの言語でやり取りされており、同じ $2$ 人の間でやり取りされる手紙は常に同じ言語で書かれている。互いに同じ言語で手紙をやり取りしている $3$ 人組が存在することを示せ。
$n$ を $6$ と互いに素な整数とする。正 $n$ 角形の各頂点を、どの色も奇数回使うように $3$ 色で塗り分けた。このとき、正 $n$ 角形の頂点からなる二等辺三角形であって、頂点の色がすべて異なるものの存在を示せ。
4. 二部グラフ
グラフ $G$ の頂点集合について、これを $n$ 個の部分集合に分割し (これらを独立集合 (independent set) と呼びます) 各部分集合内の頂点間には辺が張られていないように出来るとき、$G$ を $n$ 部グラフ (n-partite graph) と呼びます。
$n$ 部グラフは「最適頂点彩色」によって特徴付けされます19。すなわち、隣接する頂点が異なる色になるように頂点を「彩色」するとき、ちょうど $n$ 色を用いてこれが可能であるようなグラフが $n$ 部グラフです。ここから明らかに、$m\gt n$ に対して $n$ 部グラフは $m$ 部グラフであることがわかります。
異なる独立集合に属する頂点対すべてに辺を張った $n$ 部グラフを完全 $n$ 部グラフ (complete n-partite graph) と呼びます。特に各独立集合のサイズが $a,b$ である完全二部グラフを記号 $K_{a,b}$ で表します。
ここでは特に $n=2$ とした二部グラフ (bipartite graph) の性質について見ていきます。「男女間の知り合い関係」などに代表されるように様々な設定から立ち現われる、極めて自然な対象です。
二部グラフの最も重要な言い換えが以下の定理4.2.です。直感的に明らかに思えるようになると良いです。
上の定理の意外な応用例を見ることが出来ます。なお実際のところ後半はただのオマケで、前半の方が本質的です20。
Hallの結婚定理
あるグラフのマッチング (matching) とは、辺集合であって互いに端点を共有しないものを言います。特に二部グラフにおけるそれ (二部マッチング) は重要な興味です。唐突ですが合コンを想像してみましょう。同じ人数の男女が参加しており、各人には好みの異性が何人かいます。このとき全員が好みの異性と結ばれるような「マッチング」(完全マッチングと呼ばれます) は存在するでしょうか？これに対して簡潔な必要十分条件を与えるのが以下の定理です。
この定理の少し特殊な応用例の一つとして、各マスに $0$ または $1$ が書き込まれているマス目が題材となった問題があります。このとき、各行および各列に対応する頂点を作り、$1$ が書き込まれているマス目の行・列に対応する頂点間に辺を張った二部グラフを構築します。ここに何らかの形で上の定理を適用すると、常にでは無いにせよ、上手くはまることが少なくないです。以下の練習問題にもいくつか選んだのでチャレンジしてみてください。
練習問題
$n$ 個の島があり、初めはどの島の間にも橋が架かっていない。橋の架かっていない $2$ 島を選びその間に橋を架ける操作を $2$ 人が交互に繰り返す。ただし以下の条件が常に満たされねばならない：
- どの島からも奇数本の橋を渡って自身へ戻ってこれない。
先に橋を架けられなくなった方を負けとするとき、先手必勝となる $n$ をすべて求めよ。
$n$ を奇数とし、$S$ を $n$ 個の座標平面上の格子点からなる集合とする。置換 $f$：$S\to S$ について次が成り立つとする：
- 任意の $A,B\in S$ に対し、$f(A)$ と $f(B)$ の距離は $A$ と $B$ の距離以上である。
このとき $f(X)=X$ なる $X\in S$ が存在することを示せ。
$d_{1},d_{2}$ を正整数とする。座標平面上の点の集合 $S$ が良いとは、$S$ に属するどの $2$ 点間の距離も $\sqrt{d_{1}}$ および $\sqrt{d_{2}}$ でないことを指す。$n$ 個の格子点からなる集合に対し、$n/4$ 点以上からなる良い部分集合が存在することを示せ。
マス目 $n\times n$ の各マスに $0,1,-1$ のいずれかが書き込まれており、$1$ および $-1$ は各行および各列にちょうど $1$ つずつ書かれている。このとき、行および列をそれぞれ適当に入れ替えることで、元のマス目の $1$ と $-1$ を完全に入れ替えられることを示せ。
各マスに非負整数の書き込まれた $n\times n$ のマス目のうち、各行および各列に書かれた数の総和が $1$ 以上ですべて等しいものを不思議な配置、特に $n$ 個の $1$ と $n(n-1)$ 個の $0$ からなるものを単純な配置と呼ぶことにする。任意の不思議な配置は有限個の単純な配置の和として表せることを示せ。
各マスに $0$ または $1$ が書き込まれた $n\times n$ のマス目が以下の条件をみたす
- 同行および同列のものを含まないような任意の $n$ マスからなる部分集合には、少なくとも $1$ が一つ以上存在する。
このとき、$i+j\geq n+1$ かつ共通部分の $ij$ マスにすべて $1$ が書かれているような $i$ 行および $j$ 列の存在を示せ。
5. 隣接行列
著者注：この節の内容はまだまだ不十分で、改善の余地を広大に余しています。将来的に補強および分離を計画中です。
$n$ 頂点の有向グラフ $G$ に対し、頂点 $i$ から $j$ への辺が存在するとき $a_{ij}=1$、それ以外のとき $a_{ij}=0$ として $n\times n$ 行列 $A$ を定めます。ただし $a_{ii}=0$ とします。これを $G$ の隣接行列 (adjacency matrix)と呼び、以下に挙げるような良い性質を持ちます。いずれも定義から容易に従うので各自で確認してみてください。
- 正整数 $k$ に対し、行列 $A^{k}$ の $ij$ 成分は「頂点 $i$ から $j$ に至る長さ $k$ の相異なる歩道の数」を表す。
- 成分がすべて $1$ の $n$ 次元列ベクトルを $I$ で表すと、列ベクトル $AI$ の $i$ 成分は頂点 $i$ の出次数を表す。
- $A$ の転置を $A^{\top}$ で表すと、列ベクトル $A^{\top}I$ の $i$ 成分は頂点 $i$ の入次数を表す。
- 行列 $AA^{\top}$ において、$ii$ 成分は頂点 $i$ の出次数を表し、$ij$ 成分 ($i\neq j$) は「頂点 $i$ を始点とする辺と頂点 $j$ を始点とする辺で共通して終点となる頂点の数」を表す。
- 行列 $A^{\top}A$ において、$ii$ 成分は頂点 $i$ の入次数を表し、$ij$ 成分 ($i\neq j$) は「頂点 $i$ を終点とする辺と頂点 $j$ を終点とする辺で共通して始点となる頂点の数」を表す。
無向グラフに対しても同様に定められます。すなわち頂点 $i$ と $j$ が隣接しているとき $a_{ij}=1$、それ以外のとき $a_{ij}=0$ とします。$A$ が対称行列 (すなわち $A=A^{\top}$) であることに留意すると、上の諸性質は以下のように書き換えられます。
- 正整数 $k$ に対し、行列 $A^{k}$ の $ij$ 成分は「頂点 $i$ と $j$ を結ぶ長さ $k$ の相異なる歩道の数」を表す。
- 成分がすべて $1$ の $n$ 次元列ベクトルを $I$ で表すと、列ベクトル $AI$ の $i$ 成分は頂点 $i$ の次数を表す。
- 行列 $A^{2}$ において、$ii$ 成分は頂点 $i$ の次数を表し、$ij$ 成分 ($i\neq j$) は「頂点 $i$ と $j$ に共通して隣接する頂点の数」を表す。
このような値を演算で取り出せるのは扱いが良く、隣接行列の性質を調べることで問題が解けることもあります21。
ある学校において、どの男女の組も互いに知り合いであるか知り合いでないかのいずれかである。どの男子もちょうど $n (\geq 2)$ 人の女子と知り合いであり、どの女子もちょうど $n$ 人の男子と知り合いである。また、どの $2$ 人の男子についても共通の知り合いである女子はちょうど $k (\geq 0)$ 人である。このとき、どの $2$ 人の男子についても共通の知り合いである女子はちょうど $k$ 人であることを示せ。
生徒を頂点とみなし、知り合いである男女の間に辺を張った二部グラフを考えると、一つ目の条件から辺数を考えることで男子と女子の人数が等しいことがわかるので、これを $x$ とおく。$x\times x$ の単位行列を $E$、すべての成分が $1$ の $x\times x$ 行列を $I$ とおく。$i$ 人目の男子と $j$ 人目の女子が知り合いのとき $a_{ij}=1$、それ以外のとき $a_{ij}=0$ とすることで正方行列 $A$ を構成すると、各条件より $AA^{\top}=kI+(n-k)E$ が従う (これを $T$ とおく) 22。$x$ 本の列ベクトルの一次独立性より $T$ は正則で 23、特に $A$ も正則である。また一つ目の条件より $AI=IA=nI$ であり 24、 $AE=EA=A$ と合わせて $AT=TA$ が従う。よって $A^{\top}A=A^{-1}TA=T$ であり、これが示すべきことであった。
もちろん線型代数を前提にした問題は数学オリンピックでは出題されませんから、基本的になんらかの純粋に組み合わせ論的な解法は存在するのですが、一つの武器として持ち合わせておくに越したことは全くありません。いくら「オーバーキル」のように見えたところで正解は正解です。好機を逃さないようにしましょう。
練習問題
何人かの数学者がおり、どの $2$ 人も互いに知り合いかそうでないかのいずれかである。彼らを次の条件をみたすように $2$ つのグループに分ける方法の場合の数は $2$ べき (ある非負整数 $k$ を用いて $2^{k}$ と表せる整数) であることを示せ：
- どの数学者についても同じグループに知り合いが偶数人いる。
6. 雑多な話題たち
ハミルトン路
グラフ上のすべての頂点を一度ずつ通る路のことをハミルトン路 (Hamiltonian trail) と言い、特に閉路であるときハミルトン閉路 (Hamiltonian cycle) と呼びます。一般に与えられたグラフがハミルトン (閉) 路を持つための条件を記述するのは困難ですが、辺が「ある程度の密度で」存在すればハミルトン閉路を持つという事実にあまり不思議は無いでしょう。
証明を観察すると、条件は弱められることがわかります。すなわち以下の拡張が容易に可能です。
なお以上の $2$ 定理において、$G$ の連結性は条件より従うことに注意してください。最小の連結成分を考えれば良いです。
ハミルトン路のうち、特にすべての辺を一度ずつ通るものをオイラー路 (Eulerian trail) といい、特に閉路のときオイラー閉路 (Eulerian cycle) と呼びます。これはいわゆる「一筆書き」に相当するもので馴染み深く、簡潔な必要十分条件の存在も有名です。しかし特に「すべての次数が頂点が偶数のときオイラー閉路が存在する」という事実は盲点になりがちです。
クリーク
クリーク (clique) 22 とは、あるグラフの部分集合となっている完全グラフのことです。
なお, $K_3$ を含まないという条件は「triangle-free」とも言います。実際 $K_{3}$ は完全グラフというよりかは単なる閉路として意識されるのが普通な気はします。
なお, 頂点を $n/2$ ずつ独立集合に分けて構成される完全二部グラフを考えると、この評価はstrictです。
このMantelの定理の一般化として得られたのが、次のTuránの定理です。実際 $r=2$ とすれば主張が一致します。
- $d(v)\lt d(u)$ のとき：頂点 $v$ を取り除き、代わりに $u$ の「コピー」(隣接している頂点の集合が一致する) $u’$ を作る。$u$ と $u’$ の間に辺を張らないと定めると、クリークのサイズの最大値は増加せず、辺の本数は増加することがわかる。$d(v)\lt d(w)$ の場合も同様。
- $d(v)\geq d(u)$ かつ $d(v)\geq d(w)$ のとき：上と同様に、$u$ と $w$ を取り除き、代わりに $v$ の「コピー」を $2$ つ作ればよい。
以上より $\sim$ は同値関係である。したがってある $k$ が存在して $G’$ は $k$ 部グラフであり、特にクリークの条件より $k\leq r$ が必要である。残りは単なる不等式評価の範疇であるから割愛する。
またこの章立てとは直接関係ないですが、参考までにMantelの定理の別視点からの拡張である以下の結果を紹介します。
同じ対象を $2$ 通りで評価する、いわゆる「ダブルカウント」と呼ばれる手法を用います。他に練習3-4がその例です。
有向グラフをはじめ、ここでは統一的に取り上げなかったテーマは他にも多数存在します。興味のある人は探求してみると良いでしょう。なお以下の練習問題はこれらの内容も含めて総合的にチョイスしています。骨のある問題も多いですから、是非じっくり腰を据えて実力試しをしてみてください。
練習問題
無向グラフ $G$ についてどの頂点の次数も $3$ であるとする。$G$ がハミルトン閉路をもつとき、それと異なる (経由する辺集合が一致しない) ハミルトン閉路が存在することを示せ。
$n$ を正の偶数とする。$n$ 個の (相異なるとは限らない) 実数 $a_{1},\cdots,a_{n}$ について、$1\lt|a_{i}-a_{j}|\lt 2$ をみたす組 $1\leq i\lt j\leq n$ の個数の最大値を求めよ。
$n$ 頂点 $m$ 辺のグラフは $\displaystyle \frac{m(4m-n^{2})}{3n}$ 個以上のクリーク $K_{3}$ を持つことを示せ。
$n$ 頂点からなる無向グラフ $G$ が次の条件をみたすとする：
- 任意の $4$ 頂点の組 $\{A,B,C,D\}$ について、$A$ と $B$、$B$ と $C$、$C$ と $D$、$D$ と $A$ の間に辺が存在するならば、$A$ と $C$、または $B$ と $D$ の間には辺が存在する。
$G$ の相異なる極大クリーク (あるクリークに真に含まれないクリーク) は高々 $n(n-1)/2$ 個であることを示せ。
ある無向グラフ $G$ に含まれるクリーク $K_{3},K_{4}$ の個数をそれぞれ $f(G),g(G)$ とおく。このとき任意の $G$ に対して $cf(G)^{4}\geq g(G)^{3}$ が成立するような正定数 $c$ の最小値を求めよ。
各辺がいずれか一方に向き付けされた完全グラフをトーナメントグラフ (tournament graph) と呼ぶ。トーナメントグラフは (有向グラフとしての) ハミルトン路をもつことを示せ。
トーナメントグラフの各辺が赤または青で塗られている。このとき、次の条件をみたすような頂点 $v$ の存在を示せ：
- 任意の頂点 $w (\neq v)$ について、$v$ から $w$ への同色の道が存在する。
多面体の各辺がいずれか一方に向き付けされている。外周が閉路をなすような面の存在を示せ。
正整数 $n,m$ が $m(m+1)\lt 2n$ をみたす。ある国には $n$ 個の都市と $2$ つの航空会社 $X,Y$ がある。各航空会社は $2$ 都市間の (双方向とは限らない) 直行便を開設しており、次の条件をともにみたしている：
- どの都市 $C$ についても、$C$ から同じ会社のみを乗り継いで $C$ に戻ってこれない。
- どの相異なる $2$ 都市についても、いずれかからもう片方へ、同じ会社のみを乗り継いで移動できる。
このとき、ある都市から出発して次の条件をみたすように $m$ 本の直行便を乗り継げることを示せ：
- $Y$ の便の直後に $X$ の便に乗ることがない。
$m,n$ は正の整数であり、$m\geq 2,n\lt \dfrac{3}{2}(m-1)$ をみたしている。ある国には $m$ 個の都市と $n$ 本の道路があり、どの道路も $2$ つの相異なる都市を結んでいる。同じ都市間を結ぶ複数本の道路があってもよい。
いま、都市を $2$ つのグループ $\alpha,\beta$ に分割し、グループ $\alpha$ の都市とグループ $\beta$ の都市を結ぶ道路をすべて高速道路とすることになった。このとき、以下の条件をみたす分類が存在することを示せ：
- どちらのグループも都市を $1$ つ以上含む。
- どの都市に対しても、その都市から出ている高速道路は $1$ 本以下である。
$n\geq 3$ 人の人がいて、そのうち $3$ 人以上が参加する集会が毎日ある。各集会では参加したどの $2$ 人も $1$ 回ずつ握手をする。$n$ 日目の集会が終わった時点でどの $2$ 人もちょうど $1$ 回ずつ握手していたとき、すべての集会に同じ人数が参加していたことを示せ。
ある国は $2016$ 個の都市からなり、どの都市からもちょうど $1$ 本が出ているように都市間の (双方向とは限らない) 直行便を開設したい。このとき開設の仕方によらず次の条件が成立するような最小の $k$ を求めよ：
- 開設の後、都市をうまく $k$ 個のグループに分けることで、任意の都市について、同じグループ内のどの都市にも $28$ 本以下の直行便を乗り継いで移動することが不可能なようにできる。
ある学校には $4$ 人以上の生徒がおり、どの $2$ 人も互いに友人であるか友人でないかのいずれかである。$4$ 人の生徒が円卓に座ったとき、選び方や座り方によらず、両隣が友人である、または両隣が友人でない生徒が存在したという。このとき、生徒全体を $2$ つのグループに分割し、一方はどの $2$ 人も友人であり、もう一方はどの $2$ 人も友人でないように出来ることを示せ。
$4950$ 頂点からなる有向グラフ $G$ において、頂点 $A$ から $B$、および $B$ から $C$ にともに辺が張られているとき、$A$ から $C$ への辺も存在するという。このとき、以下の条件をみたす $n$ の最小値を求めよ：
- 頂点を $n$ 個のグループに分割して、各グループの頂点間には常に辺が存在するか存在しないかのいずれかに出来る。
$a,b$ を正整数とする。じゃんけん大会が行われ、どの参加者のペアについても勝ち負け引き分けのいずれかを定めた。どの参加者も$a$ 回以上勝ち $b$ 回以上負けたとき、$i=1,\cdots,a+b$ に対して $Q_{i}$ が $Q_{i+1}$ に勝ったような $a+b$ 人の参加者 $Q_{1},\cdots,Q_{a+b}$ の存在を示せ。
あるサービスには $2019$ 人のユーザーがおり、どの $2$ 人も互いに友人であるか否かのいずれかである。次のようなイベントが繰り返し起きる：
- $A$ と $B$、$A$ と $C$ が友人であり、$B$ と $C$ は友人出ないようなある $3$ 人組について、$B$ と $C$ が友人となり、$A$ と $B$、$A$ と $C$ はともに友人でなくなる。
友人の数が $1009$ 人であるユーザーが $1010$ 人、友人の数が $1010$ 人であるユーザーが $1009$ 人いたとする。イベントをうまく起こすことで、すべてのユーザーの友人の数が高々 $1$ 人になるように出来ることを示せ。
$4n$ 個の小石があり、それぞれの重さは $1,2,\cdots,4n$ である。各小石は $n$ 色のうちのいずれか $1$ 色で塗られており、各色で塗られている小石はちょうど $4$ 個ずつある。小石をうまく $2$ つの山に分けることで、次の $2$ つの条件をともにみたせることを示せ：
- 各山に含まれる小石の重さの合計は等しい。
- 各色で塗られている小石は、各山にちょうど $2$ 個ずつある.
ある無向グラフ $G$ に含まれるクリークの頂点数の最大値は偶数であることがわかっている。このとき頂点集合をうまく $2$ つの部分集合に分割することで、それぞれより誘導される部分グラフに含まれるクリークの頂点数の最大値を等しく出来ることを示せ。
あるコンテストで $6$ 問が出題され、どの $2$ 問をとっても、それらに両方正解した人は参加者全体の $2/5$ より多かった。また $6$ 問すべてに正解した参加者はいなかった。$5$ 問に正解した参加者が $2$ 人以上いることを示せ。
-
ここから「辺彩色」(要するに路線) や「辺の重み (コスト)」(要するに所要時間) などの手段によって様々な種の情報を乗せていくことが出来ます。 ↩︎
-
この定義は全く数学的ではありませんが、ここでは拘らないものとします。興味のある人は形式的な定義についても調べてみましょう。なお、頂点や辺に有限性を課す必要は実際にはありませんが、この記事内では基本的に無限グラフは考えないものとします。 ↩︎
-
用語の命名や定義には種々の流儀が存在します。誤解を生みそうな用法は避けるか、厳密に定義しておくべきでしょう。 ↩︎
-
用語こそ同じですが対象が違うので混同のおそれは無いでしょう。 ↩︎
-
要するに「あるグラフの一部になっているグラフ」です。 ↩︎
-
要するに「あるグラフからいくつか適当に頂点を選び、それらの間に存在する辺をすべて張って作られる部分グラフ」です。 ↩︎
-
これを歩道 (walk) と総称することもあります。この辺りの定義は流儀によって特に齟齬が生じやすいところですが、命題1.3.がhelpfulです。 ↩︎
-
始点と終点が一致する道には閉道 (closed path) や単純閉路 (simple cycle) という名称もありますが、多くはこれらも単に閉路と呼ばれます。 ↩︎
-
「ある $2$ 頂点の間に道が存在するか」は命題1.3.より同値関係となります。この関係による同値類として連結成分を定義してもよいです。 ↩︎
-
日常的で直感的な好例に迷路があります。一般的に迷路の解が一意なのは閉路を持たないことから保障されており、逆も然りなわけです。 ↩︎
-
図を描きましょう。すべての頂点間に「上下」関係が定まるわけではないことに留意してください。要するに「半順序」の関係です。 ↩︎
-
視覚的には一番「下」に描いた方が「根」や「木」の語感は自然ですが、以下の用語のように家系図をイメージすると「上」の方が良いですね。 ↩︎
-
一般に情報科学、もとい競技プログラミング方面の知識・発想は、グラフに限らず数学オリンピックの特にC分野やN分野で多く有用に働きます。同時に、逆も然りではないでしょうか。 ↩︎
-
やはり迷路を想像すると良いでしょう。「行き止まりに突き当たるたびに引き返す」という(恐らく)自然で馴染み深い戦略がまさにそれです。 ↩︎
-
この手順で得られた根から出て根へ戻る経路のことをオイラーツアー (Euler tour)と呼びます。 ↩︎
-
実際にはこれはグラフに限らず組み合わせ論における広範的な主張で、さらなる一般化も可能です。詳細はWikipediaなどを参照して下さい。 ↩︎
-
クリークについては第5章を参照して下さい。 ↩︎
-
具体的には $k_{1}=k_{2}=3$ のとき $R=6$ で良いことを主張しています。逆に $K_{3}$ を含まない $K_{5}$ の $2$ 色での彩色を考えてみてください。 ↩︎
-
単に「彩色」と言えば一般には「最適頂点彩色」を指すことが多いようです。確かに四色定理に代表されるように最も自然な対象ではあります。 ↩︎
-
後半部分については、実は $n$ を偶数に広げても $n=4$ に限られ、これには簡潔な証明が知られています：$n\geq 5$ に対し格子点を頂点とする正 $n$ 角形の存在を仮定し、面積最小の $A_{1}\cdots A_{n}$ をとると、$A_{i-1}A_{i}A_{i+1}B_{i}$ が平行四辺形となるような各 $B_{i}$ は格子点で、$B_{1}\cdots B_{n}$ は完全に含まれる正 $n$ 角形となり矛盾。 ↩︎
-
線型代数を以下しっかり使います。数学オリンピックでは大学以降の知識を援用しても何ら問題ありません。あくまで正しく使えてさえいれば… ↩︎
-
このように条件が二部グラフの場合は隣接行列を簡潔化できます。ただし上に挙げた諸演算で得られるものが少し変わるので注意して下さい。 ↩︎ ↩︎
-
正確には $n\gt k$ が必要ですが、$n=k$ のとき $x=n$ で特に全ての男女が知り合いとわかります。コーナーケースには常に注意しましょう。 ↩︎
-
固有値の匂いがしますね。その辺りの議論も実際グラフとは好相性です。これは記事の補強によってまた扱いたいと思っています。 ↩︎