El ancho de árbol de un gráfico no dirigido es un concepto muy importante en la teoría de gráficos. Se han inventado toneladas de algoritmos de gráficos que se ejecutan rápidamente si tiene una descomposición del gráfico con un ancho de árbol pequeño.

El ancho del árbol a menudo se define en términos de descomposiciones del árbol. Aquí hay un gráfico y una descomposición en árbol de ese gráfico, cortesía de Wikipedia:

La descomposición de un árbol es un árbol donde cada vértice está asociado con un subconjunto de los vértices del gráfico original, con las siguientes propiedades:

• Cada vértice en el gráfico original está en al menos uno de los subconjuntos.
• Cada borde en el gráfico original tiene sus dos vértices en al menos uno de los subconjuntos.
• Todos los vértices en la descomposición cuyos subconjuntos contienen un vértice original dado están conectados.

Puede verificar que la descomposición anterior sigue estas reglas. El ancho de la descomposición de un árbol es el tamaño de su subconjunto más grande, menos uno. Por lo tanto, son dos para la descomposición anterior. El ancho de árbol de un gráfico es el ancho más pequeño de cualquier descomposición de árbol de ese gráfico.

En este desafío, se le dará un gráfico conectado, no dirigido, y deberá encontrar su ancho de árbol.

Si bien encontrar descomposiciones de árboles es difícil, existen otras formas de calcular el ancho del árbol. La página de Wikipedia tiene más información, pero un método para calcular el ancho de árbol que no se menciona allí y que a menudo se usa en algoritmos para calcular el ancho de árbol es el ancho mínimo de orden de eliminación. Vea aquí un artículo que utiliza este hecho.

En un orden de eliminación, uno elimina todos los vértices de un gráfico de uno en uno. Cuando se elimina cada vértice, se agregan bordes conectando todos los vecinos de ese vértice entre sí. Esto se repite hasta que todos los vértices hayan desaparecido. El ancho de orden de eliminación es el mayor número de vecinos que tiene cualquier vértice que se está eliminando durante este proceso. El ancho de árbol es igual al mínimo en todos los pedidos del ancho de orden de eliminación. Aquí hay un programa de ejemplo que usa este hecho para calcular el ancho del árbol:

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

Ejemplos:

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

Recibirá el gráfico como entrada y deberá devolver el ancho del árbol como salida. El formato de entrada es flexible. Puede tomar una lista de aristas, un mapa de adyacencia o una matriz de adyacencia como entrada. Si desea utilizar otro formato de entrada, pregunte en los comentarios. Puede suponer que la entrada está conectada, y puede construir esa suposición en su formato de entrada, por ejemplo, utilizando una lista de bordes.

EDITAR: Las operaciones integradas que calculan el ancho del árbol no están permitidas. Pido disculpas por no especificar esto por adelantado.

El código más corto gana.

Octava, 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

Una función que toma como entrada una matriz de adyacencia. Consume una gran cantidad de memoria, por lo que es inútil si el número de vértices es superior a 10-12.

• sin endfunctionembargo, no es necesario agregarlo a tio.

Pruébalo en línea!

Sin golf:

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 sin competencia *

lambda L:Graph(L).treewidth()

* Esta respuesta se publicó antes del cambio de OP de la pregunta de que "Los builtins están prohibidos", por lo que lo hice sin competencia.

Demo en línea!

Haskell (Lambdabot), 329 321 245 bytes

Aquí está mi solución, gracias a la flexibilidad de la entrada que funciona en gráficos con gráficos que contienen cualquier tipo de instancia 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

Pruébalo en línea!

Versión sin golf:

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