木分解を生成するためのアルゴリズム
E.pojken
ツリー分解を構築したい：http：//en.wikipedia.org/wiki/Tree_decompositionそして私は弦グラフと完全な除去順序を持っています。私は前のスレッドで与えられたアドバイスに従います、すなわち：
弦グラフの非素敵な（一般的な）ツリー分解を構築するには：完全な除去順序を見つけ、最大クリークを列挙し（候補は頂点とその後に表示される隣接物です）、各クリークをとして使用します分解ノードを作成し、交差する順序で次のクリークに接続します。
ただし、これは機能せず、理由がわかりません。次の例を考えてみましょう。
完全な除去順序：
['4', '3', '5', '7', '6', '2', '0', '1']
弦グラフ：
木分解：
私はPythonを使用しており、現在のアルゴリズムは次のとおりです。
T=nx.Graph()
nodelist=[]
for i in eo:
vertex=str(i)
bag=set()
bag.add(vertex)
for j in chordal_graph.neighbors(str(i)):
bag.add(str(j))
T.add_node(frozenset(bag))
nodelist.append(frozenset(bag))
chordal_graph.remove_node(str(i))
for node1 in range(len(nodelist)):
found=False
for node2 in range(node1+1,len(nodelist)):
if found==False and len(nodelist[node1].intersection(nodelist[node2]))>0:
T.add_edge(nodelist[node1],nodelist[node2])
found=True
nx.draw(T)
p.show()
ここeoで、は完全な順序のリストであり、「chordal_graph」はのグラフオブジェクトですnetworkx。
デビッドアイゼンスタット
それが私の（結局のところ悪い）アドバイスでした。ツリー分解には、最大ではないクリークがいくつかあります。つまり、{2、0、1}、{0、1}、および{1}です。候補クリークのリストは
{4, 5, 6} (maximal)
{3, 2} (maximal)
{5, 6, 2, 0} (maximal)
{7, 2, 1} (maximal)
{6, 2, 0, 1} (maximal)
{2, 0, 1} (not maximal: subset of {6, 2, 0, 1})
{0, 1} (not maximal: subset of {6, 2, 0, 1})
{1} (not maximal: subset of {6, 2, 0, 1})
次に、分解は次のようになります。
{3, 2}
|
{4, 5, 6}----{5, 6, 2, 0}
|
{7, 2, 1}
|
{6, 2, 0, 1},
0個の頂点が接続されていないため、これも間違っています。申し訳ありません。
私がすべきことは、今のところ最大条件を脇に置き、各クリークKを、Kに属する頂点がシードされた次の候補に接続することです。これにより、少なくとも1つの後続のクリークにも存在するKのすべての頂点が保証されます。接続のターゲットにが表示されます。すると分解は次のようになります
{4, 5, 6}----{5, 6, 2, 0}
|
{6, 2, 0, 1}
|
{3, 2}----{2, 0, 1}----{7, 2, 1}
|
{0, 1}
|
{1}
また、最大でないクリークをスプライスアウトするには、クリークごとに逆の順序で、それが親のスーパーセットであるかどうかを確認し、スーパーセットである場合は、親の子を親に戻します。
{4, 5, 6}----{5, 6, 2, 0}
|
{3, 2}----{6, 2, 0, 1}----{7, 2, 1}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
数のすべての可能な因数分解を生成するためのRアルゴリズム
- 2
数のすべての可能な因数分解を生成するためのRアルゴリズム
- 3
二分木を列挙するためのアルゴリズムの改善
- 4
ポリゴンの分解のためのアルゴリズム
- 5
一種の迷路を生成するための効率的なアルゴリズム
- 6
パスを生成するための論理アルゴリズム
- 7
10進数の30桁を因数分解するためのアルゴリズム
- 8
決定木から予測するための効率的なアルゴリズム（Rを使用）
- 9
アルゴリズム：数のDoutを因数分解する
- 10
k文字のサイズnの組み合わせを生成するためのアルゴリズム
- 11
要素を削除するためのアルゴリズム
- 12
アルゴリズムをテストするためのKinect
- 13
JavaでIDを作成するためのアルゴリズム
- 14
文字列を「短縮」するためのアルゴリズム？
- 15
二分探索木に挿入するための2つの同様のアルゴリズム
- 16
文字列を生成するためのアルゴリズムの時間計算量を理解する
- 17
Javaで決定木を作るための最良の学習アルゴリズム？
- 18
二分探索木で最小合計を見つけるためのアルゴリズムの改善
- 19
強力なチームを生成するための最良のアルゴリズム
- 20
円をポリゴンに結合するためのアルゴリズム
- 21
指定された境界を持つ数行列を生成するためのアルゴリズム
- 22
n Xn個の非同形バイナリ行列を生成するためのアルゴリズム
- 23
ビデオスラッグを生成するためのYoutubeのアルゴリズムは何ですか？
- 24
間隔関係の組み合わせを生成するためのアルゴリズム
- 25
最小全域木を見つけるための欲張りアルゴリズムが確実に停止することを証明する
- 26
配列のサイズを決定するためのアルゴリズム
- 27
Unityで「ランプ」オブジェクトを生成するためのアルゴリズム
- 28
この式を計算するための優れたアルゴリズム
- 29
与えられた数までのすべての数を因数分解する高速アルゴリズム
コメントを追加