文献

J-GLOBAL ID：201102256413586946   整理番号：11A0760211

Branching trees cliqueにおける部分重み付け関数の最節約拡張

A study on most-parsimonious extensions of partial assignments on a branching trees clique

著者 (1件)： 宮川幹平 (東海大学福岡短大)
資料名： 東海大学短期大学紀要  (Proceedings of the Tokai University Junior Colleges)
号： 44  ページ： 69-74  発行年： 2011年03月22日 
JST資料番号： X0158A  ISSN： 0386-8664  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 最節約拡張(MPE)問題ではグラフとその各頂点に対する部分重み付け関数σが与えられ,その定義域をグラフの頂点集合全体に拡張した関数(σの拡張)の中でグラフの長さを最小化するものを求める。本論文では,進化生物学における進化系統樹最節約復元問題の1つとして,入力を木に限定したMPE問題に関する研究成果を概説し,ただ一つの完全グラフといくつかの木からなるグラフ(Branching Trees Clique,以下BTC)の特徴付けを行った。まず,完全部分グラフK_mの各頂点に対して実数値を対応させる重み付け関数λのときのK_mの長さL_λ(K_m)の最小化と,各木T_uiの長さL(T_ui)の最小化とのバランスの考え方がポイントとなる。そこで,BTCであるグラフGとσが与えられたときG_σの任意の拡張λがMPEであるための必要条件を示した。また,G=(K_m,T_u1,T_u2,...,T_um)とσが与えられたとき,有限木T_uiにおける各頂点u_iの特性区間をI(u_i)とすると,∩I(u_i)≠Φ(1≦i≦m,deg(u_i)≧m)を満たすBTC G_σについてMPEの特徴を示した。

シソーラス用語： *クリーク ,  *グラフ理論 ,  問題 ,  重みづけ ,  木【グラフ】 ,  完全グラフ ,  必要条件 ,  重み関数 ,  *最小化問題
準シソーラス用語： *最節約拡張問題 ,  重み付け関数

分類 (2件)： グラフ理論基礎  (IA02020S) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (3件)： 重み付け関数 ,  節約 ,  拡張