成 瞑 大 学 理 工 学 研 究 報 告
J.Fac.Sci.Tech.,SeikeiUniv.
Vol.52No.2(2015)pp.11-12
球 面 上 の 四角 形 分 割 の マ イナ ー 関 係 に つ い て
松 本
直 己*
Minorrelationfbrquadrangulationsonthesphere
NaokiMATSUMOTO*
ABSTRACT:Wepresentaminorrelationforquadrangulationsonthesphere.Itisknownthatminor
operationsmighttransformaquadrangulationintoanothergraphwhichisnotaquadrangulation.We
introducenewtransformationsforquadrangulations,wheretheyconsistofasequenceofminoroperations.
ThenwefindasequenceofquadrangulationsG=GO,Gl,G2,_.,Gk=C4(a4-cycle),whereGi+lis
obtainedfromGibyanapplicationofoneofouroperations.
Keywordsgraphs,quadrangulations,minor,generatingtheorem
(受 理 年.月 日:2014年7.月)
1.は じ め に
グ ラ フ ・マ イ ナ ー 理 論 と は,Robertson-Seymourに よ っ
て 体 系 化 さ れ た グ ラ フ 理 論 に お け る 重 要 な 理 論 の ひ と つ
で あ る.Robertson-Seymourに よ る 計20編 以 上 か ら な る
論 文 集GraphMinorsに お い て,彼 ら は 数 々 の 重 要 な マ イ
ナ ー に 関 す る 定 理 を 証 明 し て い る.そ の 中 で も 特 に 有 名
な の は,「マ イ ナ ー 関 係 に 関 して 閉 じて い る グ ラ フ の 集 合
は,有 限 個 の 禁 止 マ イ ナ ー に よ っ て 特 徴 付 け ら れ る 」 と
い う定 理 で あ る.こ れ に よ り,様 々 な グ ラ フ の ク ラ ス に
お い て,禁 止 マ イ ナ ー に よ る 特 徴 付 け や マ イ ナ ー 操 作 に
よ る グ ラ フ の 生 成 定 理 な ど が 証 明 さ れ て き た.し か し,
一 般 に マ イ ナ ー 操 作 は グ ラ フ の 染 色 数 を 保 存 しな い こ と
な ど か ら,グ ラ フ の マ イ ナ ー 操 作 は 二 部 グ ラ フ に 対 して
は あ ま り相 性 が 良 く な い と 考 え ら れ て き た.実 際,二 部
グ ラ フ の マ イ ナ ー に 関 し て は あ ま り研 究 が 進 ん で い な い.
一 方 で
,あ る 閉 曲 面S上 に 辺 の 交 差 な く 描 く こ と が で
き る グ ラ フ 全 体 の 集 合 は,マ イ ナ ー に 関 して 閉 じて い る
こ と が 知 ら れ て い る.し た が っ て,こ れ ま で に 平 面 的 グ
ラ フ の 特 徴 づ け と し て 有 名 なKuratowskiの 定 理 を は じ め
と す る様 々 な 曲 面 上 の グ ラ フ の マ イ ナ ー 関 係 に 関 す る 定
理 が 証 明 さ れ て き た.し か しな が ら,一 般 の グ ラ フ と 同
様 に,曲 面 上 の 二 部 グ ラ フ に 関 す る研 究 は ほ と ん ど さ れ
*:理 工 学 部 情 報 科 学 科 助 教(naoki
-matsumoto@st
.seikei.ac.jp)
て こな か っ た.
そ こで我 々 は,二 部 グ ラ フで あ る球 面 上 の 四 角 形 分 割
に お い て,マ イ ナ ー操 作 を組 み合 わせ て 得 られ る新 た な
局所 変 形 を 四角 形 分 割 に 対 して 定 義 し,そ れ らの 変 形 に
よる球 面 四角 形 分 割 に お け るマ イ ナ ー 関係 を発 見 した.
2.準 備
グ ラ フGと は,有 限集 合(頂 点集 合)Vと
そ の 二 元 部 分
集 合 族(辺 集 合)Eと の組 で あ る 。球 面 上 に辺 の 交 差 な く
描 かれ た各 面 が4一 サ イ クル グ ラ フC4(図1)で
囲 ま れ て
い る グ ラ フ の こ とを 四角 形 分 割 と呼 ぶ(図2).ま
た,任
意 の 四角 形 分 割 は 二部 グ ラ フで あ る こ とが 知 られ て い る
こ とか ら,以 降,四 角 形 分 割 の頂 点 を黒 と 白で 図1,2の
よ うに塗 り分 け て お く.
口
図
図14一 サ イ ク ル グ ラ フC4図2四 角 形 分 割 の 例
グ ラ フ の マ イ ナ ー 操 作 と は,図3で 示 さ れ る 「辺 の 除
去,辺 の 縮 約,孤 立 点 の 除 去 」か ら な る 三 つ の 変 形 操 作 で
あ る.あ る グ ラ フGか ら こ れ ら の 操 作 の 連 続 に よ っ て 異
な る グ ラ フHに 変 形 で き た と き,HはGの マ イ ナ ー で あ る
一11一
成 践 大 学 理 工 学 研 究 報 告
Vol.52No.2(2015.12)
と い う.
〉 一 く ゆ 〉
く
〉一く ゆ×
●
・レ
・レ
図3マ
イ ナー 操作(上 か ら辺の 除去,縮 約,孤 立 点 除去)
3.主 結 果
・レ
図5(上 か ら)2-vertexremovalとhexagonalcontraction
第1章 で 述 べ た よ うに,こ れ ま で グ ラ フ ・マ イ ナ ー 理
論 で は 二 部 グ ラ フ の マ イ ナ ー 関 係 に つ い て の 研 究 が あ ま
り さ れ て こ な か っ た.そ こ で 我 々 は ま ず 二 部 グ ラ フ の ひ
と っ で あ る 四 角 形 分 割 全 体 の マ イ ナ ー 関 係 を 明 ら か に し
よ う と 考 え た.し か し な が ら,図3か ら も 明 ら か な よ う
に,一 般 に マ イ ナ ー 操 作 は 与 え ら れ た グ ラ フ が 四 角 形 分
割 で あ る こ と を 保 存 しな い.ま た,任 意 の 四 角 形 分 割 は
面 縮 約(図4)と い う減 少 操 作 に よ りC4に 変 形 で き る こ
と が 知 ら れ て い る が[2],面 縮 約 は 一 般 に は マ イ ナ ー 関 係
を 保 存 し な い こ と も わ か っ て い る[1].
ゆ
図4面
縮 約
そ こ で 我 々 は,四 角 形 分 割 の マ イ ナ ー 関 係 を 考 え る た
め,四 角 形 分 割 で あ る こ と を 保 存 す る よ うな 二 つ の 新 し
い 変 形(hexagonal-contraction,2-vertexremoval,図5)を
定 義 し,任 意 の 四 角 形 分 割 が こ の 二 つ の 変 形 に よ っ てC4
に 変 形 で き る こ と を 証 明 し た.(こ の 二 つ の 変 形 が 図3で
表 し て い る 三 つ の マ イ ナ ー 操 作 を 何 回 か 適 用 す る と 得 ら
れ る こ と は 比 較 的 簡 単 に 分 か る.)
定 理1(Bauetal.[1]).任 意 の 四 角 形 分 割Gに 対 し,以 下
の 二 つ の 条 件(i),(ii)を 満 た す 四 角 形 分 割 の 列G-Go,Gl,
G2,...,Gk-C4が 存 在 す る 。
(i)任 意 のi<jに つ い て,GjはGlの マ イ ナ ー で あ る.
(ii)Gi+1はGiか らhexagonalcontractionか2-vertexremovalに
よ っ て 得 ら れ る.
この 定理 に よっ て 四角 形 分割 全 体 に 対 し,ひ とつ の マ
イ ナ ー 関係 を 定 め る こ とに成 功 し,二 部 グ ラ フに お け る
グ ラ フ ・マ イ ナ ー理 論 の構 築 に 貢 献 す る こ とが で きた.
今 後 は,本 定理 の他 の 曲 面 へ の 拡 張 も含 め た 曲面 上 の 二
部 グ ラ フ に お け るマ イ ナ ー 関係 に 関 す る理 論 を よ り発 展
させ て い き た い と考 え て い る.
参考文献
[1]Minorrelationsfbrquadrangulationsonthesphere,S.Bau,
N.Matsumoto,A.NakamotoandL.Zheng,toappearin
GraphsandCombinatorics.
[2]Diagonaltransformationsofgraphsonclosedsurfaces,
S.NegamiandA.Nakamoto,Sci.Rep.YbkohamaNat.
Univ.,SecI,40(1993)71-97.
一12一
