Mixing
Edge properties in a graph
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
Given a G(V,E) weighted(on edges) graph, I need to find the number of edges that belong in every MST as well as the number of the edges that belong in at least one but not all and the ones that belong in none.
The graph is given as input in the following form(example):
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
First 3 is the number of nodes, second 3 is the number of edges.The following three lines are the edges where first number is where they start, second is where they end and third is the value.
I've thought about running Kruskal once to find a MST and then for each edge belonging in G check in(linear?) time if it can replace an edge in this MST without altering it's overall weight. If it can't it belongs in none. If it can it belongs in one but not all. I can also mark the edges in the first MST (maybe with a second value 1 or 0) and in the end check how many of them could not be replaced. These are the ones belonging in every possible MST.
This algorithm is probably O(V^2) and I am not quite sure how to write it in C++. My questions are, could we somehow reduce it's complexity?
If I add an edge to the MST how can I check (and implement in C++) if the cycle formed contains an edge that has less weight?
algorithm graph-theory
edited Jan 4 at 14:47
Shubham
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
add a comment |
Given a G(V,E) weighted(on edges) graph, I need to find the number of edges that belong in every MST as well as the number of the edges that belong in at least one but not all and the ones that belong in none.
The graph is given as input in the following form(example):
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
First 3 is the number of nodes, second 3 is the number of edges.The following three lines are the edges where first number is where they start, second is where they end and third is the value.
I've thought about running Kruskal once to find a MST and then for each edge belonging in G check in(linear?) time if it can replace an edge in this MST without altering it's overall weight. If it can't it belongs in none. If it can it belongs in one but not all. I can also mark the edges in the first MST (maybe with a second value 1 or 0) and in the end check how many of them could not be replaced. These are the ones belonging in every possible MST.
This algorithm is probably O(V^2) and I am not quite sure how to write it in C++. My questions are, could we somehow reduce it's complexity?
If I add an edge to the MST how can I check (and implement in C++) if the cycle formed contains an edge that has less weight?
algorithm graph-theory
edited Jan 4 at 14:47
Shubham
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
Are you sure you mean the number of edges and not subsets ofE? If so, the number of edges in a spanning tree is independ of the actual edge set (namely|V|-1), as discussed here.
– Codor
Jan 3 at 13:36
1
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19
add a comment |
Given a G(V,E) weighted(on edges) graph, I need to find the number of edges that belong in every MST as well as the number of the edges that belong in at least one but not all and the ones that belong in none.
The graph is given as input in the following form(example):
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
First 3 is the number of nodes, second 3 is the number of edges.The following three lines are the edges where first number is where they start, second is where they end and third is the value.
I've thought about running Kruskal once to find a MST and then for each edge belonging in G check in(linear?) time if it can replace an edge in this MST without altering it's overall weight. If it can't it belongs in none. If it can it belongs in one but not all. I can also mark the edges in the first MST (maybe with a second value 1 or 0) and in the end check how many of them could not be replaced. These are the ones belonging in every possible MST.
This algorithm is probably O(V^2) and I am not quite sure how to write it in C++. My questions are, could we somehow reduce it's complexity?
If I add an edge to the MST how can I check (and implement in C++) if the cycle formed contains an edge that has less weight?
algorithm graph-theory
edited Jan 4 at 14:47
Shubham
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
Given a G(V,E) weighted(on edges) graph, I need to find the number of edges that belong in every MST as well as the number of the edges that belong in at least one but not all and the ones that belong in none.
The graph is given as input in the following form(example):
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
First 3 is the number of nodes, second 3 is the number of edges.The following three lines are the edges where first number is where they start, second is where they end and third is the value.
I've thought about running Kruskal once to find a MST and then for each edge belonging in G check in(linear?) time if it can replace an edge in this MST without altering it's overall weight. If it can't it belongs in none. If it can it belongs in one but not all. I can also mark the edges in the first MST (maybe with a second value 1 or 0) and in the end check how many of them could not be replaced. These are the ones belonging in every possible MST.
This algorithm is probably O(V^2) and I am not quite sure how to write it in C++. My questions are, could we somehow reduce it's complexity?
If I add an edge to the MST how can I check (and implement in C++) if the cycle formed contains an edge that has less weight?
algorithm graph-theory
algorithm graph-theory
edited Jan 4 at 14:47
Shubham
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
edited Jan 4 at 14:47
Shubham
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
edited Jan 4 at 14:47
Shubham
2,01821528
edited Jan 4 at 14:47
Shubham
2,01821528
edited Jan 4 at 14:47
Shubham
2,01821528
2,01821528
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
asked Jan 3 at 13:29
Epitheoritis 32Epitheoritis 32
757
757
Are you sure you mean the number of edges and not subsets ofE? If so, the number of edges in a spanning tree is independ of the actual edge set (namely|V|-1), as discussed here.
– Codor
Jan 3 at 13:36
1
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19
add a comment |
Are you sure you mean the number of edges and not subsets ofE? If so, the number of edges in a spanning tree is independ of the actual edge set (namely|V|-1), as discussed here.
– Codor
Jan 3 at 13:36
1
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19
Are you sure you mean the number of edges and not subsets of
E? If so, the number of edges in a spanning tree is independ of the actual edge set (namely |V|-1), as discussed here.– Codor
Jan 3 at 13:36
Are you sure you mean the number of edges and not subsets of
E? If so, the number of edges in a spanning tree is independ of the actual edge set (namely |V|-1), as discussed here.– Codor
Jan 3 at 13:36
1
1
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19
add a comment |
1 Answer
1
active
oldest
votes
I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:
- Build a MST with some algorithm.
- For every edge in MST create the cut which splits MST into two parts.
- Check if there other edges with the same weight in the cut
- if there are, then every of these edges belongs to some MST,
- if there aren't, the this edge belong to unique MST.
- All other edges don't belong to any MST.
We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.
I - belongs to all, II - belongs to at least one, III - doesn't belong to any.
answered Jan 3 at 17:51
YolaYola
11.5k64774
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54023252%2fedge-properties-in-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:
- Build a MST with some algorithm.
- For every edge in MST create the cut which splits MST into two parts.
- Check if there other edges with the same weight in the cut
- if there are, then every of these edges belongs to some MST,
- if there aren't, the this edge belong to unique MST.
- All other edges don't belong to any MST.
We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.
I - belongs to all, II - belongs to at least one, III - doesn't belong to any.
answered Jan 3 at 17:51
YolaYola
11.5k64774
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
add a comment |
I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:
- Build a MST with some algorithm.
- For every edge in MST create the cut which splits MST into two parts.
- Check if there other edges with the same weight in the cut
- if there are, then every of these edges belongs to some MST,
- if there aren't, the this edge belong to unique MST.
- All other edges don't belong to any MST.
We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.
I - belongs to all, II - belongs to at least one, III - doesn't belong to any.
answered Jan 3 at 17:51
YolaYola
11.5k64774
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
add a comment |
I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:
- Build a MST with some algorithm.
- For every edge in MST create the cut which splits MST into two parts.
- Check if there other edges with the same weight in the cut
- if there are, then every of these edges belongs to some MST,
- if there aren't, the this edge belong to unique MST.
- All other edges don't belong to any MST.
We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.
I - belongs to all, II - belongs to at least one, III - doesn't belong to any.
answered Jan 3 at 17:51
YolaYola
11.5k64774
I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:
- Build a MST with some algorithm.
- For every edge in MST create the cut which splits MST into two parts.
- Check if there other edges with the same weight in the cut
- if there are, then every of these edges belongs to some MST,
- if there aren't, the this edge belong to unique MST.
- All other edges don't belong to any MST.
We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.
I - belongs to all, II - belongs to at least one, III - doesn't belong to any.
answered Jan 3 at 17:51
YolaYola
11.5k64774
edited Jan 3 at 18:17
answered Jan 3 at 17:51
YolaYola
11.5k64774
answered Jan 3 at 17:51
YolaYola
11.5k64774
answered Jan 3 at 17:51
YolaYola
11.5k64774
11.5k64774
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
add a comment |
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
2
2
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
This seems good @Yola,thank you.
– Epitheoritis 32
Jan 3 at 19:48
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54023252%2fedge-properties-in-a-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Are you sure you mean the number of edges and not subsets of
E? If so, the number of edges in a spanning tree is independ of the actual edge set (namely|V|-1), as discussed here.– Codor
Jan 3 at 13:36
1
Yes,for the example i've given output has to be:0(number of edges contained in every mst),0(number of edges in none),3(number of edges belonging in at least one but not all).
– Epitheoritis 32
Jan 3 at 13:45
I've updated my answer with description of an implementation. You can either implement Prim's algorithm yourself or find one in the Internet.
– Yola
Jan 3 at 18:19