计算树宽

Question

无向图的树宽是图论中一个非常重要的概念。大量的图形算法已经被发明出来，如果你有一个小树宽的图分解的话，这些算法运行得很快。

树宽通常用树分解来定义。这是维基百科提供的一个图表和一个树分解图：

树分解是一种树，其中每个顶点与原始图的一个顶点子集相关联，具有以下属性：

• 原始图中的每个顶点至少在其中一个子集中。
• 原始图中的每个边在至少一个子集中都有两个顶点。
• 分解中包含给定原始顶点的子集的所有顶点都是连通的。

您可以检查上面的分解是否遵循以下规则。树分解的宽度是其最大子集的大小，减去1。因此，对于上述分解，它是两个。图的树宽是该图的任意树分解中最小的宽度。

在这个挑战中，你将得到一个连通的无向图，你必须找到它的树宽。

虽然找出树的分解很困难，但也有其他方法来计算树宽。维基百科页面有更多的信息，但是在计算树宽的算法中经常用到的一种计算树宽的方法是最小消序宽度。有关使用此事实的论文，请参见这里。

在消去顺序中，一个人一次消除一个图的所有顶点。当每个顶点被消除时，边被添加，将所有的顶点的邻居连接到一起。这是重复的，直到所有的顶点都消失。消除排序宽度是在此过程中被消除的任何顶点所具有的最大邻域数。树宽等于消除序宽度的所有顺序上的最小值。下面是一个使用这个事实计算树宽的示例程序：

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

您将收到作为输入的图形，并且必须返回树宽作为输出。输入格式灵活。您可以使用一个边列表、一个邻接映射或一个邻接矩阵作为输入。如果您想使用另一种输入格式，请在注释中询问。您可以假设输入是连接的，并且可以将该假设构建为您的输入格式，例如使用一个边缘列表。

编辑:不允许计算树宽的内置操作。我很抱歉没有提前说明这一点。

最短代码获胜。

Answer 1

倍频程，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中。

在网上试试！

未高尔夫球：

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