3-連 絡対木 グラフのクラスを特徴付ける理論 の構築 に関する研究 篠田 座 司 中央大学理工 学部 教 授 1.は じめ に グラフの 閉路 を含 まない 要素数最 大 の枝集合 を木 とい う。 グラフの木 に含 まれな い枝集合 を その木 と対 をなす 補木 とい う。木 となる補木が存在するようなグラフを対木構造 を持 つ グラフ、 略 して対木 グラフとい う。対木 グラフは枝 を共有 しない丁度 二 つの本 で枝集合が被服 されるグ ラフの こ とであ る。対木 グラフを真部分 グラフと して含 ない対木 グラフを素 であ る ( 極小 であ る、最小 であ る、 または強既約 である) と い う。対木 グラフに着 目 した最初 の 人 は H . B . L e e で あ る。彼 は ″ ″IEEE H.B.Lee′ On the difFering abilities oF RL structures to realize natural frequel■ cies′ T r a n s . C i r c u i t T h e oCrTy-′ 12′ 3′ 1965 p.365′ にお い て対木 グラフが 回路構成論上特別 な役割 を果 たす ことを指摘 した。 そ の後 、1 9 6 8 年 になって 、 岸 、梶谷 : 最 大距離 にあ る 2 つ の木 につい て 、電子通信学会創立 5 0 周 年記念全 国大 会、 論 文番号 3 0 、 1 9 6 7 岸 、梶 谷 : リ エ アグラフにお ける最大距 離 にあ る 2 つ の 木、電子通信学 会論文誌 、 5 ユ ー A、 5、 p. 196, 1968 にお い て 、任意 の グラフが あ る基準 の もとで三 つ の グラフに分割 され、その三 つ の グラフの ひ とつ が 対木 グラフであ るこ とが 明 らか に された。 また、同時 に 大 附、石崎 、渡部、梶 谷 、岸 : 電 気 回路 の トポ ロ ジ的 自由度 、電子通信学会創立 5 0 周 年 記念全国大 会、論文番号 3 1 、 1 9 6 7 大 附、石崎 、渡部 : 回 路網解析 と位相幾何学 自由度 、電子通信学 会論文誌 、 5 1 - A 、 6、 p. 238, 1968 にお い て 、回路 の 混合解析 にお ける最小変数集合 の選択 の 多様性 が回路 の接 続構 造 を与 えるグ ラフの岸 ・梶 谷 の 3 分 割 ( 基本分割 といわれ る) の 対木 グラフ部分 か ら発生す るこ とが 明 らか に された。 そ して 、 梶 谷 : グ ラフの基 本分害J に関す る二 、 三の性 質、昭和 4 5 年 電気四学会連合大 会、基礎 理論 、論文番号 5 4 、 1 9 7 0 小 沢 : あ る最小 グラフについ て 、昭和 4 5 年 電気 四学会連合大会 、基礎理論 、論文番号 55、 1970 にお い て 、次 の よ うな性 質 1 ) と 2 ) が 明 らか に された。 1 ) 素 で な い対木 グラフに含 まれ る 任 意 の二 つ の 素 な対 木部分 グラフは枝 を共 有す ることもな く、点 は共有す る と して も 1 点 だ け であ る。 2 ) 素 で ない対木 グラフに対 して、そのす べ ての素 な対 木部分 グラフを短絡 除去 して - 7 - 得 られるグラフは対木 グラフで、素でない対木 グラフに対 して、その ような短絡除去 を繰 り返 し適用す ると、対木 グラフの系列 とその系列 の各対木 グラフにおけ るすべ ての素な対木 グラフ が得 られ、素で ない対木 グラフは素な対木 グラフに分解 される。 この結果、対木 グラフの理論 で残 された重要な問題 は、 「 素な対木 グラフのクラスは、Tutteの3-連 結 グラフの特徴付けの ような意味 で 、 どの ように特徴 づ け られるか」 とい う問題 となった。 しか し、それを解 く鍵 と なるアイデ アが発見 されない まま、 20年 以上 の年月が過 ぎ去 つた。 ー ー 他方、情報通信 ネ ッ トワ クの分野で は、高品質高信頼サ ビス を保証す る立場 か ら、階 ー ー 層化 された情報通信 ネ ッ トワ クの、特 に上層部 ネ ッ トワ クの接続構造 に閉路構造 を組み込 む ことがなされて きている。 しか しなが ら、閉路構造 を組み込む として も、経済的観点 か ら、 で きるだけ粗 な接続構造 の もとで の信頼度 の確保 が問題 となる。 この問題 に対 して は、 これ ま で 、連結度 を与 えてネ ッ トワー クを生成す る方法 を設計す るなどの研究がなされて きた。筆者 は、対木 グラフを接続構造 とす るネッ トワー クが、運結度 では、連結度 3以 下であるが、任意 の局 か ら全 局へ の (回線 を共有 しない とい う意味 で)同 時 に 2重 の通信 を保証す るとともに、 運結度 が 3(ま たは 2)の 場合 は、任意 の 2局 間 に (途中の局 を共有 しない とい う意味 で)同 へ 時 に 3(ま たは 2)重 の通信 を保証す ることを考慮 し、上記 の信頼度確保問題 の接近 として、 ネ ッ トワー クの接続構造 として対木 グラフに着 目す ることに した。 素 な対木 グラフのクラスはどのようなもの となるか」 とい それ は、必然的 に先 に述べ た 「 う特徴付 け問題 に挑戦す る ことを意味 した。それで、対木 グラフはそれ 自体 で 閉路 を形成す る 枝 (自己閉路枝 とい う)も それ 自体 でカツ トセ ッ トを形成す る枝 (自己 カッ トセ ツ ト枝、 また は橋 とい う)を 含 まないことと、対木 グラフの どの非可分成分 も2-連 結 または 3-連 結 であ る対本部分 グラフで、素 な対木 グラフは 2-連 結 か 3-連 結 である ことを考慮 し、研究助成 申 素な 請時点 では、 (問題 が難 しか、 どうかが判明 しなか ったため)、 その問題 の部分問題 の 「 3-連 結対木 グラフの クラスは どのよ うな もの となるか」 とい う問題 に焦点 を合 わせ 、標題 の よ うな研究助成 の 申請 を行 った。 標題 の 3-連 結対木 グラフの クラスの特徴付 けは、梶谷、小沢 の結果 を考慮す ると、素 な 3-連 結対木 グラフの クラスの特徴付 け に帰着 される。今回の研究 では、後者 の特徴付 けの間 素な 3-運 結対木 グラフは 4個 の点 か らなる車輪 グラフ (比 と表す)自 体 か、 題 に対 して、 「 またはそ の車輪 グラフⅥlから (この報告書 で定義す る)T― 操作 とい う単純 な演算 を繰 り返 し 適用 して生成 されるグラ フである」 とい う美 しい解答 を得 ることがで きた。 素な 2-連 結対木 グラフは 2個 の枝 か らなる閉路 (C2と表 また、 この研究 との関連 で、 「 す)自 体 か、 またはい くつ かの素な 3-連 結対木 グラフか ら (この報告書 で定義す る)U― 操 作 とい う単純 な演算 を繰 り返 し適用 して生成 されるグラフである」 とい う命題 も証明で きた。 閉路 C2以外 の素な対木 グラフは車輪 グラフ叱 、 この ことは、上記 の解答 との組 み合わせで、 「 ならびにその車輪 グラフV'1にT― 操作 を繰 り返 し適用 して得 られるグラ フに対 して、U― 操作 を繰 り返 し適用 して生成 されるグラフである」 とい う重要 な命題 を証明 した ことになる。また、 さらに梶谷、小沢 の結果 の内容 を組 み合わせ ると、対木 グラフの クラスの特徴付 け理論 が、 こ -8- の研 究 に よって完成 した こ とになる。本研 究助成 は 、そ の意味 にお い て 、大変 な機 会 を筆者 に 与 えて くれ た こ とにな り、深 く感 謝す る次 第 であ る。 なお、定義 な しに用 い られ る連絡度 、車輪 グラフな どの用語 につい ては 、 グラフ理 論 の 適 当 な専 門書 を参照 された い 。 2 素 な 3-連 結対木 グラフの特徴付 け 命題 1:4-連 結 であ る素 な対 木 グラフは存在 しない 。 証 明 in個 の点 とm個 の枝 を持 つ 4-連 結対木 グラフの次数 kの 点 の 数 を nkと 表す。そ の とき、 m=[4n4+5n5+6n6+.… ≧[4n4+4n5+4n6+.… … ,十 p(n―n4 n5 n6 ・…np_1)]/2 .+4(n―n4 n5 n6 ・…… np_1)]/2 ≧[4n]/2=2n が成 り立 た つ が 、対木構造 であ るこ とか ら、m=2(n-1)で なければな らない か ら、矛盾 とな り、命題が成 り立 つ 。〃 これ に よ り、連絡対木 グラフは高 々 3-連 結 であ るこ とになる。そ して 、自己閉路枝 は つ ね にす べ ての 補木 に含 まれ、 また双 対 的 に 自己 カ ッ トセ ッ ト枝 はつ ね にす べ ての 木 に含 まれ なけ れば な らな い か ら、運結対木 グラフは 、 2-連 結 で ない ときには 、 2-連 結 か 3-連 結 であ る 対木部分 グ ラフをカ ッ ト点 (その点 とその点 に接続 され る枝 を除 くと、 グラフの 連結度 が増加 す る点)で 接続 されたサ ボテ ンの よ うな形 を した グラフ となる。 また、 素 な対木 グラフは、素 で あ る こ との 定義 か ら、 2-連 絡 か 3-連 結 となる。点 の 数 が 6以 下 の素 な対木 グ ラフをす べ て示す と、図 1に 示 され るグラ フとなる。図 1(a)のグラフは点 の 数 が 一 番少 な い 2-連 結対木 グラフで 、 2個 の 枝 か らなる 閉路 C2と い われ る もので あ る。また、図 1● )の グラフは点 の 数 が 一 番少 な い 3-連 結対木 グラフで 、4個 の枝 か らなる車輪 グラフW4と い われ る もので あ る。こ れ らを考慮 す る と、素 で ない 3-連 結対木 グラフは素 な 3-連 結対木 グラ フを真部 分 グラフ と して含 まなければ な らない か ら、点 の数が最 も少 ない 素 で ない 2-連 結対 木 グラフは 図 2(a)と な り、点 の 数 が 最 も少 な い 素 で ない 3-連 絡対木 グラフは同図(b)となる。 次 に、 グラフGの あ る枝 x=(a,b)を二 つ の 直列枝 y=(a,の と Z=(d,b)で置 き換 える こ とを そ の枝 xの 2分 割 といい 、点 dを そ の枝 の 2分 割 に よる挿入点 とい う。グラ フGに 対 して、あ る枝 x=(a,b)を2分 割 し、その 2分 割 による挿入点 と他 の点 の 間 に、並 列枝 が生成 されない よ う に、枝 を 1個 付 加す る操作 をT― 操作 とい う (図 3を 参照)。 この とき、 4個 の 点 か らなる車 輪 グラフW4以 外 の任意 の車輪 グラフはW4か らT― 操作 で得 られ るこ とが 、容易 に示す こ とが で きる。 また、容易 に証明 され る こ とであ るが 、次 の 命題 が成 り立 つ 。 命題 2: 3-連 結対木 グラフにお い て T― 操作 の逆が可能 で あるため の必 要十分条件 は 、 -9- (b) (a) (d) (C) (g) 図 1 点 の数 が 6以 下 の素 な対木 グラ フのす べ て (a) (b) 図 2 点 の数が最 も少な い素 でない 2 - 連 結 と 3 - 連 結 の グラ フ → 図 3 T一 - 1 0 - 操作 一 次数 3 の 点 が 存在 し、その点 に隣接 す る点 の つ の次 数 が 4 以 上 で 、残 りの 2 点 ( 仮に a 、b と表 す) の 次 数 が ともに 3 以 上 であ り、そ の 2 点 a 、b は 互 い に隣接 しない ことで ある。 一 この命 題 か ら、 T 一 操作 の逆が適用 され るため には 、次数 4 以 上 の点 がす くな くとも つ 含 まれ るこ とが 必 要 となる。 これ に関連 して、次 の命題 が成 り立 つ 。 命題 3 : す べ ての 3 - 連 結対 木 グラフは次数 3 の 点 をす くな くとも4 個 含 み 、W 4 以 外 の 3 - 連 結対木 グラフは次 数 4 以 上 の 点 を少 な くとも 1 個 含 む。 証 明 i n 個 の 点 とm 個 の 枝 を持 つ 3 - 連 結対木 グラフの次数 k の 点 の 数 を n k と 表す 。 そ の とき、 m=2(n-1) =[3n3+4n4+5n5+.… ,十 np_1)]/2 …… p ( n ―n 3 n 4 n 5 ・ … np‐ n 3 中n 4 n s ―. … ≧[ 3 n 3 + 4 n 4 + 4 n 5 + . . . . + 4 ( n … 1)]/2 ≧[ 3 n 3 + 4 ( n ―n 3 ) ] / 2 とな り、 これか ら n 3 ≧ 4 の 関係 を得 る。 したが って 、す べ ての 3 - 連 結対木 グラフは次数 3 の 点 をす くな くとも4 個 含 む。次 に、 3 - 連 結対 木 グラフに次数 4 以 上 の点 が 含 まれ ない と した ら、上 の 関係 にお い て等号 が成 り立 ち、そ の グラフと しては W 4 以 外 に存在 しな い こ とになる。 したが って 、 W 4 以 外 の 3 - 連 結対木 グラフは次数 4 以 上の点 を少 な くとも 1 個 含 む。〃 注 目す べ き こ とは 、この命題 に よって 、W 4 以 外 の 3 - 連 結対木 グラフに次数 4 以 上 の点 が 一 必 ず含 まれ 、そ の よ うな点 の す くな くとも つ に対 して、隣接 す る次 数 3 の 点 が存 在す るこ と が保証 され る こ とであ る。 そ して、命題 2 と 3 を 考慮 す る と、次 の定理 が 証 明 され る。 定理 1 : 素 な 3 - 連 結対木 グラフはW 4 で あ るか 、W 4 か らT 二 操作 を繰 り返 し適用 して得 られ るグラ フで あ る。 この定理 の証 明 の 詳 しい 記述 は学 会 での研 究発表 の機 会 に報告す る。 ここで は 、証明 の概 略 を説明 してお く。 まず 、W 4 以 外 の 3 - 連 結対木 グラフG を 考 える。その とき、命題 3 か ら、 一 C に は次数 4 以 上 の 点 が必ず 含 まれ、その よ う な点のす くな くとも つ に対 して、隣接 す る次 数 3 の 点 が存在す る。 T 一 操 作 の逆操作 を行 う ことがで きる ときには 、次数 4 以 上 の点 に隣接 一 す る次 数 3 の 点 が 1 個 消去 され 、次数 4 以 上 の 点 の つの次数 が 1 だ け減 少す るこ とになる。 この こ とを考慮 す る と、命題 2 か ら、次数 4 以 上 の点 に隣接 す る次数 3 の 点 で 、 T 一 操作 の 逆 操 作 に よって 消去す る こ とので きな い もの は 図 4 の ( a ) と●) のい ず れかの点 d の 場 合 とい う こ とになる。 ( a ) の場合 は点 d に 隣接 す る 3 点 a 、b 、c の どの次 数 も4 以 上 であ る場 合 で 、W 4 が 真部分 グラフ と して含 まれ るこ とにな り、 G が 素 で ある こ とに反す るこ とになる。 また、 ●) の 場合 は点 d に 隣接 す る 3 点 a 、b 、c の うち点 a 、b の 次数 が 3 で 、点 c の 次 数 が 4 以 上であ る場 - 1 1 - 合 で 、図 4 ( c ) のよ うに表 される場合で、点線 で 囲 まれた部分が 3 - 連 結対木部分 グラフであ る こ とが 証 明 され、G が 素 であ るこ とに反す るこ とになる。この よ う に、W 4 以 外 の 素 な 3 - 連 結 対木 グラフにはつ ね にT 一 操作 の 逆操作 が 適用 で き、最終的 にW 4 に 帰着 され、T ― 操作 の逆操 作 が 適用 で きな い の は 、 3 - 連 結対木 グラフが素で ない ときであ るこ とにな り、定 理 は証 明 さ れ る。 梶 谷 、小沢 の結果 と組 み合 わせ る と、 この 定理 に よって 、 3 - 連 結対木 グラフの クラスの 特徴付 けが完成 した こ とになる。 これが標題 の研 究 に対す る解答 である。 3 あ とが き ― 補 足込 み この研 究 で 、定理 1 を 証 明す るこ とによって 、 3 - 逗 結対木 グラフの クラスの 特徴付 け、 す なわ ち研 究課題 の解決 に成功 した。まえが きに触 れたが 、実 は 、この研 究 を推進す る うちに、 2 - 連 結対 木 グラ フの クラスの特徴付 けに も成功 す るこ とにな り、対木 グラフの クラスの特徴 付 け理論 が この研 究助成 を機 に完成す るこ ととなった。以下 に、 2 - 運 結対木 グラ フの クラス の特徴付 け につい ての成 果 を概 説 してお く。 命題 4 : 3 個 以上 の点 を持 つ 二つ の 2 - 連 結 または 3 - 連 結対木 グラフG l と G 2 に 対 して、G l の 任 意 の枝 ( a , b ) を 開放 除去 して得 られ るグラフを G 子 と し、G 2 の 任意 の枝 ( c , d ) を 開放 除去 して得 られ るグラフを G を とす る。次 に、G t と G なに対 して、a と c を 一致 させ る と 一 致 させ る ことに よって られるグラフを G と す る。 この とき、 G は 2 - 連 同時 に b と d を 得 結対木 グラ フであ る。 ここ に、G l と G 2 か らG を 得 る操作 を u ― 操作 とい う ( 図 5 を 参照) 。 この証明 はほほ 自明であるので、省略す る。図 1の oの グラフは同図①)の車輪 グラフV路の二 つ の コ ピーか ら U― 操作 で得 られる。 この U― 操作 の逆 は 自明ではない。 4個 以上の点 を持 つ 2-連 結 であるが 3-連 結 でない グラフGは つ ねに次の性 質 1)と 2)を 満 たす 2点 aと bを 持 つざ 1) 2点 aと bを 、それ らに接続す る枝 とともに、除去 して Gか ら得 られるグラフは連 結 でない。 2) Gに は、そ の 2点 aと bの みを共有す る 2個 の連結部分 グラフで、それぞれが 3点 以上 を持 つ ものが存在す る。 ここに、その よ うな二 つ の道結部分 グラフをGIと Gをと表す とき、その 2個 の点 aと bを Gに おけるGlと Gなの 2点 分離集合 とか、単 に 2点 分離集合 とい う。また、G子とGなをGの 点 aと b を 2点 分離集合 とす る相補的 2-端 子部分 グラフとい う。 G十 をGに おけるGな の補 グラフと いい、Gな をGに おけるGtの 補 グラフとい う。Gに おいてGなを一つ の新 しい枝 xで 置 き換 え ることによって得 られるグラフをGlと 表 し、GIを 一つ の新 しい枝 xで 置 き換 える ことによっ て得 られるグラフを G2と 表す。この とき、Gが Glと G2か ら、置 き換 えた枝 に着 目 し、U― 操 -12- (b) (a) 図 4 (C) 次数 4 以 上の点 に隣接す る次数 3 の 点で, T ― 操作 の逆 操作 によって消去す る ことができな い もの ( 点 d ) の 場合 図 5 U― 操作 ア (C) (b) (a) 図6 同 じ 2点 分離集合を持 つ相補的 2 一端子部分 グラフの対が複数存在す る場 合 -13- 作 に よって復 元 され る とい う意味 で 、置 き換 えた枝 をそれぞれGを とG十 の代表枝 とい う。 ここ に、Glを Gの Gを 簡約 グラフといい 、G2を Gの GI簡 約 グラ フといい 、略 して、Glと G2を GIと Gちの対 をなす 簡約 グラフ とい う。ここで 注意す べ きは、同 じ2点 分離集合 を持 つ相補 的 2-端 子部 分 グラフの対 が 複 数存在す る場合 があ るこ とであ る。図 6(a)のグラフは点 aと bを 2点 分 離集合 と して持 つ 2-連 結対木 グラフであ る。 この グラフに対 して、同図●)の グラフの対 と同 図 oの グラフの対 は ともに点 aと bを 2点 分離集合 とす る相補的 2-端 子部分 グラフであ るが、 前者 の対 をなす グラフの対 をなす簡約 グラフは どち らも対木 グラフで ない が、後者 の対 をなす グラフの対 をなす 簡約 グラフは どち らも対木 グラフであ る。 命題 5: 3個 以上 の 点 を持 つ二 つ の素 な 2-連 結 または 3-連 結対木 グラ フGlと G2に 開放 除去 して得 られ るグラフを Gtと 対 して、Glの 任意 の枝 (a,b)を を 開放 除去 して得 られ るグラフを Gな とす る。次 に、Glと Gをに対 し、G2の 任意 の枝 (c,の して、aと cを 一 致 させ る と同時 に bと dを 一 致 させ るこ とに よって得 られ るグラフを Gと す る。 この とき、 Gは 素 な 2-連 結対 木 グラフであ る。逆 に、 Gを 4個 以上の点 を持 つ 2-連 結 であ るが 3-追 結 で な い 素 な対木 グラフとす る。 この とき、 Gの 各 2点 分離集合 に関 して相補的 2-端 子部分 グラフGI とGなが 一 意 的 に存在 し、それ らの 派 生 グラフはつ ね に素 な 2-連 結 または 3-連 結対木 グラフ となる。 この 命題 の証 明 は学 会 で の研究発表 の機会 に報告す る。 この 命題 の結果、次 の 定理 が 得 ら れ る。 定理 2: 素 な 2-違 結対 木 グラフは 2個 の枝 か らなる閉路 C2自 体 か 、 または (い くつ か の )素 な 3-連 結対木 グラフか ら U― 操作 を繰 り返 し適用 して生成 され るグラフで あ る。 そ して、 この定理 と定理 1を 組 み合 わせ る と、 2個 の枝 か らなる閉路 Q以 外 の素 な対木 グ るグ ラフは車輪 グラフVレ 1、 な らびにその車輪 グラフV'1にT― 操作 を繰 り返 し適用 して 得 られ ラフに対 して、U― 操作 を繰 り返 し適用 して生成 され るグラフであ る とい う結果 を得 る。 また、 さらに梶谷 、小沢 の結果 の 内容 を組 み合 わせ る と、対木 グラフの クラスの特徴付 け理論 が、 こ の研 究 に よって完成 した こ とになる。 最後 に、本研 究助成 に対 し、深 く感謝す る次第 であ る。 - 1 4 -
© Copyright 2024 ExpyDoc
