Die Breite eines ungerichteten Graphen ist ein sehr wichtiges Konzept in der Graphentheorie. Es wurden Tonnen von Graphenalgorithmen erfunden, die schnell ablaufen, wenn Sie eine Zerlegung des Graphen mit kleiner Baumbreite haben.

Die Baumbreite wird oft in Form von Baumzerlegungen definiert. Hier ist eine Grafik und eine Baumzerlegung dieser Grafik mit freundlicher Genehmigung von Wikipedia:

Eine Baumzerlegung ist ein Baum, bei dem jeder Scheitelpunkt einer Teilmenge der Scheitelpunkte des ursprünglichen Diagramms mit den folgenden Eigenschaften zugeordnet ist:

• Jeder Scheitelpunkt im Originaldiagramm befindet sich in mindestens einer der Teilmengen.
• Jede Kante im Originalgraphen hat beide Scheitelpunkte in mindestens einer der Teilmengen.
• Alle Scheitelpunkte in der Zerlegung, deren Teilmengen einen bestimmten ursprünglichen Scheitelpunkt enthalten, werden verbunden.

Sie können überprüfen, ob die obige Zerlegung diesen Regeln entspricht. Die Breite einer Baumzerlegung entspricht der Größe der größten Teilmenge minus eins. Daher ist es zwei für die obige Zerlegung. Die Baumbreite eines Graphen ist die kleinste Breite einer Baumzerlegung dieses Graphen.

In dieser Herausforderung erhalten Sie einen zusammenhängenden, ungerichteten Graphen, und Sie müssen seine Baumbreite finden.

Während es schwierig ist, Baumzerlegungen zu finden, gibt es andere Möglichkeiten, die Baumbreite zu berechnen. Die Wikipedia-Seite enthält weitere Informationen, aber eine dort nicht erwähnte Methode zur Berechnung der Baumbreite, die häufig in Algorithmen zur Berechnung der Baumbreite verwendet wird, ist die minimale Breite der Eliminierungsreihenfolge. Sehen Sie hier für ein Papier, das diese Tatsache verwendet.

In einer Eliminierungsreihenfolge werden alle Eckpunkte eines Graphen einzeln entfernt. Wenn jeder Scheitelpunkt entfernt wird, werden Kanten hinzugefügt, die alle Nachbarn dieses Scheitelpunkts miteinander verbinden. Dies wird wiederholt, bis alle Scheitelpunkte verschwunden sind. Die Breite der Eliminierungsreihenfolge ist die größte Anzahl von Nachbarn, die ein zu eliminierender Scheitelpunkt während dieses Prozesses aufweist. Die Baumbreite ist über alle Ordnungen der Eliminierungsordnungsbreite gleich dem Minimum. Hier ist ein Beispielprogramm, das diese Tatsache zur Berechnung der Baumbreite verwendet:

import itertools
def elimination_width(graph):
    max_neighbors = 0
    for i in sorted(set(itertools.chain.from_iterable(graph))):
        neighbors = set([a for (a, b) in graph if b == i] + [b for (a, b) in graph if a == i])
        max_neighbors = max(len(neighbors), max_neighbors)
        graph = [edge for edge in graph if i not in edge] + [(a, b) for a in neighbors for b in neighbors if a < b]
    return max_neighbors

def treewidth(graph):
    vertices = list(set(itertools.chain.from_iterable(graph)))
    min_width = len(vertices)
    for permutation in itertools.permutations(vertices):
        new_graph = [(permutation[vertices.index(a)], permutation[vertices.index(b)]) for (a, b) in graph]
        min_width = min(elimination_width(new_graph), min_width)
    return min_width

if __name__ == '__main__':
    graph = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('b', 'g'),
            ('c', 'd'), ('c', 'e'), ('d', 'e'), ('e', 'g'), ('e', 'h'), ('f', 'g'), ('g', 'h')]
    print(treewidth(graph))

Beispiele:

[(0, 1), (0, 2), (0, 3), (2, 4), (3, 5)]
1

[(0, 1), (0, 2), (1, 2), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (4, 6), (4, 7), (5, 6), (6, 7)]
2

[(0, 1), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 7), (5, 8), (6, 7), (7, 8)]
3

[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
4

Sie erhalten den Graphen als Eingabe und müssen die Baumbreite als Ausgabe zurückgeben. Das Eingabeformat ist flexibel. Sie können eine Kantenliste, eine Adjazenzkarte oder eine Adjazenzmatrix als Eingabe verwenden. Wenn Sie ein anderes Eingabeformat verwenden möchten, fragen Sie in den Kommentaren. Sie können davon ausgehen, dass die Eingabe verbunden ist, und Sie können diese Annahme in Ihr Eingabeformat integrieren, z. B. mithilfe einer Kantenliste.

BEARBEITEN: Eingebaute Operationen, die die Baumbreite berechnen, sind nicht zulässig. Ich entschuldige mich dafür, dass ich dies nicht angegeben habe.

Kürzester Code gewinnt.

Oktave, 195 Bytes

function x=F(a)r=rows(a);P=perms(s=1:r);x=r;for m=s;b=a;n=0;for z=P(m,:);(T=sum(b)(z))&&{b|=(k=accumarray(nchoosek(find(b(z,:)),2),1,[r r]))|k';n=max(T,n);b(z,:)=0;b(:,z)=0}{4};end;x=min(x,n);end

Eine Funktion, die eine Adjazenzmatrix als Eingabe verwendet. Es verbraucht viel Speicher und ist daher unbrauchbar, wenn die Anzahl der Eckpunkte mehr als 10-12 beträgt.

• es besteht keine Notwendigkeit, endfunctiones sollte jedoch zu tio hinzugefügt werden.

Probieren Sie es online!

Ungolfed:

function min_width = treewidth(graph_adj)
    Nvertices = rows(graph_adj)
    Permutations = perms(1:Nvertices);                                                            % do not try it for large number of vertices
    min_width = Nvertices;
    for v = 1:Nvertices;
        new_graph=graph_adj;
        max_neighbors=0;
        for p = Permutations(v,:)
            Nneighbors=sum(new_graph)(p);
            if(Nneighbors)>0
                connection=accumarray(nchoosek(find(new_graph(p,:)),2),1,[Nvertices Nvertices]);  % connect all neighbors
                new_graph|=connection|connection';                                                % make the adjacency matrix symmetric
                new_graph(p,:)=0;new_graph(:,p)=0;                                                % eliminate the vertex
                max_neighbors=max(Nneighbors,max_neighbors);
            end
        end
        min_width=min(min_width,max_neighbors);
    end
end

SageMath, 29 Bytes nicht konkurrierend *

lambda L:Graph(L).treewidth()

* Diese Antwort wurde vor OPs Änderung der Frage "Builtins sind verboten" gepostet.

Online Demo!

Haskell (Lambdabot), 329 321 245 Bytes

Hier ist meine Lösung, dank der Flexibilität der Eingabe, die bei Diagrammen mit Diagrammen verwendet wird, die jeden Typ enthalten, von dem eine Instanz ist Eq.

(&)=elem
l=length
t n g s=last$minimum[max(t n g b)$t(n++b)g$s\\b|b<-filterM(\_->[0>1,1>0])s,l b==div(l s)2]:[l[d|d<-fst g,not$d&n,d/=s!!0,(d&)$foldr(\x y->last$y:[x++y|any(&y)x])[s!!0]$join(>>)[e|e<-snd g,all(&(s!!0:d:n))e]]|1==l s]
w=t[]<*>fst

Probieren Sie es online!

Ungolfed-Version:

type Vertex a = a
type Edge a   = [Vertex a]
type Graph a  = ([Vertex a],[Edge a])

vertices = fst
edges = snd

-- This corresponds to the function w
treeWidth :: (Eq a) => Graph a -> Int
treeWidth g = recTreeWidth g [] (vertices g)

-- This is the base case (length s == 1) of t
recTreeWidth graph left [v] =
    length [ w | w <- vertices graph
               , w `notElem` left
               , w /= v
               , w `elem` reachable (subGraph w)
           ]

  where subGraph w = [ e | e <- edges graph, all (`elem` v:w:left) e ]

        reachable g = foldr accumulateReachable [v] (g>>g)
        accumulateReachable x y = if any (`elem` y) x
                                  then x++y
                                  else y

-- This is the other case of t
recTreeWidth graph left sub =
  minimum [ comp sub' | sub' <- filterM (const [False,True]) sub
                      , length sub' == div (length sub) 2
          ]

  where comp b = max (recTreeWidth graph left b)
                     (recTreeWidth graph (left++b) (sub\\b))