nononの落書き帳

不定期に、でもずっと更新したい

OMCerに向けたグラフ理論のお話(Advent Math Calendar2023)

この記事はAdvent Math Calendar2023 day16の記事です。これまでの方の記事もとても面白いですしこれからの方の記事もとても面白いのでぜひ読みましょう。

この記事は「グラフって言葉をときどき見るけど何のこと分からない」「グラフをかっこよく使って問題を解いてみたい」という人に向けた記事です。そのため、一部厳密性よりも直観的な分かりやすさを重視して書いています。また、出来る限り新規性のある記事にするように心がけていますが、他のグラフ理論に関する記事等と内容が被っていることがあります（この記事を書くときに参考にした記事やおすすめの記事等は最後にまとめてあります。勉強等にご活用ください）。また、分かりにくい部分や説明不足だと感じた点があれば遠慮なく教えてください。加筆します。

そもそもグラフって何？

まずは「グラフ」とは何かについて話します。グラフとは、すごく簡単に言うと、点とそれらを結ぶ線を抽象的に見たものです（グラフ理論ではこれらを「頂点」・「辺」と呼びます）。例えば、以下のようなものはグラフとして考えることが出来ます。

  • 鉄道の駅とそれらを結ぶ線路の関係
  • SNSにおけるフォロー関係

駅と線路の関係については駅を頂点、線路を辺とみなせますし、SNSの例ではユーザーを頂点、フォロー関係を辺とみなせばよいですね。 ここで大切なのは辺がどの頂点とどの頂点を結んでいるのかという情報です。例えば、実社会において駅がどこにあるか、線路がどのような場所を通っているのかというのは大切な情報です（観光地との距離や住宅街との位置関係、地下を走っているのかなど）。しかし、グラフにおいてはそれらは（ほとんどの場合で）気にしません。*1このような「グラフ」について調べるのがグラフ理論という分野です。

用語集

グラフ理論においては、グラフ理論独特の用語が数多く存在します。OMCの解説等でもこれらの用語はよく使われています。みなさんも使いこなせるようになりましょう。この章ではそのような用語の紹介と簡単な説明を書いています。用語についての理解がある方は読み飛ばしてもらって構いません。なお、一部競技数学ではあまり見かけない用語も紹介しています。

先ほど述べたようにグラフとは頂点(vertex)と辺(edge)からなるものです。頂点と辺がつながっていることを指す用語として接続(incident)があります。また、辺に接続している頂点を端点(endpoint)と呼びます。

似た用語として隣接(adjacent)があります。これは、ある辺によって直接むすばれている頂点の組のこと、端点に同一の頂点を持つ辺の組を指します。*2

例えば以下のグラフにおいてはこのようにいうことが出来ます。

  • 頂点 1 と辺 1 は接続している
  • 辺 3 の端点は頂点 3 と頂点 4 である
  • 頂点 2 と頂点 5 は（辺 4 によって）隣接している

図1

グラフ全体に関する性質

次に、グラフ全体を見る性質について見ていきます。重要な性質の1つ目に連結性(connectivity)があります。あるグラフが連結(connected)であるとは、そのグラフにおいてどの頂点からどの頂点も移動が可能であることです。直感的な言葉を使えば、つながっているグラフです。連結でないグラフは非連結(disconnected)であるといいます。グラフは（辺を削除することなく）いくつかの連結なグラフに分解することが出来ます。このような連結グラフのことを連結成分(component)といい、グラフにおける連結成分の個数を連結成分数(number of connected components)といいます。

辺についての用語

次に辺について見ていきます。グラフにおいては辺に情報を乗せることがよくあります。乗せることの多い情報として重み(weight)や向き(direction)があります。辺に重みをつけることで頂点間の移動におけるコストなどを考えることが出来ます。辺に重みのついたグラフを重み付きグラフ(weighted graph)といいます。また、辺に向きをつけることがあります。辺に向きのあるグラフを有向グラフ(directed graph)、向きのないグラフを無向グラフ(undirected graph) といいます。無向グラフにおいては、辺のどちらからも他方へ移動できますが、有向グラフにおいては各辺に定められた方向にのみ移動することが出来ます。

最初にあげた例を考えると、例えば駅と線路の関係は無向グラフ*3、SNSでの関係は有向グラフと考えることが出来ます。また、鉄道は所要時間などを考えれば重み付きグラフでもありますね。

ここまでは辺の持つ情報を見てきました。次は辺の性質として多重辺(multiple edges)、自己ループ(loop)、橋(bridge)を紹介します。多重辺とは、複数の辺の組であって、端点の頂点がともに等しいもののことです。なお、有向グラフにおいて a \to b の辺と b \to a の辺を多重辺とは呼びません。自己ループは端点の等しい辺のことです。特に、多重辺と自己ループを含まないグラフを単純グラフ(simple graph)と呼びます。橋とは、その辺を削除することでグラフの連結成分数の増える辺のことです。橋の重要な性質としてサイクル（後述）に含まれないというものがあります。

頂点についての用語

次は頂点について見てみましょう。頂点における重要な用語は次数(degree)です。これは頂点に接続する辺の本数を指すものです。無向グラフにおいては、ループは 2 回カウントすることに注意しましょう。また、有向グラフにおいては入次数(indegree)と出次数(outdegree)を区別して考えます。入次数はその頂点に入ってくる辺の本数、出次数はその頂点から出ていく辺の本数です。また、競技数学ではあまり見かけませんが、関節点(articulation point)も紹介します。これは、その頂点を削除することでグラフの連結成分数が増える頂点のことです。辺における橋と似たようなものです。

その他の用語

さて、次はグラフ上での移動を考えていきます。ここで大事になる用語は歩道(walk)、道(path)*4、閉路(cycle)*5です。歩道は、グラフ上で隣接する頂点への移動を繰り返すことで得られる経路のことです。このうち、同一の頂点を含まないものを道、始点と終点の頂点が同じであり、同一の辺を通らないものを閉路といいます。これらは直感的なイメージと一致するでしょう。また、歩道に含まれる辺の本数を、その歩道の長さ(length)といいます。*6また、グラフの 2 つの頂点 u,v に対して、始点が u、終点が v であるような道の長さの最小値を u,v の距離(distance)といいます。*7

さて、このあたりでこれまでに紹介した用語を簡単に復習してみましょう。問題形式にしてあるので解いてみてください。

次のグラフについて以下の問いに答えてみましょう。

  1. それぞれの頂点の次数はいくつですか。
  2. 頂点 3 から頂点 6 までの距離はいくつですか。
  3. 橋である辺をすべて挙げてください。
  4. 関節点である頂点をすべて挙げてください。

図2

解答 1. 頂点 1 から順に 2,3,2,5,2,2 です。頂点 4 での自己ループに気を付けましょう。
2. 4 です。辺 2,1,4,7 などと通ればよいですね。
3. 辺 1,4 です。例えば、辺 1 を取り除くと、頂点 2 から頂点 [tex;4] へのパスが存在しません。
4. 頂点 1,2,4 が関節点となります。

グラフの種類

次にグラフの種類についてです。グラフは性質によって様々な種類に分けられます。これらの性質を理解することでグラフを扱う問題へのハードルがぐっと下がります（私個人の意見です）。また、以下では（functional graphを除き）グラフは無向グラフとして考えます。*8

森(forest)

閉路を含まないグラフのことです。とくに連結である必要はありません。

木(tree)

森のうち、連結であるものを指します。このことからわかるように木は明らかに森です。*9 また、木においてはある頂点を根(root)とすることが出来ます。ここで大切なのは、根とする頂点にとくに制限はないという点です。しかし、根を決めてしまえばそれによって様々なものが定まります。根を定めることで決まるものとして、例えば以下のようなものがあります。

  • 葉(leaf)
    根でない頂点のうち、次数が 1 であるものを指します。
  • 深さ(depth)
    各頂点における根からの距離のことです。
  • 親、子(parent, child)
    隣接する頂点の組のうち、根に近い（深さの小さい）頂点を親、他方を子と呼びます。
  • 先祖、子孫(ancestor, descendant)
    ある頂点に対し、その頂点から根にまでのパスに含まれる頂点のことをその頂点の先祖といいます。また、その頂点を先祖にもつ頂点をその頂点の子孫と呼びます。これらは現実世界の家系図と同じです。

また、根を定めた木を根付き木(rooted tree)と呼びます。

次に木の持つ重要な性質を紹介します。例えば以下のようなものが有名でしょう。

  • 木の辺の本数は (頂点数-1) である
  • 木の辺はすべて橋である
  • 木に辺を 1 本加えると閉路ができる
  • 任意の 2 頂点間の閉路は一意に存在する。

また、この記事では紹介しませんが有向木も良い性質をたくさん持っています。「DAG*10」などと調べればたくさんの記事が見つかります。ぜひ勉強してみてください。

完全グラフ(complete graph)

すべての頂点対に対し、それらを結ぶ辺が存在するグラフのことです。例えば、3 頂点の完全グラフは三角形、4 頂点の完全グラフは四面体となります。

二部グラフ(bipartite graph)

グラフの頂点に白か黒を塗ったときに、「どの辺についても、その両端点に塗られた色が異なる」というような塗り方が存在するものです。一般にn部グラフへの拡張を考えることもできます。二部グラフを題材とした有名な議題としてマッチングがあります。面白い定理等がたくさんあるので調べてみましょう。

完全二部グラフ(complete bipartite graph)

二部グラフのうち、「任意の頂点対について、それらが異なるグループに属するならばその間に辺が存在する」という条件を満たすものです。二部グラフに対して、グラフが二部グラフである限り辺を増やし続けることで得られます。

オイラーグラフ(Eulerian graph)

ある頂点から、すべての辺をちょうど1度だけ用いて元の頂点に戻る閉路が存在するグラフのことです。直感的な表現をすれば一筆書きをして元の場所に戻ってくることの可能なグラフです。グラフがオイラーグラフであることはすべての頂点の次数が偶数であることと同値です（証明は高校数学の美しい物語に載っているため割愛します）。また、閉路ではないが一筆書きが可能なグラフを準オイラーグラフ(semi-Eulerian graph)といい、グラフが準オイラーグラフであることの同値条件は次数が奇数の頂点の個数がちょうど2個であることです。

平面グラフ(plane graph)

平面の上に辺を交差させることなく書くことの出来るグラフです。平面でないグラフのうち、頂点数が最小のものは頂点数が 5 の完全グラフです。

正則グラフ(regular graph)

すべての頂点の次数が等しいグラフです。特に、その次数を k としてk-正則グラフ(k-regular graph)と呼ぶことがあります。

functional graph

有向グラフであって、どの頂点の出次数もちょうど 1 であるようなものです。OMCの問題としては、S=\lbrace 1, \dots, n \rbraceとして関数 f:S \to S を考える問題で有効に使えることが多いです。functional graphの性質としては以下のようなものがあります。

  • 連結成分数はサイクルの数と等しい。
  • すべての頂点の入次数が 1 であるとき、グラフはいくつかのサイクルに分解できる。

グラフを使って問題を解くときに考えること

まず、グラフを用いて問題を解く前に覚えておいてほしいことを伝えます。それは、「ほとんどの問題はグラフの用語に置き換えてからが本質である」ということです。グラフ理論と聞くと難しい数え上げ問題をサクッと解決してくれる素晴らしい飛び道具に見えるかもしれませんが、そんなことはありません。もちろん、とても強い定理や性質もありますが、そのような定理を使うだけで解ける問題は稀です。また、ほとんどの問題はグラフ理論の知識がなくても解けます。

では、なんのためにグラフを使うのでしょうか。これは人によって様々な考えがあるかもしれませんが、私は「問題の見通しを良くする」ために使っていることが多いです。問題をグラフ理論の用語に置き換えることで全体像が見えやすくなり、問題を解く手掛かりになります。また、分からないことがあったときに検索がしやすくなります。統一的な用語を用いることで、先人が残してきた様々な定理をたくさん学ぶことが出来ます。

ただ、グラフ理論の強い定理等を知っていると簡単に解ける問題があるのも事実です。以下では実際の問題を扱いながら「問題文をグラフの用語に置き換える練習」と「強い飛び道具の紹介」をしていきます。

実際に問題を解いてみよう

さて、ついに問題演習です。以下ではOMCの過去問を用いて問題を解いていきます。問題に対するネタバレを含むので注意してください。また、すべての問題に対して解答は載せておらず、グラフ的な見方をするまでのヒント・私が解いたときに考えたことや問題に対する一言コメント、類題の紹介を載せています。最終的な答えにたどり着くための計算部分はOMCの公式解説等を見てください。なお、これらは折り畳みとして載せているため、スクロールするだけではこれらが見えることはないので安心してください。

第1問

5 人の生徒がおり、それぞれが一斉に自分以外の 2 人を指差したとき、どの 2 人の生徒についても互いに指差しているか、互いに指差していないかのどちらかでした。このような指差し方は何通りありますか。ただし、それぞれの生徒は区別します。

（出典：OMC173 B）

ヒント1 まず、何を頂点、何を辺にすればよいか考えてみましょう。また、辺の有向無向や重みについてもどのようにすればよいか考えてみましょう。
ヒント2 人を頂点、指差しの関係を辺とするのが良いですね。また、ある人が別の人を指差したとき、逆方向にも指差しが行われていることから無向グラフと考えることが出来ます。
コメント 人が指差しているため有向グラフに見えてしまうことがあるかもしれませんが、「互いに指差している」という条件がうまく効いてきます。ところで、人は指差さないほうがいいらしいです。

第2問

4 つの都市 A,B,C,D があり， はじめは AB,BC,CD,DA 間にそれぞれ道路が 1 本ずつあります。 ここへ、以下の操作を 10^9+10 回繰り返します。

  • 異なる 2 都市を選び、それらを双方向に結ぶ道路を新たに 1 本建設する。

10^9+10 回の操作の組み合わせは 6^{10^9+10} 通りありますが、このうち得られた道路網について、すべての道路をちょうど 1 回ずつ通るような道順が存在しないような操作の組み合わせは何通りありますか？ 素数 10^9+7 で割った余りを求めてください。

ただし、道路は交差しないものとし、途中で引き返すことはできないものとします。 （出典：OMC073 D）

ヒント1 お分かりの通り都市を頂点、道路を辺として見てあげたら良いでしょう。条件を満たさないグラフはどのようなグラフでしょうか。
ヒント2 条件を満たさないグラフはオイラーグラフ（または準オイラーグラフ）ですね。ここでグラフの有名な性質として「グラフにおける次数和が偶数」というものを紹介します。これを考えればもとめるグラフの条件はどのように言えるでしょうか。
ヒント3 一筆書きが出来ることは、次数が奇数の頂点が 2 個以下であることと同値なのですべての頂点の次数が奇数になるものを考えればよいです。
コメント 翔子さんのユーザー解説もきれいです。ぜひ読みましょう。

第3問

以下の条件をみたす，長さ7の数列 a_1,a_2,...,a_7 はいくつありますか？

  • a_1,a_2,...,a_7 はすべて1以上7以下の整数である。
  • a_{a_{1}}=a_{a_{2}}=a_{a_{3}}=a_{a_{4}}=a_{a_{5}}=a_{a_{6}}=a_{a_{7}}

（出典：MathPower杯2022 F）

ヒント1 この問題はこれまでの問題よりもグラフとして見るのが難しいですね。まずは具体的な a をいくつか考えてみましょう。そして、 i \to a_i と辺を張ったグラフを考えてみましょう。どのような特徴が見えてくるでしょうか。
ヒント2 このグラフはfunctional graphですね。そのため、始点が決まれば 2 つ先の頂点も定まります。この頂点を固定して考えてみましょう。
ヒント3 固定した頂点から伸びる辺は自己ループである必要がありますね。この辺を無視して残りの辺からなる根付き木を考えてみましょう。
コメント この問題のようにfunctional graphを考えることでうまくいく問題がたくさんあります。類題として以下を紹介します。

第4問

ある国には 3000 個の都市があり、それぞれの都市に，都市 1, \dots, 3000 と番号が振られています。これらの都市の間に、相異なる 2 都市間を結ぶ双方向に行き来可能な道を何本か引く方法であって、以下の条件を満たすものが M 通りあるとします。

  • 任意の都市から任意の別の都市へ、必要ならばいくつかの都市を経由して、引かれている道だけを使って必ずたどり着くことができ、また同じ都市を 2 回以上通らない場合、その道順はちょうど 1 つ存在する。
  • 都市 1, \dots,1000 を端点に持つ道は、それぞれ高々 1 本である。
  • 都市 1001, \dots, 2000 を端点に持つ道は、それぞれ高々 2 本である。
  • 都市 2001, \dots, 3000 を端点に持つ道は、それぞれ高々 3 本である。

\displaystyle\frac{M}{3000!}=\displaystyle\frac{p}{q}をみたす互いに素な正整数 p,q に対して、p \times q を3000で割った余りを答えてください。

（出典：OMC186 F）

ヒント1 何を頂点・辺とすればよいかは分かるでしょう。1つ目の条件はグラフがどのようなものであることと同値でしょうか。
ヒント2 1つ目の条件はグラフが木であることと同値ですね。これは「任意の都市から任意の別の都市へ必ずたどり着くことができる」「その道順はちょうど 1 つ存在する」という部分を見ればよいです。では、次にこれを頂点 3000 を根とした根付き木として見て、葉を取り除いていくことを考えます。どのような順番で取り除けばよいでしょうか。
ヒント3 次数が 1 である頂点の取り除き方として以下の方法を考えます。

  • グラフの葉である頂点のうち番号が最小であるものおよびそれに繋がる辺を取り除く．

これは公式解説に書かれている操作です。この操作から何が分かるでしょうか。

ヒント4 この操作の背景（というか操作そのものですが）としてPrüfer codeを紹介します（細かい内容については需要がありそうなら記事を書きます）。これは、簡単に言うと N 頂点のラベル付き木から生成される長さ N-2 の数列のことで、この数列と木が一対一対応します。この事実を知っていれば簡単な議論のみで答えにたどり着くことが出来ます。
コメント この日の4eには予定があったため出れませんでした。悲しい。

おまけのおはなし

ここまでは、OMCの過去問を中心としたグラフのお話をしてきました。ここから先は、そうではない話、私が勉強しているグラフ理論の話をします。書こうと思っていましたが思ったより記事が長くなってしまったので次回以降にでも書きます。

と言いつつこれで終わってしまっても寂しいので最後に私が面白いと思った問題の紹介をします。ノーヒントで解けたらすごいと思います。

単純連結無向グラフ G（すなわち、G は多重辺、自己ループを持たない連結無向グラフである）について、その頂点数を n、最小次数を d とします。このとき、G は長さ min(n-1,2d) 以上のパスを持つことを示してください。（出典：Graph Theory/Ch1）

最小次数とは G において、頂点 i の次数を d_i とします。このとき d=min(d_1,d_2,...,d_n) です。

ヒント1 G の最長のパス P について、その長さ k を min(n-1,2d) 未満であるとしてみましょう。矛盾が生じます。
ヒント2 k \lt n-1 であるので G の頂点のうち P に含まれない頂点があります。また、k \lt 2d からは何が分かるでしょうか。
ヒント3 k \lt 2d から P 内のすべての頂点を含むサイクルが存在することがわかります。示してみましょう。
ヒント4 P の端点と隣接する頂点はどのような頂点である必要があるでしょうか。P の定義を思い出してみましょう。
略解 記号はヒントで使用したものを用いています。また、頂点数 1 のグラフなどの特殊なケースについての議論は省略しています（このようなグラフについても主張は成り立ちます）。

P=(p_0,...,p_k) とします。また、P に含まれない頂点 v について v が p_i(1 \leq i \lt k) と隣接しているとしても一般性を失いません（k \lt n-1）。次に、ヒント3にあるサイクルの存在を示します。p_0 と p_k が隣接するときは明らかなのでそうでないとしましょう。P の最長性から p_0 と p_k はサイクルに含まれない頂点には隣接しません。そのため p_0 と p_k はともに p_1,...,p_{k-1} のうち少なくとも d 個に隣接します。さらに p_0 は p_1 と、p_k は p_{k-1} と隣接します。k \lt 2d と合わせて、ある 1 \leq j \lt k-1 が存在して p_0 は p_{j+1} と、p_k は p_j と隣接することがわかります（鳩ノ巣原理）。よってサイクルの存在が示せました。このサイクルを頂点 p_i と p_{i+1} の間の辺を無視し、v とつなぐことで長さ k+1 のパスを得ることが出来ました。これによって主張が示されます。

コメント この問題はグラフ理論のゼミで私が担当した問題です。サイクルを見つける議論が難しいですね。

最後に

今回の記事では用語を中心にグラフ理論の基本について書いてみました。今回の記事には載せきれなかったことでも大切なことはたくさんあるので、ぜひこの下に載せある記事も読んでみてください。また、次の記事では今回は書けなかった純粋数学に近いグラフ理論のお話についても書きたいですね。長くなってしまいましたがここまで読んでいただきありがとうございました。それではまた次の記事でお会いしましょう！

参考文献・おすすめの記事等の紹介

*1:これらを気にして議論を行うこともありますが、競技数学においては気にしないと考えて問題ないでしょう。

*2:どちらも同じ語なので文脈から読み取ることが必要です。

*3:鉄道は移動の方向が決まっていますが反対方面のものも存在するので無向グラフと考えられます。これを有向グラフとみなすこともあるでしょう

*4:カタカナで「パス」と表記されることもあります。

*5:カタカナで「サイクル」と表記されることもあります。

*6:重み付きグラフにおいては通った辺の重みの和とすることが多いです。

*7:存在しない場合は \infty とすることが多いです。

*8:有向グラフに対しても定義できますがここでは省略します。

*9:有名な言い回しです。明日クラスメイトにも教えてあげましょう。

*10:directed acyclic graphの略です。