Древесная шириной неориентированного графа является очень важным понятием в теории графов. Были изобретены тонны графовых алгоритмов, которые работают быстро, если у вас есть разложение графа с небольшой шириной дерева.

Ширина дерева часто определяется в терминах разложения дерева. Вот график и древовидная декомпозиция этого графа, любезно предоставленная Википедией:

Разложение дерева - это дерево, в котором каждая вершина связана с подмножеством вершин исходного графа со следующими свойствами:

• Каждая вершина в исходном графе находится хотя бы в одном из подмножеств.
• Каждое ребро в исходном графе имеет обе свои вершины хотя бы в одном из подмножеств.
• Все вершины в разложении, подмножества которых содержат данную исходную вершину, связны.

Вы можете проверить, что приведенная выше декомпозиция соответствует этим правилам. Ширина разложения дерева равна размеру его наибольшего подмножества, минус один. Таким образом, это два для вышеупомянутого разложения. Ширина дерева графа является наименьшей шириной любого дерева разложения этого графа.

В этом задании вам будет предоставлен связанный неориентированный граф, и вы должны найти его ширину дерева.

Хотя найти разложение по дереву сложно, существуют другие способы вычисления ширины дерева. На странице Википедии есть больше информации, но один метод вычисления ширины дерева, не упомянутый там, который часто используется в алгоритмах для вычисления ширины дерева, - это минимальная ширина упорядочения исключения. Смотрите здесь для бумаги, используя этот факт.

В порядке исключения удаляются все вершины графа по одному. Когда каждая вершина удаляется, добавляются ребра, соединяющие всех соседей этой вершины друг с другом. Это повторяется до тех пор, пока все вершины не исчезнут. Ширина упорядочения удаления - это наибольшее число соседей, которое имеет любая удаляемая вершина во время этого процесса. Ширина дерева равна минимуму для всех порядков ширины упорядочения исключения. Вот пример программы, использующей этот факт для вычисления ширины дерева:

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

Примеры:

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

Вы получите график в качестве входных данных, и вы должны вернуть ширину дерева в качестве выходных данных. Формат ввода гибкий. В качестве входных данных вы можете взять список ребер, карту смежности или матрицу смежности. Если вы хотите использовать другой формат ввода, спросите в комментариях. Вы можете предположить, что вход подключен, и вы можете встроить это предположение в свой формат ввода, например, используя список ребер.

РЕДАКТИРОВАТЬ: встроенные операции, которые вычисляют ширину дерева не допускаются. Я извиняюсь за то, что не уточнил это заранее.

Самый короткий код выигрывает.

Октава, 195 байт

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

Функция, которая принимает в качестве входных данных матрицу смежности. Он потребляет большой объем памяти, поэтому он бесполезен, если количество вершин больше 10-12.

• однако нет необходимости endfunctionдобавлять его в tio.

Попробуйте онлайн!

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 байт неконкурентоспособны *

lambda L:Graph(L).treewidth()

* Этот ответ был опубликован до изменения ОП вопроса о том, что «Встроенные системы запрещены», поэтому я сделал его неконкурентным.

Демо онлайн!

Haskell (Lambdabot), 329 321 245 байт

Вот мое решение, благодаря гибкости ввода, он работает на графиках с графами, содержащими любой тип, который является экземпляром 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

Попробуйте онлайн!

Безголовая версия:

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