フィルターのクリア

Cyclebasis function for graphs not working

1 回表示 (過去 30 日間)
Allan
Allan 2024 年 4 月 30 日
コメント済み: Allan 2024 年 5 月 1 日
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
cycles = 7x1 cell array
{[ 1 4 11]} {[ 1 7 8 13 11]} {[2 9 5 13 11 12]} {[ 2 10 3 12]} {[ 3 6 4 11 12]} {[ 5 8 13]} {[ 11 12 13]}

採用された回答

Christine Tobler
Christine Tobler 2024 年 4 月 30 日
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 件のコメント
Christine Tobler
Christine Tobler 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)
ans = 2x1 cell array
{[1 2 3 4]} {[3 4 5 6]}
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
Allan 2024 年 5 月 1 日
Ahhh I see, so there are instances where the algorithm is not garaunteed because of the problem itself. Thank you

サインインしてコメントする。

その他の回答 (0 件)

カテゴリ

Help Center および File ExchangeGraph and Network Algorithms についてさらに検索

製品


リリース

R2023a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by