Title
ランク変調と順列集合の支配集合による分割の分類( 本文
(Fulltext) )
Author(s)
高橋, 佑輔; 鎌部, 浩
Citation
[電子情報通信学会技術研究報告. ISEC, 情報セキュリティ]
vol.[113] no.[484] p.[13]-[18]
Issue Date
2014-03-03
Rights
copyright 2014 IEICE
Version
出版社版 (publisher version) postprint
URL
http://hdl.handle.net/20.500.12099/53494
※この資料の著作権は、各資料の著者・学協会・出版社等に帰属します。
Institute of Electronics, Information, and Communication Engineers
工nstitute 。f Electr 。nics，
工nf 。rmati 。n厂
and C。 unication Engineers一
般社
団法
人電
子情 報 通 信 学 会
THE
INSTITUTE
OF
ELECTRONICS
，
INFORMATION
AND
COMMUNICATION
ENGINEERS
信 学 技 報
IEICE
Technical
Report
IT2013
−
56
，
ISEC2013
−
85
，
WBS201345
（2014
−
3）
ラ
ン
ク
変
調
と
順 列
集 合
の
支配 集 合
に よ る
分割
の
分 類
高橋
佑輔
†鎌 部
浩
††
岐 阜
大
学
大
学 院
工
学
研
究 科
応
用
情 報 学 專 攻
あ ら ま
しフ ラッ シュ メモ
リ
にデ
ー
タ を 記 録 す
る た めの方 式
と して，
デ
ー
タ を電 荷
レベルの大 小 関
係
に基
づ く置
換
を用
いて表
現
す
る方 式
が
提 案
さ れ た
．
Minimal
push
up と呼
ば れ
る操 作
を 基
本 操作
と し
て順 列
を
変 化
さ せ る
こと
でデ
ー
タ を
書
き
換
え る
こ と に よっ て，
書 き換
え に よ る電 荷
の増加
を
抑
え
ることが
でき
，結 果 的
に フ ラッ シ ュメ モリ
の寿 命
を
長
く
す
る
こと が
でき る
。
こ の方 法
で電
荷
の増
加 を 制 限 す る 符 号 を 構 成 す る た め
には
，
あ る
グ
ラ
フ の頂 点
集
合 を 支 配
集
合
に分
割す
る
こ とが 重 要
にな る
．
本 稿
では
，符 号 長 が
4
の場 合
に支 配 集 合
の要 素 数
の下 界
を達 成す
る支 配
集 合
を構 成
す る
ため
の必 要 条 件 を 示
し，
そ の よう
な支
配
集合
を全
て構 成す
る．
ま
た，
下 界 を
達成 す
る支 配集 合
の組
み合
わ せ
によ
っ て構 成
でき
る全
て の符
号 を
得
た
．
さ ら
に1
つ の支配 集 合
から
異
な る
支配 集合
を
構
成
でき る 定 理 を 用
い て これ らの符 号
を 分 類 す る
．
キ
ー
ワー
ド
ラ
ン ク変 調
，
圧 縮
符
号 化
，
フ ラッ シュ メモ リYusuke
TAKAHASHI
†andHiroshi
KAMABE
†
†Information
Science
Division，
Graduate
School
ofEngineering
，
Gifu
University
Abstract
A
coing scheme using a rank modulation wasproposed
for
storingdata
in
flash
memories．
There
aretwo
fundamental
operationfor
cha皿ging
the
state of cells，called apush
to 七he
top and a minimalpush
up．
A
cons 七ruc一
七ion
of a code withthe
minimalpush
up operation stronglydepends
on aparti
七ion
ofthe
set of al1permulations
in
dominat
sets of atrasision
graph
induced
by
the
minimalpush
up operation．
ln
this
paper ，
a necessary and suMcientcondition
is
proposed
f
（）r adomina
皿t
setto
meet alower
bound
onthe
number of elementsin
the
dominant
set with equa ユity
whenthe
length
ofthe
eraseblock
is
4．
All
possible
partitions
by
dominant
sets areidentified
usingthe
condition．
Then
the
partitions
are classi 丘edinto
some equivalent classes．
Key
wordsRa
皿k
Modulation
，Compressed
Encoding
，Flash
Memory
1
．
ま え
が
き
フ ラッ シュ メモ リ は
書
き換
え 可能
な不
揮 発 性のメモ リであり
，
現 在 広 く 普 及 して い る．
フ ラッ シュ メ モリ を 用いたドライ ブ 装 置（
Solid
State
Drive
，
SSD ）
はハー
ド ディスク 装 置（
Hard
Disk
Drive，
HDD
）
に比べ衝 撃
へ の耐性
が高 く
，
消 費電 力
と発
熱
が と も に少
ない といっ た利点
を持
っ て いる．
フラッシュ メモ リ は セ ル と 呼ば
れ る素
子 か ら構 成
さ れ，
デ
ー
タの書 き
込 み はセ ル に電荷
を注
入す
る こ と で行
う．
セ ル に貯
める こ とが可能
な 電荷 量
には限界
が あリ
，一
杯
に なっ た後
も書
き換
え を続
け る た め には電 荷
を除
去 し なけ
れば なら
ない．
電荷
の注
入は セ ル単位
で 行 え る が，
電 荷の除 去 は 複 数のセルか ら構
成 さ れ るブ
ロ ッ ク単
位
で し か行
えない．
こ のブロ ック単位
で の電荷
の除
去 をブ
ロ ッ ク消
去と呼ぶ．
ブロック 消 去 はセ ルを劣
化さ せ る ため，
品質
が保
証 さ れ るブ
ロ ック消
去 回数
には制 限
があ
る，
そこ で，
なるべく
ブロ ック消 去
を行
わ ないよ う な符号 化 方法
が研 究
さ れて いる．
セル には
SLC （Single
Level
Cell）
とMLC （
Multi
Level
Cell
）
の
2
種 類
が あ る．SLC
は 電 圧 を0
と1
に 対 応 させるこ とで1
ビット を 記録 す
るの に対
し，
MLC
は閾値 を設 定
して中間
の値を
用いること に よ り．
ひ とつ のセ ル に 複 数 ビット を 記 録 す る．
MLC
が 閾 値に よっ て 分 けら れ たq
個の離
散レベル の う ち 1つを記 録 す る 場 合，
そ れ を サ イズ qの ア ルフ ァ ベ ットのシ ンボル とみ なす
こ とができ
る．
大 容 量 化
のた めにMLC
は有 用
であ
る が，
目 標の値 に 向 かっ て 電 荷 を 注 入 す る と き に 電荷
を 過 剰 に 注 入 し てしま うオ
ー
バー
シュー
ト
という 問題 を持
っ ている．
オ
ー
バー
シュー
トによっ て 目標
の閾値
を 越 えて し ま う と 必 要の無い ブ ロック消
去 を招
いてし ま うのであ る．
こ の問 題 を 解 決 す る た めに
，
A
，
Jiang
ら はラ ン ク変調 （
Rank
Modulation
）
を使
用す
る方 法
を提 案
した［
1
］
．
ラ ン ク変 調では
，
デ
ー
タ をセル の電 荷レベ ル の大 小 関 係に対応
し た セ ル の番
号の置換
に対応
さ せ る．
ブロック の単位
を n個
の セ ルとす
る．
n個
の セ ル に それ ぞ れ1
か らnま
で番 号 を割 り
振
る．
例
えば
nニ
5
な らば順
列［
4
，
1
，
5
，
2
，
3］
といっ た様
に 表 さ れ，
セ ル4
の 電 荷 量が最 も 多 くセ ル3
の電 荷 量が最 も 少 ない．
Institute of Electronics, Information, and Communication Engineers
NII-Electronic Library Service
工nstltute 。f Electr 。nlcs，
工nf 。rmatl 。n厂
and C。 unlcatlon Englneersこ の
方 式
で は電 荷
レベルの差
がわ か れば
よい の で，
デ
ー
タに対
応 さ せ る た めの閾 値 を 必 要 と し ない．
ま た，
電 荷の大 小 関 係に デー
タが符
号 化さ れ て お り電荷
の絶 対 値に は無 関 係で あ る た め，
オー
バー
シュー
トの問
題 が 生 じにくい という利 点
が あ る．
ラン ク変
調に おけ
る誤 り 訂正符
号 や，
ブロ ッ ク を よ り 小さな単 位
に 分 割 す るこ方 式 が研
究 さ れて い る［
2］
，
［
4］
，［
5］
，［
6］
．
こ の 方 式で は 現 在の順 列 を 別の 順 列に変 更 す ること が デー
タ の書 き換 え を 意 味 す
る．
コスト を電荷
の増 加
量 と考
え た 場合
，
よ り少
ないコ ストで順 列
を変更 す
る こ と はブロ ック消 去
の発
生 間 隔 を 延ば す
こと につ なが
る．
［
1］
ではpushto
the
top
操 作 を順 列を
変
更す
る た め の基 本操 作
と し て用いた場 合に，
電荷
の増
加 量 を抑制 す
る符 号
が提 案
さ れている．
この符 号
は任 意
のセルの
tw
n に 対 して構
成 可 能 で あ る．
minimal push up を 用い た場 合
は，
push
tQ the top を用いた場 合より も符
号 化率
の高
い符 号 を 構 成でき ること が 期 待でき る
．
minimalpush
up を 使 用す
る 場 合 にn＝
・
3
，
4
，
5
，
6
で最 大 の符
号 化 率 を 達 成 す る 符 号が
示 さ れている［
3］
，
［
7］
．
これ らの符 号
を構成 す
る た めには順 列 集合
をいくつ かの支 配 集 合に分 割 す る 必 要 が あ る．
よ り 多 くの支 配集 合
に分割 す
る こ と で，
より高
い符
号 化 率 が達
成できる．
第
2
節
で は電荷
の増加
量 を制 限す
る符号
を説 明す
る．
第
3
節
では，
minimal push up を 順 列 を 変 更 す る た めの基
本 操作
と し て用い た場合
に構 成
さ れ るグラ フ に対し て，
n＝
4
の場合
に支
配 集 合の要 素 数に関 す る 下 界 を 達 成 す る 支 配 集 合 を 構 成 す る た めの必 要 条 件 を 示す
．
さ らに，
n＝
・
4
の場 合に構成
可能
な全
て の下 界 を 達 成 す る 支 配 集 合 を 求 め，
構 成 可 能 な 全て の最 大の符号 化 率
を持
つ符 号
を構 成す
る．
第
4
節
では そ れ らの符号
を同
じ 様 な 性 質 を 持っ た グルー
プ に 分 類 す る．
2
．
電 荷
の
増 加 量 を 制 限 す
る
符 号
2
．
1minimal push llp長
さ n の全て の順
列 をSn
とす
る．
状
態 を 順 列 とし て定 義 し，
現 在の順 列を u＝
［
u（
1）
，
．
一
，
u（
n）
1
∈Sn
，
遷 移 先の順 列を v＝
［
v（
1）
，
＿
，v（
n）
〕
∈Sn
とす
る．
minimalpush
up は どのセ ルも
できるだけ 少
ない電 荷
レベ ル の増 加
となるよ うに v に基い て電 荷 を 注 入 す る 操 作であ る，
i
＝ n−
1
，
n−
2
，
＿，
1
に 対 して 順 番に次の操 作
を行う ：｛
セ ル Vi の レベルをセ ル Vi＋ 1 の レベ ルより も大
きくす
る｝
．
例
え ば，
u＝
［
1
，2
，3
，4］
，v＝
［
2
，4
，1
，3］
と す る と， まず
v3＝
1
とv4＝
3
の 電 荷レベルを を 比 較 し，
v3 が大 き く
なるよ うに電荷
レベ ルを増 加
さ せ る．
次
に u2＝
4
と u3 ＝1
の電 荷レベ ルを を 比 較 し，
v2 が大 き く な る よ うに電 荷 レベルを増
加 さ せ，
最 後に v1＝
2
とv2；
4
の電 荷レベ ルを を 比 較 して v2 が大 き く な る よ うに電荷
レベルを増加
させる．
2
．
2
コ ス トminimal
push
up によっ て u をv に変 更 す る 為のコ スト を0
（
u → v）
と す る．
こ のコ ス ト は書
き換
え 前の最 大の電荷
レベ ルと，
書
き換
え後
の最
大の電 荷
レベ ルを
比較
し たとき
の増 加 量
を 指 し，
整 数 で 表 さ れ る．
0
（
u → v）
＝1
であ るこ とは最
小の 最 大 電荷
レベル の増
加で書
き換
え を行
うこ とを 意 味し て おり，
常にそのよ う な 書 き 換えが 可 能と な る符
号を構成 す
る こ とが 目標
とす
る．
0
〔
u → v）
は次 式
で定 義
さ れ る［
3］
．
図1n
＝
3
の遷 移 グラ フ σ（
U → V）
−
m ・x（
ゼ 1（
の
一
U−
’（
の）
t∈［司（
1
）
こ こ で［
n］
＝
｛1
，2
，＿
，n｝
とす
る．
例
え ば， u＝
［
1，
2，
3
，
4］
，
u＝
［
2
，
1
，
4
，
3］
な らば
0
（
u → v）
＝
1
，
u＝
［
1
，2
，3
，4
］
，u＝
［
4
，3
，2
，1］
な ら ば0
〔
u → v）
＝
3
と な る．
2
。
3
遷 移 グラ フ遷 移 グラフ
Gn
＝
（
Vn
，．An
）
を次
の ように定 義 する．
Vn
は 長 さ がn のす
べ て の順
列Sn
であ る．
有 向 辺U → V が 存 在 す る事
と，
0
（
u → v）
＝
1であ ること は 同 値にな る よ う に 集 合An
を 定 義 す る．
頂 点 u ∈Vn
と r∈｛
0
，
1，
．
．
．
，
n−
1｝
が与
え ら れ た と き，
）＊
Bn
，
。
（
U）
をBn
，
r（
U）
＝
｛
V ∈VnlC
（
U → V）
≦r｝
と 定義 す
る．
Bn
，
r（
u）
の要 素 数 は 以 下で与えられ る［
3
］
．
IBn
，
。
（
u）
1
＝ r ！（
r ＋1）
n−「
（
2
）
こ こ で，
集 合A
に対し てレ
41
を そ の要
素 数とする，
図1
は n＝
3
の遷 移 グ ラフ であ る．
どの辺 もコ スト 1の状 態 遷 移を表す
．
push
to the top を 用いた 場合
には 実 線の遷 移 し かで き ない が
，
minimal push up を状態 遷移
のための操作
と し て用いる の で あ れば破 線
の遷移
も可能
となる（
push
tQ the tQp につ いて は国
を参 照
）
．
2
．
4
支
配集
合Gn
中
の頂点 集合
をD
とす
る．
D
中の頂 点 を 除 く 全 て の 頂 点 が D の頂 点へ の 有 向 辺を持つ場 合，
ヱ） を支 配集 合
と呼ぶ．
IDI
を 支 配 集 合D
が 含 む 順 列の数であ る と す る．
IDI
は 次の不 等 式 を 満たす
［
3
］
．
1
・1
・
ll
・・
．
：
，Xi
L
−
・（
・）
2
．
5
符
号 構 成r
・
＝
1の場 合，
すな わ ち常
にコス ト 1で書
き換
え可能
な符
号 を考
え る．
記 録 す
る情 報
シ ン ボル をi
∈｛
1，
＿，
1｝
とする．
遷 移グ
ラフGn
の頂点 集 合
が，
互い に素
な支配集 合
D
、，
＿，
Dl
に分
割でき た と 仮 定 す る．
こ のとき，
D1，
＿，
D、
，
＿，
Dl に それ ぞ れ異な る シ ンボルi
を割
り当
て，
D
，
中の順 列 全てを 割 り 当て一14 一
N工 工一
Electronlc LlbraryInstitute of Electronics, Information, and Communication Engineers
工nstltute 。f Electr 。nlcs，
工nf 。rmatl 。n厂
and C。 unlcatlon EnglneersD1
［
1，
2，
3，
41
〔
2，
3，
4，
11［
3，
4，
ユ，
21［
4，
1，
2，
31 D2［
1，
2，
4，
31［
2，
4，
3，
11［
4，
3，
1，
21［
3，
1，
2，
4］
D3［
1，
3，
2，
41［
3，
2，
4，
11［
2，
4，
1，
3】
［
4，
1，
3，
2］
D4［
1，
3，
4，
21［
3，
4，2，1｝
［
4，
2，
1，
3】
［
2，
1，3，4］
P5［
1，
4，
2，
3】
［
4，
2，
3，
1］
［
2，
3，
1，
41［
3，
1，
4，
2］
D6［
1，
4，
3，
2】
［
4，
3，
2，
1］
［
3，
2，
1，
4】
［
2，
1，
4，
3］
表 1（3
）
の下 界 を達 成する支 配集 合による構 成 ら れた情 報シ ンボルi
に写 像 す る．
高い符 号 化 率 を 持つ符 号 を構 成 す
る た めにはに，
n ！個
の順 列
をできるだけ 多 く
の支配 集
合 に 分 割 で き れば
よい，
更新 関
数 は 情 報 シンボ ルi
が 与 え ら れ た場 合に，
割 り 当てられ た情 報シ ンボ
ル iと一
致 する順 列の中 で，
現 在の順 列 か らのコス ト が 最 も 小 さい順 列 を 返す
．
n1 個 の全
て の順 列に対
して シ ンボ
ルが割
り 当て ら れている符
号 をfull
−
assignment符号
，
全て の順 列
に対
してシンボ ル が割り 当
てら れて い ない
符
号 を non−
fu11
−
assignment 符 号 と 呼 ぶ．
本 稿で は，
full
−
assignment符
号のみ を扱
う．
［
3
］
ではn＝3，
4
，
5
の場合
に，
［
7］
では冊＝
6
の場 合
に，
全て の支配 集 合
が（
3
）
の下界
を達 成す
る符
号が
示 さ れ ている．
表
1
は n ＝4
の 場 合 の一
例 で ある．
3 ．
n ＝4
の場 合
に
下 界 を
達
成 す る
支
配 集 合 を 構
成 す
る
た
め
の必 要 条 件
n
＝
4の場 合
に下 界を 満 たす 支 配集 合 を構 成 す
る た めの十
分 条 件 が示さ れて い る［
7
］
．
定 理1
．
G4
に お け るr
の
の下 界 と 等 しい 集 合 をX
と す る．
こ の ときX
が次
の性 質 を 満
たす な ら ば
，
X
は支
配集 合
で あ る．
X
中
の各 順
列の3
番
目の要 素
を集
め る と｛1
，2
，3
，4｝
と なる．
同様
に 4番
目 を集
め て も｛
1，2，3，4｝
と な る．
す
な わ ち，
｛
M3 ：［
Xl，
x2，
x3，
x4］
∈X ｝
＝｛1
，2
，3
，4｝
かつ，
｛
ω4：［
x1 ，m2，x3 ，x4｝
∈X ｝
＝
｛
1
，2
，3
，4｝
となる．
この条件
は， 必要 条件
に も なっ ている．
定理2
。
G4
に おける集 合
X
を（
3
丿
の下 界を達 成す
る支 配集
合 と す る．
このと きX
は 次の性質
を満
たす
．
X
中
の各順 列
の3
番
目
の要素
を集
める と｛
1，
2，
3
，
4｝
となる．
同様
に 4番
目を集
めて も｛
1
，
2
，
3
，
4｝
と な る．
す
な わ ち，
｛
鞠 ：［
Xl，
x2，
x3 ，x4］
∈X ｝
＝
｛
1，2
，3
，4｝
かつ，
｛
x4 ：［
xl，
π27M3，
x4］
∈X ｝
＝
｛
1，
2，
3
，
4｝
と な る．
証 明．
n＝
4
の支 配集
合 を 構 成 す る 要 索 数の下 界 は（
3）
よ り4
で あ る．
X
＝
｛
Xl，
x2 ，x3 ，x4｝
，
勾＝
［
コ3ゴ1，物 2，筋 3，吻 4］
，
Y3
＝
｛
Y3
：［
Y1
，
Y2iY3
，
Y4］
∈X｝
，
Y4＝
｛
Y4 ：［
Yl，
Y2，
Y3，
Y4］
∈X ｝
，
｛
a，b
，c，d｝
＝｛1
，2
，3
，4｝
と す る．
ま た，
2
つ の順 列 を u＝
［
u（
1）
，＿
，u（
n）
1
¢
X，
v＝
［
v（
1）
，
＿、
v（
n）
1
∈X
と し，φ
ゴ（
w）
＝
φ
ゴ（
［
w（
1）
，
＿，
w（
n）
D
＝
w（
」
）
とす
る．
ま
ず
，
Y3
＝｛
α，
b
，
c，
d｝
と な ること を示す．
Y3
≠ ｛
α，b
，c，d
｝
となるパター
ン はIY
，1
＝
1，
IY
，1
＝
2，
IY31
＝
3
の3
通 りであ る．
これ らの場合
にX
が支配 集 合
と な ら ない こと を 示す
．
1 ）
IY
，1
＝
1
の場 合
Y3 ＝
｛
a｝
とす
る．
この 場 合，
u＝
［
a，
b，
c，
cl］
¢
X
であ る．
コスト
の計算
式〔
1）
か ら，
0 （
u → v）
＝
maXi ∈回＠
−
1（
の
一
u−
1（
i）
）
≧ u−
1〔
a）
一
ガ 1（
α）
＝2
と な り，
［
a，
b
，
c，
d］
か らX
中の順 列へ 遷移 す
る た め にコ ストは少 なく とも2
必要
となる．
よっ てX
は 支配
集合
に は 成 リ 得 なし丶 2）
1
鶏1
＝
2の場 合
B3
＝
｛
a，
b｝
と す る．
こ の場 合 は 次の3
通 り が 考 え ら れる．
1
｛
i
：φ
3（
Xi）
｝
1
＝
1
1
｛i
：φ
3（
Xi）
｝
1
＝
2
1
｛
乞：φ
3圃 ｝
1
＝3
（
4
）
（
5）
（
6）
（
4）
と（
6
）
はa とb
を 入れ替 え れば
同 じにな るため，（
4）
と（
5）
の場 合
を考
え る．
（
4）
の場 合m・
＝
［
X・・ ，m・2，
a，X・4］
，
X2＝
［
＝ 2・，
X22，
a，
X24］
，
X3＝
［
＝31，X32 ，α、X34］
，
X4＝
［
X41，X42 ，b
，X44］
と しても一
般 性
を失
わ ない．
uニ
［
a，
x44，
u｛
3）
，
u（
4）
］¢ X
という 順 列 を考
え る，
こ のと き，
X
には xゴ1＝
a と なる順 列
が存 在
し ない．
ま
た，
X42 は X44 と 成 り得
ないた め，
u ばX
に含
ま れ ない，
i・
＝
1，
2，
3
の とき，
0 （
u → Xi）
＝
maXz ∈ 圄＠
−
1（
i）
＿
u−
1（
i））
≧
u−
1（
α）
−
v−
1（
α）
＝
2
と な る，
i
＝
4
の とき
，
0
（
u → x4）
＝
maxi ∈圄＠
−
1（
i）
−
u−
1（
i））
≧u−
1（
x44）
−
v−
1（
x44）
＝2
と なる．
u からX
中
の順 列へ遷 移 す
る た め にコス トは少な くとも 2必要
と な る た め，IY31
；
2
かつ（
4）
の場合
にX
は支配 集合
には成
り得 な
い．
（
5）
の場 合
X・
一
［
X・ ・，
X・2，
a，
X・4］
，
X2 ＝［
X2 、，
X22，a，
X24】
，
X3 ＝［
X31，X32 ，b
，X34］
，
X4＝
〔
X41，X42 ，b
，X44］
とす
る．
（
X14，
X24）
が 取 り う るパ ター
ン は（
b
，
b）
，
〔
C，
C）
，
〔
d
，
d）
，
（
b
，
C）
，
（
b
，
d）
，
（
C，
b）
，
（
C，
d）
，
（
d
，b）
，（
d
，c）
の9
パ ター
ン であ
る．
これ らそれ ぞ れに対
して（
X34，
X44）
の取 り う る パ ター
ンが
（
α，
α）
，
（
C，
C）
，
（
d
，
d）
，
（
α，
C）
，
（
a，
d）
，
（
c，α）
，（
c，d
）
，（
d
，a）
，〔
d
，c）
の9
パ ター
ン存 在す
る，
（
皿147×24）
＝
（
b
，
b）
の場 合，u
＝
＝
［
b
，a，
u（
3）
，
u（
4）
1
≠X
とす
ると，
i
＝
1
，
2
の とき
，
C
（
u → Xi）
； maXi ∈［n ］（
v−
1（
i）
−
u−
1（
i））
≧ u−
1（
b）
−
v−
1（
わ）
＝3
，
i
＝
3
，4
の とき，
σ〔
u → Xi）
＝
maXi ∈［n］（
v−
1一
u−
i（
i）
）
≧ u−
1（
b）
−
v−
1（
b）
＝
2
と な る．
よっ て，
こ の場 合
にX
は支 配 集
合
には成 り得
ない．
〔
M14，
X24）
＝
（
C，
C）
の場合
，
（
x34，
x44）
＝
（
α，
α）
な らば
，
u ＝［
α，
b
，
c，
di
≠ x
と す る と，
i
＝
1
，2
のと き，
0
（
u → mi）
＝
maXi ∈回＠
−
1（
i
）
＿
u−
1（
i
）
）≧
u−
1（
a）
−
v−
1（
α）
＝
2
，
i
＝
3
，
4
の と き， σ（
u → Xi）
；
maXi ∈回（
v−
1（
i）
−
u−
1（
i））
≧u−
1（
α）
−
v−
1（
a）
＝3
と なる．
よっ て，
こ の場合
にX
は 支 配集
合には 成 り 得 ない．
〔
x34 ，x44）
＝
（
c，c）
な ら ば，
u＝
［
c，b
，d
，
α］¢ X
とす
る と，
i＝
1
，
2
，
3
，
4
のと き，0 （
u → ¢i）
＝
maXi ∈［n｝（
v−
1（
i）
＿
u−
1（
i
）
）
≧ u−
1〔
c）
−
v−
1（
c）
＝3
とな
る．
よっ て，
こ の 場 合 にX
は 支配集
合
に は成
リ得
ない．
（
X34，
X44）
＝
（
d，
d
）
，
（
α，
の
，
（
d
，
a）
な ら ば，
U＝
［
α ，d
，b
， C］¢ X
とす
る と，
i
＝
1
，2
のと き，
σ（
u → mi）
＝
maXi ∈［n］（
v−
1（
i
）
一
Institute of Electronics, Information, and Communication Engineers
NII-Electronic Library Service
工nstitute 。f Electr 。nics，
工nf 。rmati 。n厂
and C。 unication Engineersu
−
1（
i）
）
≧ u−
1（
α）
−
v−
1〔
α）
＝
2
と なり
，
i
＝
3
，4
の と き，
σ（
U → X・）
・＝
・m ・Xi ∈〔n］（
V−
1（
i
）
一
ゼ
（
i
）
）≧
U”（
・）
−
V−
’（
a）
＝
3
ま たは，
C
（
u → x）
＝
maXi ∈（nl（
v一
1（
の
一
uTl〔
i
）
）
≧u−
1（
d
）
−
v−
1（
d）
＝
2
と な る．
よっ て，
こ の 場 合にX
は 支 配 集 合には 成 り得
ない．
（
X34 ，X44）
；
（
alC）
，
（
C，a）
な ら ば，
U＝
［
α ，C，d
，
b］¢ X
とす
ると，
，
i
＝
1
，
2 の とき
，
C
（
u → Xi）
＝
maXi ∈回（
v−
1（
i）
−
u−
1（
i
）
）≧
u−
1（
c）
−
v−
1（
c）
＝
2
と な り，
i
＝
3
，4
の とき，
0
（
u → Xi）
＝
maXi ∈國（
v−
1（
i＞
−
u−
1（
i））
≧ u−
1（
α）
−
v−
1（
の
＝
3
ま たは，
（フ（
U → X｛）
＝
maXi ∈圄（
V−
1（
i
）
−
U−
1（
i
）
）
≧U−
1（
C）
−
v−
1（
c）
＝
2
となる．
よっ て，
こ の場 合にX
は支 配 集 合には 成 リ 得 ない，
（
x34，
x44）
＝
（
c，d
）
，（
d
，c）
な らば
，
u＝
［
c，d
，α，b
］¢
X
とす
る と，
，
i
＝
1
，
2
のと き，
0 （
u → Xz）
＝
rnaXt ∈［n ］（
vTl（
i）
−
u−
1（
i）
）
≧ゼ 1（
c）
−
v一
工（
c）
＝3
と な リ，
i
；3
，
4
の とき，
0
（
u → mi）
＝
maXi ∈回（
v−
1（
i）
−
u−
i（
i）
）≧
u−
1（
c）
−
v−
1（
c）
＝
3
ま たは，
σ〔
u →＝
maXi ∈En
］（
・−
1（
i）
−
u−
’（
i）
）
≧u−
’（
d）
−
v−
’〔
d）
＝
2
と な る．
よっ て，
こ の場 合にX
は 支 配集合
には成
り得
ない．
（
x14 ，x24）
＝
（
d
，d
）
の場 合
も（
c，c）
の場 合
と同様
に し てX
は支 配 集 合とな ら ない．
（
x14，
x24）
＝
（
b，
c）
，（
c，b
）
の場合
，
u＝
［
b
， c， a，d
］≠
X
とす
ると，
i＝
1，2
の と き，
σ（
u → Xi）
＝
ma 崘∈［nl（
v−
1（
i）
−
u−
1（
i）
）
≧ u−
1〔
b
）
−
v−
1（
b
）
；3
ま た は0
（
u → Xi）
＝
maXi ∈圄＠
−
1（
i）
−
u−
1〔
i）
）≧
u−
1（
c）
−
v−
1（
c）
＝
2
となり，
i
；
3
，4
の とき，
0
（
u → Xi）
＝
maXi ∈ 回（
v−
1（
i）
−
u−
i（
i）
）
≧
u−
1（
b
）
−
v−
1（
b
）
＝
2 と な る，
よっ て，
こ の場 合
にX
は支配 集合
には 成 り得
ない．
（
Xl4，
X24）
＝（
b
，
d）
，
（
d
，
b
）
の 場合
，
U＝
［
b，
d，
α，
C］≠
X とす
る と，
i＝
1，2
の と き，
C
（
u → Xt）
＝
maXi ∈［n】（
v−
1（
i
）
＿
u−
1〔
i
）
）
≧ u−
1（
b）
一
ゼ 1（
b）
＝
3
または0
（
u → Xi）
＝
maXi ∈ ［n］（
v−
1（
i）
一
ゼ 1（
i
）
）
≧ u−
1（
d
）
−
v−
1（
d
）
＝
2
と なり
，
i
＝
3
，4
のと き，
σ（
u →勾
＝ m ・・ 、∈ ［。
】＠
−
1（
i）
−
U−
’（
i））
≧
ゼ ’（
b
）
−
v−
1（
b
）
＝
2
と な る．
よっ て，
こ の場合
にX
は支配 集 合
に は成
り得
ない．
（
X14 ，X24）
＝
（
C，d）
の場 合，
（
x34，
x44）
＝
（
α，
の な ら ば
，
u＝
［
a，b
，u〔
3
）
，u〔
4
）
1
¢
X
とす
る と，
i
＝
1
，
2
，3
，
4
の と き，0
（
u → Xi）
＝
maXt ∈圄＠
−
1（
i）
−
u−
i（
i
）
） ≧
u−
1（
α）
一
ガ 1（
a）
＝
3
ま
た は0
（
u → Xi）
＝
maXi ∈岡〔
v−
1（
i
）
−
u−
1（
i
）
）
≧ u−
1（
a）
−
v−
1（
a）
＝2
とな る．
よっ て，
こ の場 合にX
は支 配集合
に は成
り得
ない．
（
X34 ，X44）
＝
〔
C，C）
，（
a，C）
，
（
C，a）
な ら ば， Uニ
［
a，
C，
d，
b
］¢ X
と す ると，
i
＝
1，
2の とき
，
σ（
u → Xi）
＝
rnaXi ∈［n］（
v−
1（
i）
−
u−
1（
の）
≧u−
1（
a）
−
vT1（
α）
＝
2
と な り，
i
＝3
，
4
の と き，
σ（
u → X、）
−
maXi ∈［n］（
ガ 1（
i）
−
U−
’（
O
）
≧
U−
1（
・）
−
V−
’（
・）
−
2
ま た は0
（
u → mi）
＝
maXi ∈［n］（
v＿
1（
i
）
−
u−
1（
i
）
）
≧u−
1（
a）
−
v−
1（
α）
＝
3 となる．
よっ て，
こ の場 合
にX
は 支 配 集 合 に は 成 り 得 ない．
（
x34 ，x44）
＝
（
d
，d
）
な ら ば，
u＝
［
d
，c，a，b］≠ X
と す る と，
，
i
；
1
，
2
，
3
，
4
の と き，
0
（
u → Xz）
＝
maXi ∈［n］（
v−
1（
i
）
−
u−
1（
i）
）
≧ u−
1（
d
）
−
v−
1（
d
）
＝
3
ま た はC （
u → Xi）
＝
maXi ∈［n］（
v−
1（
i）
−
u−
1（
i））
≧u−
1（
c）
−
v−
1（
c）
＝
2
と な る．
よっ て，
こ の場合
にX
は支
配集合
に は成り得
ない．
（
x34，
x44）
＝
（
α，
d
）
，
（
d，
a）
な らば
，
u＝
［
a，d
，c，b
］≠X
とす
ると
，
i；
1，
2
のと き，
（フ（
u → x，
i）
＝
rnaXi ∈圄（
v−
1（
i）
＿
u一
工〔
i）〉
≧
u
