翻訳と辞書
Words near each other
・ 木内荘
・ 木内裕也
・ 木内裕子
・ 木内貴史
・ 木内道祥
・ 木内酒造
・ 木内重四郎
・ 木内鶴彦
・ 木刀
・ 木刀による剣道基本技稽古法
木分解
・ 木切れ
・ 木刈
・ 木刈中学校
・ 木刈小学校
・ 木前町
・ 木剣
・ 木割機
・ 木化
・ 木匠マユリ


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

木分解 : ミニ英和和英辞書
木分解[きぶんかい]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [き]
 【名詞】 1. tree 2. wood 3. timber 
: [ぶん, ふん]
  1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1
分解 : [ぶんかい]
  1. (n,vs) analysis 2. disassembly 

木分解 : ウィキペディア日本語版
木分解[きぶんかい]

グラフ理論において、木分解とはグラフからへのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。
機械学習では、木分解はjunction treeclique treejoin treeとも呼ばれ、確率伝搬法制約充足問題クエリ最適化:en:matrix decompositionのような問題で重要な役割を果たす。
木分解の概念は最初ににより導入された。後ににより再発見され、以降他の多数の研究者たちに研究されている。〔 pp.354–355〕
==定義==
直観的には、木分解は与えられたグラフ''G''の頂点をある一つの木の部分木として表現する。元のグラフ''G''において2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、''G''は部分木達の交差グラフ部分グラフをなす。交差グラフそのものはである。
それぞれの部分木はグラフの頂点に木のノードの集合を割り当てる。このことを形式的に定義すると、木のノードひとつひとつを、それに関連付けられたグラフの頂点の集合として表現する。そのため、グラフ''G'' = (''V'', ''E'')が与えられたとき、木分解はペア(''X'', ''T'')である。ここで、''X'' = は''V''の部分集合族で、''T''は頂点が''V''の部分集合''X''''i''であるような木であり、以下の性質を満たす:〔 section 12.3〕
# 全ての集合''X''''i''の和集合は''V''に等しい。つまり、それぞれの頂点は少なくとも一つの木のノードに割り当てられている。
# グラフの各辺(''v'', ''w'') に対して、''v''と''w''の両方を含む部分集合 ''X''''i'' が少なくとも一つ存在する。つまり、グラフの中で頂点が隣接するのは対応する部分木が共通のノードを持つ場合に限られる。
# ''X''''i'' と ''X''''j'' が両方とも頂点''v''を含む場合、''X''''i'' と ''X''''j'' の間の(一意な)パスに含まれる全てのノード''X''''k''も''v''を含む。つまり、''v''に関連付けられたノードたちは''T''の連結な部分集合をなす。これはcoherenceや''running intersection property''としても知られている。これは、「X_i, X_j, X_kがノードで、X_kX_i から X_jへのパス上にあるならば、X_i \cap X_j \subseteq X_kである」という条件と同値である。
木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。
台となる木がであるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは道幅として知られている。
木幅''k''の木分解(''X'', ''T'' = (''I'', ''F''))は、\forall i \in I : |X_i| = k + 1\forall (i, j) \in F : |X_i \cap X_j| = kを満たすとき''smooth''であるという。〔.〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「木分解」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.