Связующее дерево, которое минимизирует динамическую "метрику"

Question

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

Дополнительная сложность заключается в том, что если у вершины есть n автомобилей, которые проезжают из нее, то стоимость K^n, а не n*K.

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

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

редактировать:

Процесс такой. Мы удаляем ряд ребер, чтобы сделать граф остовным деревом. Каждый удаленный край создает 2 машины, по одному на каждую вершину удаленного края, которые должны встретиться друг с другом. Мы устанавливаем путь для каждой из этих машин-близнецов. Затем мы проверяем, сколько машин (со всех удаленных нами ребер) проходит через каждую вершину. Если количество автомобилей, которые проезжают из вершины, равно n, стоимость равна K^n, где K - это константа. Затем мы добавляем все затраты, и это глобальные затраты, которые необходимо минимизировать.

пожалуйста, скажите мне, если что-то неясно. https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric

Answer 1

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

Чтобы найти минимальную стоимость для блока - вы можете перечислить все связующие деревья для этого блока и рассчитать стоимость для каждого - метод грубой силы, но он должен работать.