Treewidth z undirected wykresu jest bardzo ważnym pojęciem w teorii grafów. Wynaleziono mnóstwo algorytmów graficznych, które działają szybko, jeśli masz rozkład wykresu o małej szerokości.

Szerokość grzbietu jest często definiowana w kategoriach rozkładu drzew. Oto wykres i rozkład drzewa tego wykresu, dzięki uprzejmości Wikipedii:

Rozkład drzewa to drzewo, w którym każdy wierzchołek jest powiązany z podzbiorem wierzchołków oryginalnego wykresu, o następujących właściwościach:

• Każdy wierzchołek na oryginalnym wykresie znajduje się w co najmniej jednym z podzbiorów.
• Każda krawędź oryginalnego wykresu ma oba wierzchołki w co najmniej jednym z podzbiorów.
• Wszystkie wierzchołki w rozkładzie, których podzbiory zawierają dany oryginalny wierzchołek, są połączone.

Możesz sprawdzić, czy powyższy rozkład podlega tym regułom. Szerokość rozkładu drzewa jest wielkością jego największego podzbioru minus jeden. Dlatego dla powyższego rozkładu są dwa. Szerokość wykresu jest najmniejszą szerokością rozkładu drzewa tego wykresu.

W tym wyzwaniu otrzymasz połączony, nieukierunkowany wykres i musisz znaleźć jego szerokość.

Chociaż znalezienie rozkładu drzew jest trudne, istnieją inne sposoby obliczania szerokości grzbietu. Strona Wikipedii zawiera więcej informacji, ale jedną z metod obliczania szerokości poprzecznej, o której tam nie wspomniano, która jest często stosowana w algorytmach do obliczania szerokości poprzecznej, jest minimalna szerokość zamówienia eliminacji. Zobacz tutaj artykuł wykorzystujący ten fakt.

W kolejności eliminacji eliminuje się wszystkie wierzchołki wykresu pojedynczo. Po wyeliminowaniu każdego wierzchołka dodawane są krawędzie łączące ze sobą wszystkich sąsiadów tego wierzchołka. Jest to powtarzane, aż wszystkie wierzchołki znikną. Szerokość porządkowania eliminacji jest największą liczbą sąsiadów, jaką ma wyeliminowany wierzchołek podczas tego procesu. Szerokość jest równa minimum we wszystkich rzędach szerokości uporządkowania eliminacji. Oto przykładowy program wykorzystujący ten fakt do obliczenia szerokości poprzecznej:

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

Przykłady:

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

Otrzymasz wykres jako dane wejściowe i musisz zwrócić szerokość jako wynik. Format wejściowy jest elastyczny. Jako dane wejściowe możesz wziąć listę krawędzi, mapę przylegania lub macierz przylegania. Jeśli chcesz użyć innego formatu wejściowego, zapytaj w komentarzach. Możesz założyć, że wejście jest podłączone i możesz założyć to założenie do swojego formatu wejściowego, np. Używając listy krawędzi.

EDYCJA: Wbudowane operacje obliczające szerokość profilu są niedozwolone. Przepraszam, że nie sprecyzowałem tego z góry.

Najkrótszy kod wygrywa.

Oktawa, 195 bajtów

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

Funkcja, która przyjmuje jako dane wejściowe macierz przylegania. Zużywa dużą ilość pamięci, więc jest bezużyteczne, jeśli liczba wierzchołków jest większa niż 10-12.

• nie ma potrzeby endfunctionjednak dodawać go do tio.

Wypróbuj online!

Nie golfowany:

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 bajtów niekonkurencyjnych *

lambda L:Graph(L).treewidth()

* Ta odpowiedź została zamieszczona przed zmianą OP dotyczącą pytania: „Wbudowane są zbanowane”, więc uczyniłem to niekonkurencyjnym.

Demo online!

Haskell (Lambdabot), 329 321 245 bajtów

Oto moje rozwiązanie, dzięki elastyczności wejścia, które działa na wykresach zawierających wykresy dowolnego typu, który jest instancją 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

Wypróbuj online!

Wersja bez golfa:

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