Ich möchte eine Baumzerlegung konstruieren:http://en.wikipedia.org/wiki/Tree_decomposition und ich habe das Akkorddiagramm und eine perfekte Eliminierungsreihenfolge. Ich folge den Ratschlägen in avorheriger Threadnämlich:

Um eine (im Allgemeinen) nicht schöne Baumzerlegung eines Akkordgraphen zu konstruieren: Finden Sie eine perfekte Eliminierungsreihenfolge, zählen Sie die maximalen Cliquen auf (die Kandidaten sind ein Eckpunkt und die Nachbarn, die in der Reihenfolge danach erscheinen), und verwenden Sie jede Clique als a Dekompositionsknoten und verbinden Sie ihn mit der nächsten Clique in der Reihenfolge, in der er sich schneidet.

Dies funktioniert jedoch nicht und ich kann nicht herausfinden, warum. Betrachten Sie das folgende Beispiel:

Perfekte Eliminierungsreihenfolge:

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

Akkorddiagramm:

Baumzerlegung:

Ich benutze Python und mein aktueller Algorithmus ist der folgende:

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

woeo ist eine Liste der perfekten Reihenfolge und 'chordal_graph' ist ein Graph-Objekt fürnetworkx.