Understanding number of unbounded regions in graph
$begingroup$
I came across following problem:
Find the minimum number of cables to be removed from an electric network with 100 connecting cables joining 50 nodes so that all circuits are removed though connection among the nodes are unhampered.
I thought I just have to remove circuits while leaving back graph connected. So I have to form a tree. Tree with $n$ nodes has $n-1$ edges. So I will need 49 edges and hence I will be able to remove $51$ edges.
My answer was correct. But not the approach. The given solution was:
Required number of cables = number of bounded regions $=e-n+1=100-50+1=51$
(If I remember it correctly,) I feel this is trying to find graph nullity which also happened to be the number of bounded regions in the graph. However how this turn out to be same as the desired number of cables?
Is it like, what I am trying to find with my approach is "maximum" number of nodes that can be removed, but the question asks for minimum number of nodes. Or am I indeed correct with my approach and both question (with "minimum") and book solution are wrong?
Update
Just gave further thought:
Bounded region is nothing but a cycle. If we remove one of its edge, we remove cycle. So when we remove $e-n+1$ edges which also turns out to be number of bounded edges from any connected graph ($1$ in $e-n+1$ being the number of connected components and hence connected graph), it leaves back a tree.
So, if we remove $e-n+k$ edges from any graph ($e:$ number of edges, $n:$ number of vertices, $k:$ number of connected components), it leaves back a forest without any cycle and with original number ($k$) of connected components.
This idea sounds a bit confusing to me. Is it correct?
graph-theory
asked Jan 17 at 9:16
aniranir
413211
$endgroup$
add a comment |
$begingroup$
I came across following problem:
Find the minimum number of cables to be removed from an electric network with 100 connecting cables joining 50 nodes so that all circuits are removed though connection among the nodes are unhampered.
I thought I just have to remove circuits while leaving back graph connected. So I have to form a tree. Tree with $n$ nodes has $n-1$ edges. So I will need 49 edges and hence I will be able to remove $51$ edges.
My answer was correct. But not the approach. The given solution was:
Required number of cables = number of bounded regions $=e-n+1=100-50+1=51$
(If I remember it correctly,) I feel this is trying to find graph nullity which also happened to be the number of bounded regions in the graph. However how this turn out to be same as the desired number of cables?
Is it like, what I am trying to find with my approach is "maximum" number of nodes that can be removed, but the question asks for minimum number of nodes. Or am I indeed correct with my approach and both question (with "minimum") and book solution are wrong?
Update
Just gave further thought:
Bounded region is nothing but a cycle. If we remove one of its edge, we remove cycle. So when we remove $e-n+1$ edges which also turns out to be number of bounded edges from any connected graph ($1$ in $e-n+1$ being the number of connected components and hence connected graph), it leaves back a tree.
So, if we remove $e-n+k$ edges from any graph ($e:$ number of edges, $n:$ number of vertices, $k:$ number of connected components), it leaves back a forest without any cycle and with original number ($k$) of connected components.
This idea sounds a bit confusing to me. Is it correct?
graph-theory
asked Jan 17 at 9:16
aniranir
413211
$endgroup$
add a comment |
$begingroup$
I came across following problem:
Find the minimum number of cables to be removed from an electric network with 100 connecting cables joining 50 nodes so that all circuits are removed though connection among the nodes are unhampered.
I thought I just have to remove circuits while leaving back graph connected. So I have to form a tree. Tree with $n$ nodes has $n-1$ edges. So I will need 49 edges and hence I will be able to remove $51$ edges.
My answer was correct. But not the approach. The given solution was:
Required number of cables = number of bounded regions $=e-n+1=100-50+1=51$
(If I remember it correctly,) I feel this is trying to find graph nullity which also happened to be the number of bounded regions in the graph. However how this turn out to be same as the desired number of cables?
Is it like, what I am trying to find with my approach is "maximum" number of nodes that can be removed, but the question asks for minimum number of nodes. Or am I indeed correct with my approach and both question (with "minimum") and book solution are wrong?
Update
Just gave further thought:
Bounded region is nothing but a cycle. If we remove one of its edge, we remove cycle. So when we remove $e-n+1$ edges which also turns out to be number of bounded edges from any connected graph ($1$ in $e-n+1$ being the number of connected components and hence connected graph), it leaves back a tree.
So, if we remove $e-n+k$ edges from any graph ($e:$ number of edges, $n:$ number of vertices, $k:$ number of connected components), it leaves back a forest without any cycle and with original number ($k$) of connected components.
This idea sounds a bit confusing to me. Is it correct?
graph-theory
asked Jan 17 at 9:16
aniranir
413211
$endgroup$
I came across following problem:
Find the minimum number of cables to be removed from an electric network with 100 connecting cables joining 50 nodes so that all circuits are removed though connection among the nodes are unhampered.
I thought I just have to remove circuits while leaving back graph connected. So I have to form a tree. Tree with $n$ nodes has $n-1$ edges. So I will need 49 edges and hence I will be able to remove $51$ edges.
My answer was correct. But not the approach. The given solution was:
Required number of cables = number of bounded regions $=e-n+1=100-50+1=51$
(If I remember it correctly,) I feel this is trying to find graph nullity which also happened to be the number of bounded regions in the graph. However how this turn out to be same as the desired number of cables?
Is it like, what I am trying to find with my approach is "maximum" number of nodes that can be removed, but the question asks for minimum number of nodes. Or am I indeed correct with my approach and both question (with "minimum") and book solution are wrong?
Update
Just gave further thought:
Bounded region is nothing but a cycle. If we remove one of its edge, we remove cycle. So when we remove $e-n+1$ edges which also turns out to be number of bounded edges from any connected graph ($1$ in $e-n+1$ being the number of connected components and hence connected graph), it leaves back a tree.
So, if we remove $e-n+k$ edges from any graph ($e:$ number of edges, $n:$ number of vertices, $k:$ number of connected components), it leaves back a forest without any cycle and with original number ($k$) of connected components.
This idea sounds a bit confusing to me. Is it correct?
graph-theory
graph-theory
asked Jan 17 at 9:16
aniranir
413211
asked Jan 17 at 9:16
aniranir
413211
edited Jan 17 at 15:33
anir
asked Jan 17 at 9:16
aniranir
413211
asked Jan 17 at 9:16
aniranir
413211
asked Jan 17 at 9:16
aniranir
413211
413211
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3076770%2funderstanding-number-of-unbounded-regions-in-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fmath.stackexchange.com%2fquestions%2f3076770%2funderstanding-number-of-unbounded-regions-in-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
