Древесное разложение: насколько граф похож на дерево

Если ты проверишь три условия древесного разложения, назовёшь древесную ширину дерева, цикла, решётки и полного графа и знаешь, как оценить её порядком исключения вершин, листай до «Теперь сам».

Как думаешь, что обобщить

Динамика на дереве держалась на одном: поддерево связано с остальным графом одной вершиной. В цикле из шести вершин так не получится - любой кусок цикла соединён с остальным двумя рёбрами.

Ответь себе до чтения: можно ли сохранить идею, если разрешить «перемычку» не из одной вершины, а из нескольких? Да: если граф режется на части перемычками из двух-трёх вершин, динамика будет хранить не два числа, а по числу на каждое состояние перемычки - 2² или 2³. Осталось определить, что значит «режется перемычками», и измерить, насколько они малы. Это и делает древесное разложение.

На что это похоже

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

Дерево собирается листами по две вершины. Решётка улиц k × k - листами по k + 1 улице, и меньше не выйдет: в решётке нет узких мест.

Механизм: мешки, три условия, ширина

мешки X₁ … X_t - наборы вершин, связанные в дерево T
1. каждая вершина графа лежит хотя бы в одном мешке
2. для каждого ребра u-v есть мешок, где лежат и u, и v
3. для каждой вершины v мешки с v образуют связный кусок T
ширина = max |Xᵢ| − 1;  древесная ширина tw(G) - наименьшая ширина

Почему мешок - перемычка. Если убрать из графа вершины мешка Xᵢ, части графа, висящие на разных ветках дерева T от Xᵢ, не связаны рёбрами: ребро между ними нарушило бы условие 2 или 3. Значит, всё общение между ветками идёт через мешок, как в дереве - через вершину.

Цикл из шести вершин. Мешки {0,1,2}, {0,2,3}, {0,3,4}, {0,4,5} подряд: вершина 0 во всех, остальные - в одном-двух соседних. Ширина 2. Меньше нельзя: граф ширины 1 - это дерево или лес, а цикл им не является.

Порядок исключения. Оценку сверху для ширины даёт процедура: брать вершину наименьшей степени, соединить всех её соседей между собой, удалить её; ширина - наибольшая степень в момент удаления. Это эвристика: найти точную древесную ширину NP-трудно, но при фиксированной ширине k есть алгоритмы за 2^(O(k³)) · n (Бодлендер, 1996), а на практике - эвристики вроде этой.

Правило

Древесное разложение - мешки вершин, связанные в дерево: каждая вершина и каждое ребро в каком-то мешке, мешки с одной вершиной связны. Ширина - наибольший мешок минус один. Дерево - 1, цикл - 2, решётка k × k - k, полный граф - n − 1. Мешок отделяет ветки разложения друг от друга, как вершина дерева.

Разбор: три разложения цикла

proverit проверяет три условия и печатает ширину или первое нарушение. Цикл из шести вершин, три попытки: «веер» с вершиной 0 во всех мешках, три мешка «вокруг цикла» в цепочку и разложение, в котором пропущено ребро.

def proverit(n, ryobra, meshki, svyazi):
    # 1) каждая вершина в каком-то мешке
    for v in range(n):
        est = False
        for m in meshki:
            if v in m:
                est = True
        if not est:
            return "вершина " + str(v) + " ни в одном мешке"
    # 2) каждое ребро целиком в каком-то мешке
    for r in ryobra:
        est = False
        for m in meshki:
            if r[0] in m and r[1] in m:
                est = True
        if not est:
            return "ребро " + str(r) + " ни в одном мешке"
    # 3) мешки с вершиной v связны в дереве мешков
    #    (что связи мешков - дерево, здесь не проверяется: они цепочка)
    for v in range(n):
        s_v = []
        for i in range(len(meshki)):
            if v in meshki[i]:
                s_v.append(i)
        dostignuto = [s_v[0]]
        k = 0
        while k < len(dostignuto):
            for r in svyazi:
                for a, b in [[r[0], r[1]], [r[1], r[0]]]:
                    if a == dostignuto[k] and b in s_v:
                        if b not in dostignuto:
                            dostignuto.append(b)
            k = k + 1
        if len(dostignuto) != len(s_v):
            return "мешки с вершиной " + str(v) + " не связны"
    shirina = 0
    for m in meshki:
        shirina = max(shirina, len(m) - 1)
    return "ширина " + str(shirina)

cikl = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0]]
print(proverit(6, cikl, [[0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5]],
               [[0, 1], [1, 2], [2, 3]]))
print(proverit(6, cikl, [[0, 1, 2], [2, 3, 4], [4, 5, 0]],
               [[0, 1], [1, 2]]))
print(proverit(6, cikl, [[0, 1], [1, 2, 3], [3, 4, 5]],
               [[0, 1], [1, 2]]))

ширина 2
мешки с вершиной 0 не связны
ребро [5, 0] ни в одном мешке

Первое - правильное, ширина 2. Во втором все рёбра покрыты, но вершина 0 лежит в первом и третьем мешках, а между ними второй, без неё: нарушено условие 3. Будь оно разрешено, мешок {2, 3, 4} не отделял бы вершину 1 от вершины 5, хотя они соседи через 0. Третье теряет ребро 5-0: его концы не встретились ни в одном мешке.

Разбор: ширина разных графов

isklyuchenie исключает вершины наименьшей степени и возвращает наибольшую степень при исключении - оценку древесной ширины сверху. Дерево на 20 вершинах, цикл на 12, полный граф на 7, решётки от 2 × 2 до 6 × 6.

def isklyuchenie(n, ryobra):
    sosedi = []
    for v in range(n):
        sosedi.append([])
    for r in ryobra:
        sosedi[r[0]].append(r[1])
        sosedi[r[1]].append(r[0])
    zhivye = list(range(n))
    shirina = 0
    while len(zhivye) > 0:
        v = zhivye[0]
        for u in zhivye:
            if len(sosedi[u]) < len(sosedi[v]):
                v = u
        shirina = max(shirina, len(sosedi[v]))
        for a in sosedi[v]:
            for b in sosedi[v]:
                if a != b and b not in sosedi[a]:
                    sosedi[a].append(b)
            sosedi[a].remove(v)
        zhivye.remove(v)
    return shirina

def reshetka(k):
    ryobra = []
    for i in range(k):
        for j in range(k):
            if j + 1 < k:
                ryobra.append([i * k + j, i * k + j + 1])
            if i + 1 < k:
                ryobra.append([i * k + j, (i + 1) * k + j])
    return ryobra

derevo = []
for v in range(1, 20):
    derevo.append([(v - 1) // 2, v])
cikl = []
for v in range(12):
    cikl.append([v, (v + 1) % 12])
klika = []
for a in range(7):
    for b in range(a + 1, 7):
        klika.append([a, b])
print(isklyuchenie(20, derevo), isklyuchenie(12, cikl),
      isklyuchenie(7, klika))
for k in [2, 3, 4, 5, 6]:
    print(k, isklyuchenie(k * k, reshetka(k)))

1 2 6
2 2
3 3
4 4
5 5
6 6

Дерево - 1, цикл - 2, полный граф на семи вершинах - 6. Решётка k × k - ровно k: эвристика здесь нашла точное значение. Решётка 6 × 6 - 36 вершин, но ширина 6: разложение идёт по столбцам: мешок - столбец, в котором вершины по одной заменяются вершинами следующего столбца, и в каждый момент в нём не больше k + 1 вершины.

Это важная граница. Решётка k × k - плоский граф с k² вершинами и шириной k = √n. Любой плоский граф имеет ширину O(√n), и отсюда алгоритмы за 2^(O(√n)) для плоских графов - о них последний урок главы.

Что ломается без этого

Забывают условие связности. Мешки, где вершина «то есть, то нет», не отделяют части графа, и динамика по ним считает неправду.

Ждут малой ширины от плотных графов. У графа, где каждая вершина связана с половиной остальных, ширина порядка n - разложение ничего не даёт.

Ищут точную ширину на больших графах. Это NP-трудно; на практике берут эвристику и работают с тем разложением, что получилось, - динамике нужна не наименьшая ширина, а достаточно малая.

Зачем это в работе

Малая древесная ширина встречается чаще, чем кажется: графы потока управления программ (ширина не больше 6-7 для структурных программ без goto), дорожные сети и электросети (узкие места между районами), молекулы, многие байесовские сети. Компиляторы, решатели и системы вероятностного вывода пользуются этим явно: выделение регистров, вывод в графических моделях (алгоритм дерева сочленений - это и есть динамика по древесному разложению).

Теперь сам

1. Путь из пяти вершин 0-1-2-3-4. Предложи разложение ширины 1.
2. Мешки {1,2}, {2,3}, {1,3} связаны в цепочку именно в таком порядке. Граф - треугольник 1-2-3. Какое условие нарушено?
3. Какова древесная ширина полного графа на 10 вершинах и почему меньше нельзя?