グラフによるしりとりの表現

なんか思いついたので書いときます。だいぶ適当です。

グラフ理論についてはこちら↓
グラフ理論の基本

しりとりをグラフで表現する

その1

しりとりのルールを数学っぽく表します。とはいえ、あまり厳密にするのも面倒なので、ゆるっとやります。

しりとりは単語の列で$$w_1\to w_2\to w_3\to \cdots$$と続いていきますが、これを有向グラフの有向道とみなしましょう。つまり、単語を頂点とするのです。

具体的には次のようにします。しりとりに使える単語全体の集合を$W$とします。さらに$w\in W$の最初の文字を$\mathrm{init}(w)$、最後の文字を$\mathrm{ter}(w)$と表します。すると辺集合$E\subseteq W^2$を$$E:=\{(v,w)\in W^2\mid \mathrm{ter}(v)=\mathrm{init}(w)\}$$と定めれば、グラフ$(W,E)$が得られます。

しりとりにおける手番の行動は現在の単語（頂点）の（その単語を始点とする）隣接点を一つを選ぶことです。そしてすでに選ばれた単語（頂点）を選んでしまったら負けになります。必然的にその単語の隣接点がすべてすでに選ばれている場合、負けになります。つまり、しりとりの試合は有向道として得られます。

「ん」で終わる単語をいったら負けになるルールも、そのような単語（頂点）を選んだら負け、とすればよいでしょう。あるいは、「ん」で終わる単語を$W$に含めないという方法もあります。

濁点や拗音、長音については些細なことです。望むように$\int (w),\mathrm{ter}(w)$を定義すればいいのですから。

さて、一応は形ができましたが、このグラフは頂点も辺もかなり多いものになっています（頂点数が単語数で、辺数はその自乗の$\frac{1}{50}$くらい）。どうにかしてもっと単純なグラフにできないでしょうか。

その2

先ほどは単語を頂点とみなしましたが、今度は辺とみなしてみましょう。つまり、頂点集合を文字全体の集合$L$とし、辺集合を$W$、接続関数を$\psi :w\mapsto (\mathrm{init}(w),\mathrm{ter}(w))$とします。すると$G=(L,W,\psi )$がグラフになります。

このとき、手番行動は、辺を一つ選ぶことになり、しりとりの試合は小径として得られます。すでに選ばれている辺を選ぶことはできません。

このグラフは頂点数が約50、辺数が単語数になります。

その3

先ほどのグラフ$G=(L,W,\psi )$の平行な辺は特に違いがありません。なので、平行な辺の本数$\mathrm{\#}:L^2\to \mathbb{N}$を重みとする重み付きグラフ$(L,L^2)$と同一視できます。

このとき、手番行動は今いる頂点から伸びている辺を一つ選び、その重みを$1$だけ減らすことになります。すでに重みが$0$になっている辺は選べません。しりとりの試合は歩道として得られます。

このグラフは頂点数が約$50$、辺数が約$2500$になります。