Cyclebasis function for graphs not working
显示 更早的评论
I have the following graph, with the corresponding cycle generation using cycle basis:
Matlab generates makes a mistake with the third cycle giving:
2 9 5 13 11 12 when it should be 2 9 5 13 12.
s = [ 1 4 6 3 10 2 9 5 8 7 1 11 12 3 12 13 4 11 13];
t = [ 4 6 3 10 2 9 5 8 7 1 11 12 2 12 13 8 11 13 5];
G = graph(s,t);
plot(G)
[cycles,edgecycles] = cyclebasis(G);
cycles
采纳的回答
Christine Tobler
2024-4-30
1 个投票
Yes, cyclebasis returns a fundamental cycle basis, but not necessarily the one with the shortest cycle lengths. See the documentation's "more about" section: "However, cyclebasis is not guaranteed to return the shortest possible fundamental cycle basis."
3 个评论
Allan
2024-4-30
I'm assuming you mean this statement from the doc:
"For each edge that is not in the minimum spanning tree, there exists one fundamental cycle which is composed of that edge, its end nodes, and the path in the minimum spanning tree that connects them."
It's separating the edges into two types, those that are in the chosen minimum spanning tree, and those that are not. Only the ones that are not in that tree appear in only one of the cycles.
Here's an example:
G = graph([1:4], [2:4 1]);
G = addedge(G, [4:6], [5:6 3]);
p = plot(G);
cyclebasis(G)
Here the edge (3, 4) is a part of two cycles - but this is all right. In fact, I don't think it's possible to find two cycles here without any overlapping edges.
So what is this minimum spanning tree? A tree that would lead to the cycles above is the following:
t = rmedge(G, [1 5], [2 6]); % a minimum spanning tree
figure;
p = plot(G);
highlight(p, t)
You can see two edges are missing, (1,2) and (5, 6), each of which makes one of the cycles above when combined with the tree itself. For example, take edge (1, 2) and combine it with the shortest path inside the tree connecting nodes 1 and 2. This makes for the cycle (1, 2, 3, 4, 1).
Allan
2024-5-1
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
