Правилен ли этот алгоритм минимального связующего дерева?

Что произойдет, если два цикла пересекутся? У какого из них первым было удалено самое длинное ребро? Имеет ли значение, если самое длинное ребро каждого является общим для двух циклов или нет?

Например:

V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }

Есть цикл a -> b -> c -> a и a -> b -> d -> a.

@shrughes.blogspot.com:

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

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

Кроме того, запрещена ли рекурсия в этой теоретической архитектуре? Если это так, может быть фактически невозможно найти MST на графе, потому что у вас не будет никаких средств для проверки каждой вершины/ребра на графе.

Я не знаю, работает ли это, но несмотря ни на что, ваш алгоритм даже не стоит реализовывать. Поиск всех циклов станет чертовски огромным узким местом, которое его убьет. Также сделать это без итераций невозможно. Почему бы вам не реализовать какой-нибудь стандартный алгоритм, скажем, Prim's.

Ваш алгоритм не совсем четко определен. Если у вас есть полный граф, ваш алгоритм, по-видимому, предполагает удаление на первом этапе всех элементов, кроме двух минимальных. Кроме того, перечисление всех циклов на графике может занять экспоненциальное время.

Разработка:

В графе с n узлами и ребром между каждой парой узлов есть, если я правильно понял математику, n!/(2k(n-k)!) циклов размера k, если вы считаете цикл как некоторый подграф из k узлов и k ребер, где каждый узел имеет степень 2.

@Tynan Систему можно описать (несколько упрощенно) как систему правил, описывающих категоризацию. «Вещи находятся в категории A, если они находятся в B, но не в C», «Узлы, связанные с узлами в Z, также находятся в Z», «Каждая категория в M связана с узлом N и имеет «дочерние» категории, также в M для каждого узла, подключенного к N". Это немного сложнее, чем это. (Я показал, что, создавая нестабильные правила, вы можете смоделировать токарный станок, но это не относится к делу.) Он не может явно определить итерацию или рекурсию, но может работать с рекурсивными данными с такими правилами, как 2-е и 3-е.

@Marcin, предположим, что существует неограниченное количество процессоров. Легко показать, что программа может быть запущена за O(n^2) для n, являющегося самым длинным циклом. С лучшими структурами данных это может быть уменьшено до O (n * O (установить функцию поиска)), я могу представить аппаратное обеспечение (квантовые компьютеры?), Которое может оценивать все циклы за постоянное время. давая O (1) решение проблемы MST.

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

Хм....

Хорошо, это попытка закончить доказательство правильности. По аналогии с алгоритмом обратного удаления мы знаем, что будет удалено достаточно ребер. Остается показать, что удаленных ребер не будет слишком много.

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

Осталось показать, что это распространяется на> 2-сторонние разделы.