Поиск MST таким образом, что определенная вершина имеет минимальную степень

Question

Полученный неориентированный граф G = {V, E}, вершина из V (G), обозначить его v и весовую функцию f: E-> R + (Положительные действительные числа), мне нужно найти MST, чтобы степень v была минимальной. Я уже заметил, что если все ребра имеют уникальный вес, MST уникален, поэтому я считаю, что он имеет какое-то отношение к повторяющимся весам по краям. Я, хотя про алгоритм Kruskal, но при сортировке ребер, я всегда буду рассматривать ребра, которые встречаются на v в прошлом. Например, если (a, b), (c, d), (v, e) являются единственными ребрами веса k, поэтому возможными перестановками этих ребер в массиве отсортированных ребер являются: {(a, b), (c, d), (v, e)} или {(c, d), (a, b), (v, e)}. Я выполнил эту вариацию на нескольких графиках, и, похоже, это работает, но я не мог это доказать. Кто-нибудь знает, как доказать правильность алгоритма (значение степени доказывания v минимально) или дать противоположный пример отказа алгоритма?

Answer 1

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

Доказательство проводится по индукции по количеству, k, от четких весов.

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

1) Нет выбранное ребро не образует цикла с ранее выбранных ребер

2) ребро с участием v не выбран, если какой-либо край, который не включать v не нарушает правило 1.

G' Пусть обозначим график, из которого v и всех инцидентных ребер были удалены из G. Легко видеть, что алгоритм в этом частном случае работает следующим образом. Он начинается с создания сплошного леса для G'. Затем он берет те деревья в лесу, которые содержатся в подключенном компоненте v's в исходном графе G, и соединяет каждый компонент с v одним краем. Поскольку компоненты, подключенные к v на второй стадии, могут быть соединены друг с другом не иначе (поскольку, если существует какой-либо соединительный край, не содержащий v, он был бы выбран по правилу 2), легко видеть, что степень v равна минимален.

Индуктивный Корпус: Предположим, что результат справедлив для k и G является взвешенный граф с k+1 различными весами и v является указанной вершиной в G. Сортировка отдельных весов в порядке возрастания (так что вес k+1 является самым длинным из отдельных весов - скажем w_{k+1}). Пусть G' является подграфом G с тем же набором вершин, но со всеми краями веса w_{k+1} удален. Поскольку ребра сортируются в порядке возрастания веса, обратите внимание, что модифицированный алгоритм Kruskal's в действии начинает, применяя себя к G'.Таким образом, по предположению индукции перед рассмотрением краев веса w_{k+1} алгоритм преуспел в построении MSF F' от G', для которого степень d'v в G' минимизирована.

В качестве заключительного шага модифицированный Kruskal применяется к общему графику G объединит некоторые деревья в F' вместе, добавив края веса w_{k+1}. Один из способов концептуализации последнего шага - думать о F' как о графике, где два дерева связаны точно, когда есть край веса w_{k+1} из некоторого узла в первом дереве на некоторый узел во втором дереве. У нас есть (почти) базисный случай с F'. Модифицированный Kruskal добавит обрезанный вес w_{k+1}, пока он больше не сможет этого сделать, и не добавит края, соединяющегося с v, если нет другого способа подключения к деревьям в F', которые необходимо подключить, чтобы получить связующий лес для исходного графика G.

В последней степени v в результате MSF является d = d'+d", где d" это число ребер веса w_{k+1} добавляют на конечной стадии. Ни d', ни d" не могут быть сделаны меньшими, следовательно, из этого следует, что d не может быть меньше (поскольку степень v в любом охватывающем лесу может быть записана как сумма количества ребер, вес которых меньше w_{k+1} в v и номер с краев веса w_{k+1}, входящий в v).

QED.

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

Последнее замечание - кажется довольно очевидным, что алгоритм Prim может быть аналогичным образом модифицирован для этой проблемы. Вы изучили это?