Bir ağaç ayrıştırma oluşturmak için algoritma

Question

Bir ağaç ayrıştırma oluşturmak istiyorum: http://en.wikipedia.org/wiki/Tree_decomposition ve ben korse grafiği ve mükemmel bir eleme siparişi var.

bir kiriş grafiğin ağaç ayrışma (genel olarak) olmayan bir güzel inşa etmek: Ben yani previous thread verilen danışmanlık, takip ediyorum mükemmel bir eleme sipariş bulmak, maksimal klikler numaralandırmak (adayları bir köşe noktasıdır ve siparişte görünen komşulardır, her bir kertiği bir ayrıştırma düğümü olarak kullanın ve onu kesişme sırasındaki sonraki klikle bağlayın.

Bu işe yaramıyor ve nedenini anlayamıyorum. Aşağıdaki örneği inceleyelim:

Mükemmel eleme sipariş:

['4', '3', '5', '7', '6', '2', '0', '1'] 

Korda grafiği:

Ağaç ayrışma: Ben

kullanıyorum eo mükemmel bir sipariş listesi ve 'chordal_graph' dir

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()  

networkx için bir grafik nesnesidir: piton ve benim şimdiki algoritma şudur.

Answer 1

Bu benim önerim (kötü olduğu gibi) oldu. Ağaç ayrıştırma işleminizin maksimal olmayan bazı kestikleri vardır, diğer bir deyişle {2, 0, 1}, {0, 1} ve {1}. Aday klikler listesi

{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}) 

Ardından ayrışma 0 köşe bağlı olmadıklarından, hem de yanlış

   {3, 2} 
        | 
{4, 5, 6}----{5, 6, 2, 0} 
        | 
      {7, 2, 1} 
        | 
      {6, 2, 0, 1}, 

gibi görünmelidir olduğunu. Bunun için üzgünüm.

Yapmam gereken şey, o an için en yüksek koşul koşulunu bir kenara ayırmak ve her bir K noktasını K'ya ait bir köşe ile tohumlanan bir sonraki adaya bağlamaktır. Bu, K'daki her tepe noktasının en az birinde var olmasını sağlar. diğer takip eden klik, bağlantının hedefinde de belirir. Ardından ayrışma bu

{4, 5, 6}----{5, 6, 2, 0} 
        | 
      {6, 2, 0, 1} 
        | 
    {3, 2}----{2, 0, 1}----{7, 2, 1} 
        | 
       {0, 1} 
        | 
       {1} 

benziyor ve onun ebeveynin çocuklarını reparenting ters sırada her kliğin için, kontrol ederek dışı maksimal klikler dışarı splice, onun ebeveynin bir üst olsun, ve eğer öyleyse, olabilir o.

{4, 5, 6}----{5, 6, 2, 0} 
        | 
    {3, 2}----{6, 2, 0, 1}----{7, 2, 1}