木
一本足りないのではない。一本多くないのだ。
〜 木 について、ある辺の遺失物係
木(き、tree)とは、グラフ理論において、辺を一本だけなくしたまま、それを取り戻すことを拒んでいるグラフのことである。頂点が n 個ある木には、辺がちょうど n−1 本ある。残りの一本がどこへ行ったのかは、木自身も覚えていない。
頂点が n 個あるのに辺が n−1 本しかないことは、木の定義の一部として、どの教科書にも書かれている。足りない一本を探さないのも、教科書の決まりである。
木の外から辺を一本持ってきてどこか二つの頂点をつなぐと、グラフの中に閉路がちょうど一つできる。これはどの二頂点を選んでも変わらない。数学者のあいだでは、この閉路は「帰ってきた辺に沿って、木がぐるぐる回り始めた跡」として扱われ、回り始めた木は二度と木には戻らない。木が辺を取り戻さないのは、回るのが嫌いだからである。
なくした辺の候補は、頂点のあいだでまだつながっていない組の数だけある。頂点が4個の木なら、組は全部で6、つながっているのが3なので、候補は3本になる。このうちどれが本当になくした一本なのかを決める方法は、まだ見つかっていない。どれを選んでも閉路が一つできるので、確かめるたびに木が一本ずつ失われるからである。

1918年、ハインツ・プリューファーは、番号を振った頂点を持つ木を、長さ n−2 の数の並び一つと必ず一対一に対応させる方法を示した。この並びはプリューファー列と呼ばれ、辺の遺失物係では、そのまま遺失届の受付番号として使われている。
受付番号の並べ方は全部で n の n−2 乗あり、番号を振った頂点 n 個の木の数と一致する。これはケイリーの公式として知られている。頂点が5個なら木は125本で、遺失届も125通、受付番号は三桁になる。頂点が2個なら木は1本、受付番号の長さは0で、白紙の届けが一通だけ保管されている。
頂点が1個の場合、辺は0本で、なくした辺は「−0本」とも「1本」とも数えられる。ケイリーの公式によれば木は 1 の −1 乗で1本、受付番号の長さは −1 である。長さが −1 の番号を渡すことはできないため、この場合に限り、遺失物係のほうが木に一桁借りている[1]。
次数が1の頂点を葉という。頂点が2個以上ある木には、葉が必ず2枚以上ある。葉は片方の手だけを木の内側につなぎ、もう片方を外に出して、なくした辺を探している頂点だと説明される。
葉がちょうど2枚しかない木は道と呼ばれる。道の両端の葉は互いに反対の方角を探しているので、同じ辺を二度見つけることが無い。
郵便番号の七桁目は、ほとんど誰も覚えていない。
葉をすべて取り除いても、残りは木のままである。これを繰り返すと、最後には頂点が1個か、辺で結ばれた2個が残る。これを木の中心という。中心は辺を探しに行かない。一番奥にいるので、外に何があるのかを知らないからである。
木の頂点を一つ選んで根と呼ぶと、根付き木になる。どの頂点を根にしてもよいが、選ばれた頂点はその日から、辺をなくした日のことを思い出そうとし始める。根付き木の図で根がいちばん上に描かれるのは、思い出そうとする頂点が上を向く癖を持つからである[要出典]。
木がいくつか、互いにつながらずに並んだものを森という。森は木の数だけ辺をなくしている。
一方、数学に林は無い。二本の木をそれぞれ一つずつの頂点で辺一本につなぐと、閉路はできず、全体が一本の木になる。「木」を二つ並べたものは、並べた瞬間に一つの木に数え直されるので、林は存在できない。このとき使った辺は、二本の木が一本ずつなくしていた辺のうちの片方だと考えられており、もう片方は依然として行方が分からない。
この理屈によると、森は「まだ林になっていない木の集まり」であり、漢字の成り立ちとは順番が逆である。
1847年、グスタフ・キルヒホフは電気回路の計算の中で、回路から辺を外していって閉路の無い部分を取り出す方法を使った。これが全域木の始まりとされる。キルヒホフが外した辺は回路のほうに残ったので、このとき辺はまだ一本もなくなっていない。
「木」という名前を付けたのは、1857年のアーサー・ケイリーである。名付けられた時点で、木は辺を一本なくしていた。名前が先か、なくしたのが先かについて、ケイリーは何も書き残していない。
この記事には本文の節が7つあり、節と節のあいだの区切りは6つである。したがって、この記事は木である。
書き手は記事の下書きで、本文の中に閉路の項目へのリンクを一本置いた。読み返すと、記事の最後まで読んだ読者が冒頭の引用に戻っていたので、そのリンクは外した。外したリンクは、いまも見つかっていない。
- ↑ この一桁は返済の見込みが無いまま、毎年の決算で繰り越されている。繰り越しの記録も一桁ぶん短い。