Given an n by n matrix of 0s and 1s, find the maximum number of 1s you can remove if you can only remove 1s...
up vote
3
down vote
favorite
This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if at the current time there is another 1 in the same row or column as the 1 to be removed. What is an algorithm to calculate the maximum number of 1s that can be removed for any such matrix?
I suspect this has something to do with graph theory (treating the matrix as an adjacency matrix) or possibly linear algebra, but I'm not certain. Any advice is appreciated.
We did figure out the following: treating the matrix as a directed graph, where a 1 at (i,j) indicates an edge from i to j, then we can remove an edge from the graph iff after removing the edge there would still be an edge from i to another vertex OR there would still be a vertex from j to another vertex. So we want to remove the greatest number of edges (where we count a bidirectional edge as two different edges, one in each direction).
linear-algebra matrices graph-theory algorithms computer-science
asked Nov 23 at 3:14
ubadub
1306
add a comment |
up vote
3
down vote
favorite
This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if at the current time there is another 1 in the same row or column as the 1 to be removed. What is an algorithm to calculate the maximum number of 1s that can be removed for any such matrix?
I suspect this has something to do with graph theory (treating the matrix as an adjacency matrix) or possibly linear algebra, but I'm not certain. Any advice is appreciated.
We did figure out the following: treating the matrix as a directed graph, where a 1 at (i,j) indicates an edge from i to j, then we can remove an edge from the graph iff after removing the edge there would still be an edge from i to another vertex OR there would still be a vertex from j to another vertex. So we want to remove the greatest number of edges (where we count a bidirectional edge as two different edges, one in each direction).
linear-algebra matrices graph-theory algorithms computer-science
asked Nov 23 at 3:14
ubadub
1306
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if at the current time there is another 1 in the same row or column as the 1 to be removed. What is an algorithm to calculate the maximum number of 1s that can be removed for any such matrix?
I suspect this has something to do with graph theory (treating the matrix as an adjacency matrix) or possibly linear algebra, but I'm not certain. Any advice is appreciated.
We did figure out the following: treating the matrix as a directed graph, where a 1 at (i,j) indicates an edge from i to j, then we can remove an edge from the graph iff after removing the edge there would still be an edge from i to another vertex OR there would still be a vertex from j to another vertex. So we want to remove the greatest number of edges (where we count a bidirectional edge as two different edges, one in each direction).
linear-algebra matrices graph-theory algorithms computer-science
asked Nov 23 at 3:14
ubadub
1306
This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if at the current time there is another 1 in the same row or column as the 1 to be removed. What is an algorithm to calculate the maximum number of 1s that can be removed for any such matrix?
I suspect this has something to do with graph theory (treating the matrix as an adjacency matrix) or possibly linear algebra, but I'm not certain. Any advice is appreciated.
We did figure out the following: treating the matrix as a directed graph, where a 1 at (i,j) indicates an edge from i to j, then we can remove an edge from the graph iff after removing the edge there would still be an edge from i to another vertex OR there would still be a vertex from j to another vertex. So we want to remove the greatest number of edges (where we count a bidirectional edge as two different edges, one in each direction).
linear-algebra matrices graph-theory algorithms computer-science
linear-algebra matrices graph-theory algorithms computer-science
asked Nov 23 at 3:14
ubadub
1306
asked Nov 23 at 3:14
ubadub
1306
edited Nov 23 at 3:45
asked Nov 23 at 3:14
ubadub
1306
asked Nov 23 at 3:14
ubadub
1306
asked Nov 23 at 3:14
ubadub
1306
1306
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.
answered Nov 23 at 4:09
user1551
71.1k566125
add a comment |
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',
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%2f3009931%2fgiven-an-n-by-n-matrix-of-0s-and-1s-find-the-maximum-number-of-1s-you-can-remov%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
up vote
2
down vote
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.
answered Nov 23 at 4:09
user1551
71.1k566125
add a comment |
up vote
2
down vote
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.
answered Nov 23 at 4:09
user1551
71.1k566125
add a comment |
up vote
2
down vote
up vote
2
down vote
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.
answered Nov 23 at 4:09
user1551
71.1k566125
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.
answered Nov 23 at 4:09
user1551
71.1k566125
edited Nov 23 at 5:14
answered Nov 23 at 4:09
user1551
71.1k566125
answered Nov 23 at 4:09
user1551
71.1k566125
answered Nov 23 at 4:09
user1551
71.1k566125
71.1k566125
add a comment |
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2fmath.stackexchange.com%2fquestions%2f3009931%2fgiven-an-n-by-n-matrix-of-0s-and-1s-find-the-maximum-number-of-1s-you-can-remov%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
