1

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

116
0
$$\newcommand{init}[0]{\mathrm{init}} \newcommand{ter}[0]{\mathrm{ter}} $$

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

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

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

その1

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

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

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

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

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

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

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

その2

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

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

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

その3

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

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

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

投稿日:2023410

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

三星聯
三星聯
35
2878
主にフィボナッチ数列とパスカルの三角形の関係について書いていくと思います。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中