Algoritmo per la generazione di una scomposizione dell'albero

Question

Voglio costruire una scomposizione dell'albero: http://en.wikipedia.org/wiki/Tree_decomposition e ho il grafico cordale e un ordine di eliminazione perfetto. Seguo consigli dati in un previous thread, vale a dire:

per costruire una non bella (in generale) albero decomposizione di un grafico accordale: trovare un perfetto ordinamento eliminazione, enumerare le massime cricche (i candidati sono un vertice e i vicini che compaiono dopo l'ordine), usano ciascuna cricca come nodo di scomposizione e collegano alla cricca successiva nell'ordine in cui si interseca.

Questo non funziona tuttavia e non riesco a capire perché. Si consideri il seguente esempio:

perfetta eliminazione ordinazione:

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

grafico Chordal:

Albero di decomposizione:

sto usando pitone e il mio algoritmo attuale è la seguente:

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

dove eo è un elenco di dell'ordinamento perfetto e 'chordal_graph' è un oggetto grafico per networkx.

Answer 1

Quindi quello era il mio (cattivo, come risulta) consiglio. La scomposizione dell'albero ha alcune cricche che non sono massime, cioè {2, 0, 1}, {0, 1} e {1}. L'elenco dei candidati è cricche

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

Poi la decomposizione dovrebbe essere simile

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

che è sbagliato, così, dal momento che i vertici 0 non sono collegati. Mi dispiace per quello

Quello che avrei dovuto fare era mettere da parte la condizione di massima per il momento e collegare ogni cricca K al prossimo candidato seminato con un vertice appartenente a K. Ciò garantisce che ogni vertice in K che esiste in almeno uno anche la clique successiva appare nel target della connessione. Poi la decomposizione assomiglia a questo

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

ed è possibile unire le cricche non massimale verificando, per ogni cricca in ordine inverso, che si tratti di un superset del suo genitore, e in caso affermativo, reparenting figli del suo capostipite esso.

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