Из того, что я могу сказать, не только предчувствие Брайана, но и еще более сильное утверждение: каждое ребро, которое не входит в минимальное остовное дерево, добавляет ровно один новый "базовый цикл".
Чтобы увидеть это, давайте посмотрим, что произойдет, когда вы добавите ребро E, которого нет в MST. Давайте сделаем любимый математический способ усложнить вещи и добавить некоторые обозначения;) Назовите исходный граф G, график перед добавлением E G 'и график после добавления E G' '. Таким образом, нам нужно выяснить, как изменяется «счетчик базовых циклов» с G 'на G' '.
Добавление E должно завершить хотя бы один цикл (в противном случае E было бы в MST G в первую очередь). Очевидно, что он должен добавить хотя бы один «базовый цикл» к уже существующим в G '. Но это добавляет больше чем один?
Он не может добавить более двух, поскольку ни одно ребро не может быть членом более двух базовых циклов. Но если E является членом двух базовых циклов, то «объединение» этих двух базовых циклов должно было быть базовым циклом в G ', поэтому мы снова получаем, что изменение числа циклов все еще равно одному.
Ergo, для каждого ребра, не входящего в MST, вы получаете новый базовый цикл. Таким образом, часть «считать» проста. Найти все ребра для каждого базового цикла немного сложнее, но, следуя рассуждениям выше, я думаю, что это можно сделать (в псевдо-Python):
for v in vertices[G]:
cycles[v] = []
for e in (edges[G] \ mst[G]):
cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
if cycle_to_split == None:
# we're adding a completely new cycle
path = find_path(e.node1, e.node2, mst[G])
for vertex on path:
cycles[vertex].append(path + [e])
cycles
else:
# we're splitting an existing base cycle
cycle1, cycle2 = split(cycle_to_split, e)
for vertex on cycle_to_split:
cycles[vertex].remove(cycle_to_split)
if vertex on cycle1:
cycles[vertex].append(cycle1)
if vertex on cycle2:
cycles[vertex].append(cycle2)
base_cycles = set(cycles)
Редактировать : код должен найти все базовые циклы на графике (base_cycles установлен внизу). Предполагается, что вы знаете, как:
- найти минимальное остовное дерево графа (mst [G])
- найти разницу между двумя списками (ребра \ mst [G])
- найти пересечение двух списков
- найти путь между двумя вершинами в MST
- разделить цикл на два, добавив к нему дополнительный край (функция разделения)
И это в основном следует за обсуждением выше. Для каждого ребра, не входящего в MST, у вас есть два случая: либо он приносит совершенно новый базовый цикл, либо разбивает существующий один на два. Чтобы отследить, какой из двух случаев имеет место, мы отслеживаем все базовые циклы, частью которых является вершина (используя словарь циклов).