数理解析研究所講究録 1325 巻 2003 年 21-26

21
短絡除去可能な順序なし二分木における最小被覆木問題に対する一考察
牧山 幸史 (Kouji MAKIYAMA), 安浦 寛人 (Hiroto YASUURA)

九州大学大学院システム情報科学府情報工学部門

Department of Computer Science and Communication Engineering Graduate School of Information
Science and Electrical Engineering, Kyushu University{makiyama, yasuura}$c.csce.kyushu-u.ac. jP

1

はじめに

定義 22(二分木の等価) 二分木の等価を次のように定義する.

現在, 我々はプログラマブルコントローラと呼ばれる制御用機器に対する専用回路のアーキテクチャを決定する際に現れた最小評価木問題という最適化問題に対して考察を行っている. これは, ノード数 の全ての二分木を被覆するような二分木の中で, ノード数が最小のものを求めよというものである. 最小評価木問題に対する正確な定義は本稿の第 2 節問題 25 に示してある.
我々は, この最小評価木問題に対して, 有効と考えら(i) nil は nil のみと等価である.
(i) nil でない二分木と $t(b_{3}, b_{4})$ が等価であるとが等価であり, かつが等価であるときであり, そのときに限る.

とは,

$n$

れるアルゴリズムを発見し, それによって求められた二分木が, ノード数 $n$ の全ての二分木を被覆するという性質を持つことを証明した [1]. L かしながら, このアルゴリズムによって求められた二分木が, ノード数最小という性質を満たしているかどうかについては未解決である.
最小評価木問題は, 二分木の被覆という概念を(i) 単純に考えたときの被覆条件(ii) 順序なし二分木に対応する被覆条件(iii) 短絡除去可能という性質を表すための条件の三つに分けることで, 最小被覆木問題 (第 3 節問題
32) を短絡除去可能な順序なし二分木に対して考えたものであるとみなすことができる.
本稿では, この観点からと$b_{1}$$t(b_{1}, b_{2})$$b_{3}$$b_{4}$$b_{2}$が等価てあることを $b_{1}=b_{2}$ と表二つの二分木と表す.
す. また, 等価でないことを$b_{1},$$b_{2}$$b_{1}\neq b_{2}$

定義 23(二分木のノード数) 二分木 のノード数をと表すことにして, 二分木のノード数を次のように定義
$b$

$|b|$

する.

0, if
, if $b=t(b_{1}, b_{2})$ .
$b=\mathrm{n}\mathrm{i}1$$|b|=\{$$|b_{1}|+|b_{2}|+1$

全ての二分木の集合を $B$ とする. また. ノード数と表す. このとき,全ての二分木の集合を$n$の$B_{n}$$B=\cup B:i=0\infty$,$i\neq j\Rightarrow B_{:}\cap B_{j}=\emptyset$が成り立つ.

1. 被覆条件として (i) のみを考慮した場合

2. 被覆条件として (i) と $(ii)$ を考えた場合という二つの緩和問題に対して考察を行った.
本稿は以下のように構成される. 第 2 節では最小評価
木問題に関する諸定義を行う. 第 3 節では上記 1. 2 の定義 24(二分木の被覆) 二分木

が被覆
を二分木
と表すことにして, 二分木の被覆をすることを
次のように定義する.
$b_{1}$$b_{2}$$b_{1}\subseteq b_{2}$$b_{1}\subseteq b_{2}\ovalbox{\tt\small REJECT}$

それぞれの緩和問題について解法アルゴリズムを提示し,その正当性に関する証明及ひ考察を行う. 第 4 節でまとめと今後の課題を述べる.

$(b_{1}=\mathrm{n}\mathrm{i}\mathrm{l})$$\vee((b_{1}\neq \mathrm{n}\mathrm{i}\mathrm{l})\Lambda(b_{2}\neq \mathrm{n}\mathrm{i}\mathrm{l})$$\Lambda(((b_{11}\subseteq b_{21})\Lambda(b_{12}\subseteq b_{22}))$$\vee((b_{11}\underline{\mathrm{C}}b_{22})\Lambda(b_{12}\subseteq b_{21}))$2

諸定義$\vee(b_{1}\subseteq b_{21})\vee(b_{1}\subseteq b_{22})))$

定義 21(二分木) 次のように二分木を定義する.
(i) 一つの頂点のみは, その頂点を根とする二分木である.

(i) 二つの二分木があって, それらの根を新しい頂点の下に繋いだものは, その頂点を根とする二分木で

ただし,以上により得られるもののみが二分木である.

ここで, 次のように記号を定める.

nil

:

頂点のみ

$t(b_{1}, b_{2})$:二分木$b_{1},$

nil でない二分木は必ず意して欲しい.

$b_{2}$

を新しい頂点に繋いだもの$t(b_{1}, b_{2})$の形で表されることに注$b_{2}$

は nil でな$\mathrm{A}\mathrm{a}$とき, それぞれ $t(b_{11}, b_{12})$ ,と表されるとする.

問題 25(最小評価木問題) すべての自然数 $n$ に対して,$Z_{n}=\{z\in B|\forall b\in B_{n}(b\subseteq z)\}$ある.
$(\overline{\dot{\mathrm{m}}})$$b_{1},$$t(b_{21}, b_{22})$

とおく.

このとき, 任意の自然数 $n$ に対して,$Z_{n}^{*}=\{z\in Z_{n}|\forall z’\in Z_{n}(|z|\leq|z^{l}|)\}$

を求めよ.

22
3

緩和問題

2. $i=n$ ならば終了.

本節では, 被覆条件を緩和して得られる緩和問題について考察する. 被覆条件は大きく次の 3 つに分けられる.

(i)$(b_{11}\subseteq b_{21})\Lambda(b_{12}\underline{\Xi}b_{22})$$\circ 0(b_{11}\subseteq b_{22})\Lambda(b_{12}\subseteq b_{21})$$(\ddot{\dot{\mathrm{m}}})(b_{1}\subseteq b_{21})\vee(b_{1}\subseteq b_{22})$

条件 (i) は普通に考えたときの被覆条件であり, (i) は順
序なし二分木に対応した拡張である. 条件 (i) は短絡除去可能という性質を言い表したものである.
これらの条件のうち, 3.1 節では (i) のみを考慮した場
合, 32 節では (i) と (可) を合わせた場合のそれぞれについて求解アルゴリズ
ついて考察する.

31を示し,$\text{ム}$アルゴリズ$\text{ム}$の正当性に被覆条件として (i) のみを採用したものを
すなわち,$b_{1}\subseteq jb_{2}\mathrm{g}\mathrm{e}(b_{1}=\mathrm{n}\mathrm{i}\mathrm{l})$$\subseteq_{\mathrm{i}}$と表す.

ならば 3. へ進む.

3. $x[i]arrow t(x[i-1], x[i-1]),$ $iarrow i+1,\mathit{2}$ . へ戻る.
出力 :$x[n]$

以下, 本小節はアルゴリズム 1 の正当性の証明に費される. 補題 33\sim 定理 37 は, 完全二分木が問題 32 の解となること, 定理 38\sim 定理 314 は, 解がそれだけであることの証明である.

補題 33 任意の $n(=1,2,3, \ldots)$ に対して,$\forall b\in B_{n-1}(\exists b’\in B_{n}(b\subseteq_{\mathrm{i}}b’))$が成り立つ.
(証明)

被覆条件 (i) のみを考慮した場合$i\neq n$

任意の $b\in B$ }こ対して, $b’=t$ ( ,nil) をとれば,である. したがって証明さ$b$$|b’|=|b|+1$ であり,れた. (証明終)$b\subseteq_{\mathrm{i}}b’$

補題 3.4 任意の $n(=1,2,3, \ldots)$ に対して,$m\leq n\Rightarrow\forall b\in B_{n-m}(\exists b’\in B_{n}(b\subseteq_{\mathrm{i}}b’))$$\vee((b_{1}\neq \mathrm{n}\mathrm{i}\mathrm{l})\Lambda(b_{2}\neq \mathrm{n}\mathrm{i}\mathrm{l})$(1)が成り立つ.

$\Lambda(b_{11}\subseteq_{\mathrm{i}}b_{21})\Lambda(b_{12}\subseteq_{\mathrm{i}}b_{22}))$とする. このとき,は順序関係である. すなわち, 次の命題 3.1 が成り立つ.
$\subseteq_{\mathrm{i}}$(証明) $m$ における数学的帰納法により証明する. $m=0$のときは命題 31 より明らか. $m<k$ ならば式 (1) が成り立つと仮定する. このとき, $m=k$ ならば, 補題 33が成り立つよより, 任意の b\in B、-m に対して
うな $b’\in B_{n-(m-1)}$ が存在する. 帰納法の仮定より,となるような $b”\in Bn$ が存在する. した{こはとなるような $b”\in Bn$ ががって, 命題 3.1 より存在する. 以上により証明された. (証明終)$b\subseteq_{\mathrm{i}}b’$

命題 31 任意の

$b_{1},$$b_{2}\in B$に対して,$b_{1}=b_{2}\Rightarrow b_{1}\subseteq_{\mathrm{i}}b_{2}$

$b’$

,

$b’\subseteq_{\mathrm{i}}b’’$$b\subseteq_{\mathrm{i}}b’’$$(b_{1}\subseteq_{\mathrm{i}}b_{2})\Lambda(b_{2}\subseteq_{\mathrm{i}}b_{1})\Rightarrow b_{1}=b_{2}$,$(b_{1}\subseteq_{\mathrm{i}}b_{2})\Lambda(b_{2}\subseteq_{\mathrm{i}}b_{3})\Rightarrow b_{1}\subseteq_{\mathrm{i}}b_{3}$補題 35 任意の $n(=0,1,2, \ldots)$ に対して,が成り立つ.
$(x\in X_{n})\Lambda(m\leq n)\Rightarrow\forall b\in B_{m}(b\subseteq_{\mathrm{i}}x)$(証明略)

問題 32(最小被覆木問題) すべての $n(=0,1,2, \ldots)$ に対して,が成り立つ.
(証明) $x\in X_{n}$ とする. 補題 3.4 より, $m\leq n$ ならが成り立つようなば, 任意の $b\in B_{m}$ に対して,$b’\in B_{n}$ が存在する.
の定義より,
が成り立が成り立つ. したがって証明された. (証つので,明終)$b\subseteq_{\mathrm{i}}b’$$X_{n}=\{x\in B|\forall b\in B_{n}(b\subseteq_{\mathrm{i}}x)\}$

このとき, 任意の $n(=0,1,2, \ldots)$ に対して,

とおく.

$X_{n}^{*}=\{x^{*}\in X_{n}|\forall x\in X_{n}(|x^{*}|\leq|x|)\}$を求めよ.
$B_{0}=$$X_{n}$$b’\subseteq_{\mathrm{i}}x$$b\subseteq_{\mathrm{i}}x$

定理 36 任意の $n(=1,2,3, \ldots)$ に対して,$(x\in X_{n-1})\Lambda(x’=t(x, x))\Rightarrow x’\in X_{n}${nil} より, 明らかに,$X_{0}=B,$$X_{0}^{*}=B_{0}=$が成り立つ.

{nil}

である.

問題 32 の解が完全二分木となることは容易に予想できる. 完全二分木が何であるかについては本稿では特に説明しないが, 次のアルゴリズム 1 は問題 32 の求解ア
ルゴリズムである. したがって, これによって得られるものは完全二分木である.
アルゴリズム 1 人力 :(証明) $(x\in X_{n-1})\Lambda(x’=t(x, x))$ が成り立つとする. 任意の $b\in B_{n}$ は $b=t(b_{1}, b_{2})$ と表すことができ,$|b_{2}|<n$ が成り立つので, 補題 35 より,
このときが成り立つ. したがって,$|b_{1}|,$$b_{1}\subseteq_{\mathrm{i}}x,$$b_{2}\subseteq_{\mathrm{i}}x$$b=t(b_{1}, b_{2})\subseteq_{\mathrm{i}}t(x, x)=x’$

かったので,$x’\in X_{n}$が成り立つ.

定理 37 任意の $n(=1,2,3, \ldots)$ に対して,$n$$x^{*}\in X_{n-1}^{*}\Rightarrow t(x^{*}, x^{*})\in X_{n}^{*}$

変数 :

:

整数
$x[i]$ , 二分木の配列$i$,

1. $iarrow 1,$$x[0]arrow \mathrm{n}\mathrm{i}1$.

$b$が示された. (証明終)が成り立$-\supset$

.

は任意でよ

23
(証明) $x^{*}\in X_{n-1}^{*}$ とすると, 定理 36 より, $t(x^{*}, x^{*})\in$である. このとき, $t(x^{*}, x^{*})\not\in X_{n}^{*}$ が成り立つと仮定
すると, ある $x’\in X_{n}$ が存在して, $|x’|<|t(x^{*}, x^{*})|$ となる. これより, $x’=t(x_{1}’, x_{2}’)$ とおくと, $|x_{1}’|+|x_{2}’|<$$X_{n}$

が成り立つので,のどちらか (もしくは両方) が成り立っていなくてはならな
い. 一方, 任意の $b\in B_{n-1}$ に対して $b’=t$ ( , nil) をとると,\in B、であるので, $x’\in X_{n}$ より, 任意の$b\in B_{n-1}$ に対して,が成り立っていなければならない. これは, $x_{1}’\in X_{n-1}$ を意味している. した.
がって, $|x_{1}’|\geq|x^{*}|$ である. しかしながら, 同様にして.
$x_{2}’\in X_{n-1}$ が言えるので,$|x_{2}’|\geq|x^{*}|$ も成り立たなくてはならず, $|x_{1}’|+|x_{2}’|\geq 2|x^{*}|$ が成り立ってしまう. これは矛盾である. したがって, $t(x^{*}, x^{*})\in X_{n}^{*}$ が成り立つ.
(証明終)$2|x^{*}|$$|x_{1}’|<|x^{*}|,$$|x_{2}’|<|x^{*}|$

$b$

$b’$

$b\subseteq_{\mathrm{i}}x_{1}’$対してが成り立つような
また, 任意の a2に対してうなが存在する. ここで,
$a_{1}^{*}\underline{\mathrm{H}}_{\mathrm{i}}a_{1}$$\in A_{2}$$a_{2}^{*}\in A_{2}$( $a1$ , a2)が存在し,$a_{1}^{*}\in A_{1}$a2 が成り立っよ$a_{2}^{*}\subseteq_{\mathrm{i}}$$A=\{a\in B|b\underline{\Xi}_{\mathrm{i}}$(a2),, a2) $|a_{1}\in A_{1}$ , a2
} {こ
注意して,
とおくと, 任意の $a\in A$ に対して,が成り立つことがわかる. したがって,$n=k$ となる任意のの組に対して定理が成り立っ.
以上により証明された. (証明終)$a,$$b’\subseteq_{\mathrm{i}}a\}=\{t$$a_{1})\Lambda$(a2)$b_{2}’\subseteq_{\mathrm{i}}$

$\}$

$=$

{

$|(b_{1}\subseteq_{\mathrm{i}}a_{1})\Lambda$$(b_{1}’\subseteq_{\mathrm{i}}$$b_{2}\underline{\mathrm{r}}_{\mathrm{i}}$$t(a_{1}$$\in A_{2}$$a^{*}=t(a_{1}^{*}, a_{2}^{*})$$a^{*}\subseteq_{\mathrm{i}}a$$b,$ $b’$

系 310

でない任意の有限部分集合 $P\subset B$ に対して.

$\emptyset$$C=\{c\in B|\forall p\in P(p\subseteq_{\mathrm{i}}c)\}$

とおくと,$\exists!\mathrm{c}^{*}\in C(\forall \mathrm{c}\in C(c^{*}\subseteq_{\mathrm{i}}c))$

定理 38 任意の$b’\in B$

$b,$

に対して,

(2)

$b\underline{\mathrm{H}}_{\mathrm{i}}b’\Rightarrow|b|\leq|b’|$が成り立つ.

が成り立つ.
(証明)$c^{*}$が存在することは, 定理 39 より明らかなので, それが唯一であることを示す.
が二つ存在したとして, もう一方をと表すことにすると, 定義より$c^{*}$(証明)のノード数
における数学的帰納法により証明する. $|b|=0$ のときは明らか. $|b|<k$ となる全てのに対して式 (2) が成り立つと仮定する. このとき, $|b|=k$ となる任意の に対して,とすると,なので, $b=t(b_{1}, b_{2}),$ $b’=t(b_{1}’, b_{2}’)$ とおけば,かつが成り立つ. 帰納法の仮定より, $|b_{1}|\leq|b_{1}’|$ かつ $|b_{2}|\leq|b_{2}’|$ が成り立つので,$|b|=|b_{1}|+|b_{2}|+1\leq|b_{\acute{1}}|+|b_{\acute{2}}|+1=|b’|$ が成り立つ.
以上により証明された. (証明終)
$b$

$|b|$

$b$

$b$

定理 39 任意の♂が成り立つ. このとき,
称性により, 結局 $c^{*}=c^{**}$ となる. したがって,一である. (証明終)♂

$\subseteq_{\mathrm{i}}c^{**},$$c^{**}\subseteq_{\mathrm{i}}$$\subseteq_{\mathrm{i}}$の反対は唯$c^{\mathrm{a}}$$b\subseteq_{\mathrm{i}}b’$$b’\neq \mathrm{n}\mathrm{i}\mathrm{l}$$b_{1}\subseteq_{\mathrm{i}}b_{1}’$$c^{**}$

補題 311 任意の$b,$$b’\in B$に対して,$b_{2}\subseteq_{\mathrm{i}}b_{2}’$$b,$$b’\in B$が成り立つ.
(証明)のノード数
における数学的帰納法により証となり, 式 (3) が成明する. $|b|=0$ のとき,り立つのは明らか. $|b|<k$ のとき, 式 (3) が成り立つと$b=t(b_{1}, b_{2})$ ,仮定する. このとき, $|b|=|b’|=k,$
とすると,
が同時に成
り立っていなければならない. 定理 38 から,$|b_{2}|\leq|b_{2}’|$ が成り立つことと,$|b|=|b’|=k$ であること
より,が成り立つ. したがって,が成り立ち, $b=b’$
帰納法の . 定より,が成り立つ. 以上により証明された. (証明終)
$b$

に対して,

(3)

$(|b|=|b’|)\Lambda(b\subseteq_{\mathrm{i}}b’)\Rightarrow b=b’$$|b|$$b=b’=\mathrm{n}\mathrm{i}\mathrm{l}$$A=\{a\in B|b\subseteq_{\mathrm{i}}a, b’\subseteq_{\mathrm{i}}a\}$$b\subseteq_{\mathrm{i}}b’,$

とおくと,$b’=t(b_{\acute{1}}, b_{\acute{2}})$$b_{1}\subseteq_{\mathrm{i}}b_{\acute{1}},$$b_{2}\subseteq_{\mathrm{i}}b_{\acute{2}}$$|b_{1}|\leq|b_{\acute{1}}|$$\exists!a^{\mathrm{r}}\in A(\forall a\in A(a^{*}\subseteq_{\mathrm{i}}a))$$|b_{1}|=|b_{\acute{1}}|,$

が成り立つ.

$\text{仮}$(証明) 任意の $a\in A$ に対してが成り立っようなが存在したとすると, 定理 38 より, 全ての $a\in A$$a^{*}\subseteq_{\mathrm{i}}a$$a^{*}$に対して $|a^{*}|\leq|a|$ が成り立っていなくてはならない. したがって, 全ての $a\in A$ に対して $|a^{*}|\leq|a|$ が成り立っとしてよい. また, このときは唯一である. なぜなら, 任意の $a\in A$ に対してが成り立っようなが二つあったとすると,が順序関係である (したがって反対称律が成り立つ) ことにより, その二っは一致したものとなってしまうからである.
$|b|,$の最大値, $n= \max(|b|, |b’|)$ における数学的帰納法により証明する. $n=0$ のとき, $|b|=|b’|=0$ より $b=b’$ =n 垣である. このとき, $A=B$ となるので,をとれば, 任意の $a\in A$ に対してが成り立つ. $n<k$ となる任意のの組に対して, 定理が成り立つと仮定する. このとき, $n=k$ となる任意の$|b_{2}|=|b_{\acute{2}}|$$b_{1}=b_{\acute{1}},$$b_{2}=b_{\acute{2}}$定理 312 任意の $n(=0,1,2, \ldots)$ に対して,$X_{n}^{**}=\{x\in X_{n}|\forall x^{l}\in X_{n}(x\subseteq_{\mathrm{i}}x’)\}$$a^{*}$$a^{*}$$a^{*}\subseteq_{\mathrm{i}}a$とおくと,$\subseteq_{\mathrm{i}}$$X_{n}^{*\mathrm{s}}=X_{n}^{*}$.

が成り立つ.

$|b’|$$a^{*}=\mathrm{n}\mathrm{i}\mathrm{l}$$a^{*}\subseteq_{\mathrm{i}}a$$b,$ $b’$$b,$ $b’$の組に対して定理が成り立つことを示す. $|b|=k,$ $|b’|\leq k$としてよい.
=n 垣の場合, $A=\{a\in B|b\subseteq_{\mathrm{i}}a\}$ であるので $a^{*}=b$ をとれば, 任意の $a\in A$ に対してが成り立つ.
の場合, $b=t(b_{1}, b_{2}),$ $b’=t(b_{1}’, b_{2}’)$$b’$$a^{*}\subseteq\iota a$$b’\neq \mathrm{n}\mathrm{i}\mathrm{l}$

とすると,
より,

$|b_{1}|,$$|b_{2}|,$$|b_{\acute{1}}|,$$|b_{\acute{2}}|<k$であり, 帰納法の仮定$A_{1}=\{a_{1}\in B|b_{1}\subseteq_{\mathrm{i}}a_{1}, b_{1}’\subseteq_{\mathrm{i}}a_{1}\}$$B|b_{2}\subseteq_{\mathrm{i}}$a2,$b_{2}’\subseteq_{\mathrm{i}}$, $A2=$ {a2a2} とおくと, 任意の$a_{1}\in A_{1}$

$\in$

{こ

(証明) 定理 38 より, $x\in X_{n}^{*}$
である
ことは明らかである. また, 系 310 において, $P=B_{n}$とおくと, $C=X_{n}$ となり, 任意の $x\in X_{n}$ に対してがただ一つ存在する. すが成り立つようななわち $X_{n}^{**}=\{x^{*}\}$ である. このとき,は任意の$x^{*}\mathrm{q}_{\mathrm{i}}$$x$$\Rightarrow x\in X_{n}^{\mathrm{s}}$$x^{*}$$x^{*}$に対して $|x^{*}|\leq|x|$ が成り立っている. すなわ
ち,である. もし, $|x’|=|x^{*}|$ となるような$x’\in X_{n}$ が存在したとすると, $x^{*}|x’$ かつ $|x^{*}|=|x’|$となり,が成り立つので. 補題 3.11 より, 結局であったので,$|X_{n}^{*}|=1$ であることがわかる.
が証明された. (証
結局 $X_{n}^{*}=\{x^{*}\}$ となり,$x\in X_{n}$$x^{*}\in X_{n}^{*}$$x^{\mathrm{r}}=x’$$x^{*}\in X_{n}^{*}$$X_{n}^{*}=X_{n}^{*\mathrm{r}}$

明終)

24
は同値関係となっている. すなわち, 次の命題 3.17が成り立つ.

系 313 任意の $n(=0,1,2, \ldots)$ に対して,$\simeq$$|X_{n}^{*}|=1$

命題 317 任意のが成り立つ.

定理 3.12 の証明参照. (証明終)(証明)$b_{1},$$b_{2}\in B$に対して,$b_{1}=b_{2}\Rightarrow b_{1}\simeq b_{2}$$b_{1}\simeq b_{2}\Rightarrow b_{2}\simeq b_{1}$定理 314 任意の $n(=1,2,3, \ldots)$ に対して,$(b_{1}\simeq b_{2})\Lambda(b_{2}\simeq b_{3})\Rightarrow b_{1}\simeq b_{3}$$x^{*}\in X_{n-1}^{*}$$\Rightarrow X_{n}^{*}=\{t(x^{*}, x^{*})\}$

が成り立つ.

が成り立つ.
(証明) 定理 37 より $t(x^{*}, x^{*})\in X_{n}^{*}$ であり, 系 313 より $|X_{n}^{l}|=1$ であることから明らか. (証明終)

32

(証明略)

命題 318 任意のすすなわち,$b_{2}\in B$

に対して,

(5)

$b_{1}\simeq b_{2}\Rightarrow|b_{1}|=|b_{2}|$被覆条件 (i) と (i) を考慮した場合

被覆条件として (i) と (i) を採用したものを =。と表

$b_{1},$

が成り立つ.
(証明)

における数学的帰納法により証のノード数がであるので,
明する . |b、$|=0$ のとき,成り立つならば,でなければならない. したがって, $|b_{1}|=|b_{2}|=0$ である. $|b_{1}|<k$ となるような全ての$b_{1}\in B$ に対して, 式 (5) が成り立つと仮定する. このとき,$|b_{1}|=k$ となるような任意の $b_{1}=\in B_{k}$ [こ対して,であり, $b_{1}=t(b_{11}, b_{12})$ ,が成り立つならば,$b_{2}=t(b_{21}, b_{22})$ とすると. $(b_{11}\simeq b_{21})\Lambda(b_{12}\simeq b_{22})$ また$|b_{1}|$$b_{1}$$b_{1}\simeq b_{2}$$b_{1}=\mathrm{n}\mathrm{i}\mathrm{l}$$b_{1}\subseteq_{\mathrm{i}\mathrm{i}}b_{2}\mathrm{g}\mathrm{e}$$b_{2}=\mathrm{n}\mathrm{i}\mathrm{l}$$(b_{1}=\mathrm{n}\mathrm{i}\mathrm{l})$$\vee((b_{1}\neq \mathrm{n}\mathrm{i}\mathrm{l})\Lambda(b_{2}\neq \mathrm{n}\mathrm{i}\mathrm{l})$$\Lambda(((b_{11}\subseteq_{\mathrm{i}\mathrm{i}}b_{21})\Lambda(b_{12}\subseteq_{\mathrm{i}\mathrm{i}}b_{22}))$$b_{1}\simeq b_{2}$$\vee((b_{11}\subseteq_{\mathrm{i}\mathrm{i}}b_{22})\Lambda(b_{12}\subseteq_{\mathrm{i}\mathrm{i}}b_{21}))))$$b_{2}\neq \mathrm{n}\mathrm{i}\mathrm{l}$とする.

$|b_{11}|,$問題 315(順序なし最小被覆木問題) すべての $n(=0$ ,1, 2,) に対して,$\ldots$(4)$Y_{n}=\{y\in B|\forall b\in B_{n}(b\subseteq_{\mathrm{i}\mathrm{i}}y)\}$このとき, 任意の $n(=0,1,2, \ldots)$ に対して,

とおく.

$Y_{n}^{*}=\{y^{*}\in Y_{n}|\forall y\in Y_{n}(|y^{*}|\leq|y|)\}$

を求めよ.

被覆条件 (i) と (i) を考慮した場合は, (i) のみで考えた場合とは違って, 解がどのようなものであるかはそれほど明らかではない.

アルゴリズ A 2 人力 :変数 :は $(b_{11}\simeq b_{22})\Lambda(b_{12}\simeq b_{21})$ が成り立つ.
$|b_{12}|<k$より, 帰納法の仮定より, $(|b_{11}|=|b_{21}|)\Lambda(|b_{12}|=|b_{22}|)$または $(|b_{11}| =|b_{22}|)\Lambda(|b_{12}|=|b_{21}|)$ が成り立つ. したがって, どちらの場合も $|b_{1}|=|b_{11}|+|b_{12}|+1=$$|b_{21}|+|b_{22}|+1=|b_{2}|$ が成り立つ. 以上により証明された. (証明終)

$i,$

$j$

: $y[i]$

$n$

. 整数

任意の $b\in B$ に対して, 同値関係\simeq における類を $[b]$ と表す. すなわち,$[b]=\{b’\in B|b\simeq b’\}$を含む同形類と呼ぶことにする. 命題が成り立
つのは明らかである. また, 以下では, 見やすさを考慮
して,による商集合をオーバーラインで表すことにする. 例えば次のようにである.
とする.

$[b]$

を

$b$

318 より, 任意の $b\in B_{n}$ に対して,$[b]\subseteq B_{n}$. 二分木の配列$\overline{B}=B/\simeq=\{[b]|b\in B\}$,$y[0]arrow \mathrm{n}\mathrm{i}1$$B_{n}=B_{n}/\simeq=\{[b]|b\in B_{n}\}$.

これらに対して,$\overline{B}=\bigcup_{=0}^{\infty}.\cdot\overline{B_{\dot{l}}}$$y[n]$,$i\neq j\Rightarrow\overline{B.\cdot}\cap\overline{B_{j}}=\emptyset$

定義 316(二分木の同形) 二つの二分木 と b が同形であることをと表すことにして. 二分木の同形を
次のように定義する.
$b_{1}$$b_{1}\simeq b_{2}$が成り立つ.
我々は, 3.1 節と同様の議論を進めたいのだから,

二分木$b_{1}\simeq b_{2}\Leftrightarrow \mathrm{e}$$B$$((b_{1}=\mathrm{n}\mathrm{i}\mathrm{l})$

–
–

同形類,
$\overline{B}$$\Lambda(b_{2}=\mathrm{n}\mathrm{i}\mathrm{l}))$$\vee((b_{1}\neq \mathrm{n}\mathrm{i}\mathrm{l})\Lambda(b_{2}\neq \mathrm{n}\mathrm{i}\mathrm{l})$$\Lambda(((b_{11}\simeq b_{21})\Lambda(b_{12}\simeq b_{22}))$という対応を考え, 同形類に対して二分木と同様の概念を導入する.
に対して,
明らかに, 任意の$\tilde{b}_{1},\overline{b}_{2},\overline{b}\in\overline{B}$$\vee((b_{11}\simeq b_{22})\Lambda(b_{12}\simeq b_{21}))))$

ただし,$b_{1},$$t(b_{21}, b_{22})$の同値$\simeq$.
1. $iarrow 1,$
2. $i=n$ ならば終了. $i\neq n$ ならば 3. へ進む.
3. $jarrow\lfloor(i-1)/2\rfloor,$ $y[i]arrow t$ ( $y[i-1]$ , y 化]), $iarrow i+1$ ,2. へ戻る.
出力 :$b$$b_{2}$

は nil でな $l1$ とき, それぞれ $t(b_{11}, b_{12})$ ,と表されるとする.

$\exists b_{1}\in\overline{b}_{1}(\exists b_{2}\in\overline{b}_{2}(t(b_{1}, b_{2})\in\overline{b}))$$\Rightarrow$$\forall b_{1}’\in\overline{b}_{1}(\forall b_{2}’\in\overline{b}_{2}(t(b_{1}’, b_{2}’)\in\tilde{b}))$25が成り立つ. このような は任意の ,に対して,必ずただ一つだけ存在する. したがって, 任意のに対して,$\tilde{b}$$\tilde{b}_{2}\in\overline{B}$$\tilde{b}_{1}$命題 320 任意の$\overline{b}_{1}$,$\overline{b}_{2}\in\overline{B}$に対して,$\overline{b}_{1},\overline{b}_{2}\in\ovalbox{\tt\small REJECT}$が成り立つ.

$t(\tilde{b}_{1},\tilde{b}_{2})=\{b\in B|b_{1}\in\tilde{b}_{1}, b_{2}\in\tilde{b}_{2}, b\simeq t(b_{1}, b_{2})\}$と定める.

$t(\overline{b}_{1},\tilde{b}_{2})\in\overline{B}$となっている. 二分木に対するものとの違いは,

(証明)

: 自明.
-1 こおける数学的帰納法により証明丈る.

$\Leftarrow$$\Rightarrow:||b_{1}||$のとき,{n 垣} であるので,$b_{1}=$$\overline{b}_{1}\in B$$\tilde{b}’\in\overline{B}$$\vee\supset$$||\tilde{b}_{1}||=k$$\tilde{b}_{1}$$\tilde{b}\subseteq \mathrm{i}\mathrm{i}\overline{b}’\mathrm{g}\mathrm{e}\forall b\in\overline{b}(\exists b’\in\tilde{b}’(b\subseteq \mathrm{i}\mathrm{i}b’))$$b_{2}\in\overline{b}_{2}$$(b_{11}\subseteq_{\mathrm{i}\mathrm{i}}b_{21})\Lambda(b_{12}\subseteq_{\mathrm{i}\mathrm{i}}b_{22})$$(b_{11}\subseteq_{\mathrm{i}\mathrm{i}}b_{22})\Lambda(b_{12}\subseteq_{\mathrm{i}\mathrm{i}}b_{21})$という定義をおく. これは,$t(b_{11}, b_{12}),$ $b_{2}=t(b_{21}, b_{22}))$が成り立つ (ただし,または$([b_{11}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{21}])\Lambda([b_{12}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{22}])$$\text{る}$$b$$_{-}^{-}\text{め}$$\in\overline{B}$$\{\tilde{y}\in\overline{B}|\forall\tilde{b}\in\overline{B_{n}}(\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}\tilde{y})\}$である (式 (4) と比較して欲しい). また, 任
に対して,

g線

$||\overline{b}||=n$が成り立っている.
であるので, 帰納法の仮定より,$(\exists b_{11}’\in[b_{11}](\exists b_{21}’\in$または$(\exists b_{11}’\in[b_{11}](\exists b_{22}’\in[b_{22}](b_{11}’\subseteq_{\mathrm{i}}b_{22}’)))\Lambda$$(\exists b_{12}’\in[b_{12}](\exists b_{21}’\in[b_{21}](b_{12}’\subseteq_{\mathrm{i}}b_{21}’)))$$b_{1}=t(b_{11}, b_{12})\simeq t(b_{11}’,$と定義すると,$b_{1}\in\tilde{b}_{1},$$t(b_{22}’, b_{21}’),$$b_{12}’\mathrm{J},$$b_{2}\in b_{2}$$\forall b_{1}’\in\tilde{b}_{1}(\exists b_{2}’\in\tilde{b}_{2}(b_{1}’\subseteq_{\mathrm{i}}b_{2}’))$$=$$\overline{Y_{n}^{*}}$$\{\tilde{y}\in\overline{Y_{n}}|\forall\tilde{y}’\in\overline{Y_{n}}(||\tilde{y}||\leq||\overline{y}’||)\}$$Y_{n}^{*}$

が成り立つ.

$b_{2}=t(b_{21}, b_{22})\simeq t(b_{21}’, b_{22}’)\simeq$

であることに注意すると,が成り立って る. 以上に$\mathrm{A}1$

より証明された. (証明終)となる.

問題 315 の解$([b_{11}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{22}])\Lambda$$||[b_{11}]||,$ $||[b_{12}]||<k$$[b_{21}](b_{11}’\subseteq_{\mathrm{i}}b_{21}’)))\Lambda(\exists b_{12}’\in[b_{12}](\exists b_{22}’\in[b_{22}](b_{12}’\subseteq_{\mathrm{i}}$$b_{22}’)))$$\overline{b}\subseteq B_{n}$$b_{1}=$. このとき. 命題 319 より.

$([b_{12}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{21}])$とす意の$\tilde{b}_{1}\subseteq_{\mathrm{i}\mathrm{i}}$$b_{1}\in\tilde{b}_{1}$$\tilde{b}_{2}$

$=$

$=0$

$\tilde{b}_{2}\in\overline{B}$が成り立つことである.
に対して,
任意の ,

$\overline{Y_{n}}$$||b_{1}||$$\exists b_{2}\in\tilde{b}_{2}(\mathrm{n}\mathrm{i}1\subseteq_{\mathrm{i}}b_{2})$に対して成り立つことより, 式 (7) がが任意の成り立つことは明らか. $||b_{1}||<k$ となるような全てのに対して, 式 (7) が成り立 と仮定する. このに対して,となるような任意のとき.
に対して, あるが成り立つならば. 任意のまたはが存在して.

$t(\tilde{b}_{1},\overline{b}_{2})=t(\tilde{b}_{2},\overline{b}_{1})$$\tilde{b}$(7)$\tilde{b}_{1}\underline{\mathrm{r}}_{\mathrm{i}\mathrm{i}}\tilde{b}_{2}\Leftrightarrow\forall b_{1}\in\tilde{b}_{1}(\exists b_{2}\in\tilde{b}_{2}(b_{1}\subseteq_{\mathrm{i}}b_{2}))$

補題 321 任意のは$b_{1},$ $b_{1}’,$ $b_{2},$$b_{2}’\in B$に対して,$([b\iota]\subseteq_{jj}[b_{1}’])\Lambda([b_{2}]\subseteq_{j\mathrm{i}}[b_{2}’])\Rightarrow[b]\subseteq_{\mathrm{i}\mathrm{i}}[b’]$.

$Y_{n}^{*}=\cup\overline{y}\in \mathrm{Y}_{|}’,-^{\tilde{y}}$が成り立つ (ただし,であることがわかる. したがって, 以を求めることに集中する.

$\mathrm{t}^{-}\backslash$,

本小節では–$Y_{r\iota}^{*}$$b=t(b_{1},$ $b_{2}),$$\tilde{b}_{2}\in$$([b_{1}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{1}’])\Lambda([b_{2}]\subseteq_{\mathrm{i}\mathrm{i}}[b_{2}’])$$b_{1}’’\in[b_{1}’]$$b_{1}\subseteq_{\mathrm{i}\mathrm{i}}b_{1}’’$万に対して.

$\Leftrightarrow\exists b_{1}\in\tilde{b}_{1}$$\overline{b}\iota\subseteq j\mathrm{i}\tilde{b}_{2}$($\exists b_{2}\in\tilde{b}_{2}$

).

(証明)
が成り立っている
ならば, 定義より.
が成り \mbox{\boldmath $\alpha$}つようなが成り立つような及ひが存在する.
$b”=t(b_{1}’’, b_{2}’’)$ とおくと,
命題 319 より,$[b’]$ が成り立つ.
したがって証明された. (証明終)$b_{2}’’\in[b_{2}’]$$b_{2}\subseteq_{\mathrm{i}\mathrm{i}}b_{2}’’$

命題 319 任意の bl,$b’=t(b_{\rceil}’,$ $b_{2}’)$$[b]\subseteq_{\mathrm{i}j}[b^{ll}]=$(bl。 ))(6)$b_{2}$

は順序関係で
命題 322 同形類に対して定義されたある. すなわち, 任意の ,に対して,$\subseteq_{\mathrm{i}\mathrm{i}}$が成り立つ.
(証明)$\Rightarrow$$\Leftarrow:||\tilde{b}_{1}||$と$\tilde{b}_{1}$:自明.

$\tilde{b}_{1}=\tilde{b}_{2}$j こおける数学的帰納法に\epsilon k り証明する.

{nil} より明らか.

$||\overline{b}_{1}||=0$となる全てのに対して, 式 (6) が成り立つと仮定する. このとき,$b_{2}\in B$ を任意に$|b_{1}|=k$ が成り立つようなであり, $b_{1}=t(b_{11}, b_{12}),$ $b_{2}=t(b_{21}, b_{22})$
とれば.
とすると.
または
が成り立つ.
$|b_{12}|<k$ であることに注意すると, 帰納法の仮定より, (. [bll](\exists b2’、$\mathit{0})$$\text{き},\tilde{b}_{1}=$$||\tilde{b}_{1}||$

(

く $k$

(

$\overline{b}_{1}\in\overline{B}$$b_{1}\subseteq_{\mathrm{i}\mathrm{i}}b_{2},$$b_{1},$$\overline{b}_{1}\underline{\mathrm{H}}_{\mathrm{i}\mathrm{i}}$$\tilde{b}_{1}\subseteq_{\mathrm{i}\mathrm{i}}$$\Rightarrow$$\overline{b}_{2}\in\overline{B}$$\tilde{b}_{1}\subseteq_{\mathrm{i}\mathrm{i}}\overline{b}_{2}$b\tilde 2)\wedge (b-2\sim 。
b-2)\wedge (b\tilde 2\sim 。

$\tilde{b}_{1}$$b_{3}^{-}$))$\Rightarrow\tilde{b}_{1}=\tilde{b}_{2}$$\Rightarrow\tilde{b}_{1}\subseteq j\mathrm{i}\ovalbox{\tt\small REJECT}$が成り立つ.

$b_{2}\neq\prime 1\mathrm{i}1$$(b_{11}\subseteq jjb_{21})\Lambda(b_{12}\subseteq_{\mathrm{i}\mathrm{i}}b_{22})$$b_{22})\Lambda(b_{12}\subseteq j\mathrm{i}b_{21})$$(b_{11}\subseteq_{\mathrm{i}\mathrm{i}}$(証明略)$|b_{11}|,$$\forall b_{11}’\in$$\in$

任意の $n(=1,2,3, \ldots)$ に対して.

$[b_{21}](b_{11}’\subseteq_{\mathrm{i}\mathrm{i}}b_{21}’)))\Lambda(\forall b_{12}’\in[b_{12}](\exists b_{22}’\in[b_{22}](b_{12}’\subseteq_{\mathrm{i}\mathrm{i}}$または $(\forall b_{11}’\in[b_{11}](\exists b_{22}’\in[b_{22}](b_{11}’\subseteq jib_{22}’)))\Lambda$
が成り立つ. したがって,ならば, $b_{1}’=t(b_{11}’, b_{12}’)$ とおけば,またはが成り立つようなが存在して, $t(b_{21}’, b_{22}’)\simeq$$t(b_{21}, b_{22})=b_{2}$ が成り立つ.
すなわち, $b_{2}’=t(b_{21}’, b_{22}’)$とおけば,(( Cii )) が成り立つ.
り,$|b_{1}|=k$ では任意でよかったので,とに対して, 式 (6) が成り立つ. 以上によりなる任意の証明された. (証明終)$b_{22}’)))$$\lfloor(n-1)/2\rfloor=\{$$(\forall b_{12}’\in[b_{12}](\exists b_{21}’\in[b_{21}](b_{12}’\subseteq_{\mathrm{i}\mathrm{i}}b_{21}’)))$$(n-1)/2$$(n-2)/2$

,

$n$

,

$n$

が奇数のときが偶数のとき$b_{1}’\simeq b_{1}$$(b_{11}’\subseteq_{\mathrm{i}\mathrm{i}}b_{21}’)\Lambda(b_{12}’\subseteq_{\mathrm{i}\mathrm{i}}b_{22}’)$$b_{21}’)$$(b_{11}’\subseteq_{\mathrm{i}\mathrm{i}}b_{22}’)\Lambda(b_{12}’\subseteq_{\mathrm{i}\mathrm{i}}$という表現を使う.

$b_{21}’,$ $b_{22}’$$\forall b_{1}’\in[b_{1}]$$\text{あ}$$\tilde{b}_{1}$$b_{1}$$\exists b_{2}’\in[b_{2}]$$b_{1}’$

補題 323 任意の $n(=1,2,3, \ldots)$ に対して,$b_{2}’$$\forall\tilde{b}\in\overline{B_{n-1}}(\exists\tilde{b}’\in\overline{B_{n}}(\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}\tilde{b}’))$$||\tilde{b}_{1}||=k$が成り立つ.

26(証明) 任意の{こ対して,
ば, $||b’||=||b||+1$ であり,証明された. (証明終)$\tilde{b}’=t$$\overline{b}\in\overline{B}$$\overline{b}\underline{\mathrm{C}}_{\mathrm{i}\mathrm{i}}\tilde{b}’$($\tilde{b},$[nil]) をとれ

である.

参考文献

したがって

[1] 牧山幸史, “最小評価木問題に対する一考察”,.csce.
http:$\mathrm{k}\mathrm{y}\mathrm{u}\mathrm{s}\mathrm{h}\mathrm{u}-\mathrm{u}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\sim_{\mathrm{m}\mathrm{a}\mathrm{k}\mathrm{i}\mathrm{y}\mathrm{a}\mathrm{m}\mathrm{a}}/$$//\mathrm{k}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{a}$補題 324 任意の $n(=1,2,3, \ldots)$ に対して,$\mathrm{k}\mathrm{e}\mathrm{n}\mathrm{q}/\mathrm{M}\mathrm{E}\mathrm{T}\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}/$(8)$m\geq n\Rightarrow\forall\tilde{b}\in\overline{B_{n-m}}(\exists\tilde{b}’\in\overline{B_{n}}(\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}\tilde{b}’))$

が成り立つ.
(証明) $m$ における数学的帰納法により証明する. $m=0$のときは命題 322 より明らか. $m<k$ ならば式 (8) が成り立つと仮定する. このとき, $m=k$ ならば, 補題 323$B_{n-m}$ に対してが成り立つようより, 任意の–$\tilde{b}\in$$\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}$$\tilde{b}’$にが存在する. 帰納法の仮定より,となるようなが存在する. したがっはが成り立つ. 以上により証て, 命題 322 より,明された. (証明終)な$\overline{b}’$$b’$$\overline{b}’$$\in\overline{B_{n-(m-1)}}$$\overline{b}’’$$\subseteq_{\mathrm{i}\mathrm{i}}\tilde{b}^{Jl}$$\in\overline{B_{n}}$$\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}\tilde{b}’’$

補題 325 任意の $n(=0,1,2, \ldots)$ に対して,$(\tilde{y}\in\overline{Y_{n}})\Lambda(m\leq n)\Rightarrow\forall\overline{b}\in\overline{B_{m}}(\tilde{b}\subseteq_{\mathrm{i}\mathrm{i}}\overline{y})$が成り立つ.
(証明)とする. 補題 324 より, $m\leq n$ ならが成り立つようなに対して,ば, 任意のが成り立の定義より,が存在する.
つ. したがって証明された. (証明終)$\tilde{y}\in\overline{Y_{n}}$$\tilde{b}\in ・B_{m}$$\overline{b}’\in\overline{B_{n}}$$\tilde{b}\subseteq_{\mathrm{I}\mathrm{i}}\tilde{b}’$$\tilde{b}’\subseteq_{\mathrm{i}\mathrm{i}}\overline{y}$$\overline{Y_{n}}$定理 326 任意の $n(=1,2,3, \ldots)$ に対して,($\tilde{y}_{1}\in$$Y_{n-1}$】–)$\Lambda(\tilde{y}_{2}\in\overline{Y_{[(n-1)/2\rfloor}})\Rightarrow t(\tilde{y}_{1},\tilde{y}_{2})\in\overline{Y_{n}}$が成り立つ.
(証明)が成り立つとと表す とが,$(\tilde{y}_{1}\in\overline{Y_{n-1}})\wedge(\tilde{y}_{2}\in\overline{Y_{[(n-1)/2\rfloor}})$す 6. 任意の$\tilde{b}\in ・B_{n}$は b\tilde$=t(\overline{b}_{1},\tilde{b}_{2})$$\llcorner\vee$$\vee C\text{き}$力 I 成り立つことより, 」としてよい. $||\tilde{b}_{1}||+||\tilde{b}_{2}||=n-1$ より, $||b_{1}||\leq n-1$ ,が成り立つので, 補題 325 より,
このときが成り立つ. したがって,$|\overline{b}_{1}||\geq||\tilde{b}_{2}||$$t(\overline{b}_{1},\tilde{b}_{2})=t(\tilde{b}_{2},\overline{b}_{1})$$||\overline{b}_{2}||\leq\llcorner(n-\mathfrak{h}/2\rfloor$$b_{1}\subseteq_{\mathrm{i}\mathrm{i}}$$\tilde{y}_{1},\tilde{b}_{2}\subseteq j\mathrm{i}\tilde{y}_{2}$は任意でよかっが成り立つ.
が示された. (証明終)$\overline{b}$$\tilde{b}=t(\overline{b}_{1},\tilde{b}_{2})\subseteq_{\mathrm{i}\mathrm{i}}t(\tilde{y}_{1},\overline{y}_{2})$たので,$t(\tilde{y}_{1},\tilde{y}_{2})\in\overline{Y_{n}}$議論を 31 節と同様に進めるならば, ここで,$(\tilde{y}_{1}^{*}\in\overline{Y_{n-1}^{*}})\Lambda(\overline{y}_{2}^{*}\in\overline{Y_{\lfloor(n-1)/2\rfloor}^{*}})\Rightarrow t(\tilde{y}_{1}^{*},\overline{y}_{2}^{*})\in\overline{Y_{n}^{*}}$

を証明したいのであるが, 3.1 節と同様の考え方ではこれがはうまくはいかない. なぜなら,に対して成り立つことから, 全ての b\tilde$t(\tilde{b}_{1},\tilde{b}_{2})=t(\overline{b}_{2},\tilde{b}_{1})$$=t(\tilde{b}_{1},\overline{b}_{2})\in\overline{B_{n}}$$\overline{b}_{1}\subseteq_{\mathrm{i}\mathrm{i}}\tilde{y}_{1}^{*}$

が成り立っている必要性を言うことができないためである.

4

おわりに

本稿では, 最小評価木問題の被覆条件を切り分けることによって得られた緩和問題に対する考察を行った. 被覆条件の緩和にはもう一つ, (i) と (可) を採用した場合が考えられる. また, 被覆条件以外の緩和については, 文
献 [1] の第 5 章にある準最小評価木問題のように, 被覆しなければならない二分木の集合の範囲を狭めるといった方法もある. 今後はこれらの場合に対しても考察を重ね, 最小評価木問題を解決する足掛かりとしたい.

,

卒業論文