Difference between a sub graph and induced sub graph.
$begingroup$
I have the following paragraph in my notes:
If $G=(V,E)$ is a general graph . Let $Usubseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ ,
then $H=(U,F)$ is also a general graph and $H$ is a subgraph of $G$ .
If $F$ consists of all edges of $G$ which have endpoints in $U$ ,then $H$ is called induced subgraph of $G$ and is denoted by $G_U. $
From here both the definition of a subgraph and a induced subgraph seem same to me..
I can't understand what is the difference between them...
Please help with this..
graph-theory
asked Nov 9 '14 at 11:14
patangpatang
2891212
$endgroup$
|
show 3 more comments
$begingroup$
I have the following paragraph in my notes:
If $G=(V,E)$ is a general graph . Let $Usubseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ ,
then $H=(U,F)$ is also a general graph and $H$ is a subgraph of $G$ .
If $F$ consists of all edges of $G$ which have endpoints in $U$ ,then $H$ is called induced subgraph of $G$ and is denoted by $G_U. $
From here both the definition of a subgraph and a induced subgraph seem same to me..
I can't understand what is the difference between them...
Please help with this..
graph-theory
asked Nov 9 '14 at 11:14
patangpatang
2891212
$endgroup$
1
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
1
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
1
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
1
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49
|
show 3 more comments
$begingroup$
I have the following paragraph in my notes:
If $G=(V,E)$ is a general graph . Let $Usubseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ ,
then $H=(U,F)$ is also a general graph and $H$ is a subgraph of $G$ .
If $F$ consists of all edges of $G$ which have endpoints in $U$ ,then $H$ is called induced subgraph of $G$ and is denoted by $G_U. $
From here both the definition of a subgraph and a induced subgraph seem same to me..
I can't understand what is the difference between them...
Please help with this..
graph-theory
asked Nov 9 '14 at 11:14
patangpatang
2891212
$endgroup$
I have the following paragraph in my notes:
If $G=(V,E)$ is a general graph . Let $Usubseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ ,
then $H=(U,F)$ is also a general graph and $H$ is a subgraph of $G$ .
If $F$ consists of all edges of $G$ which have endpoints in $U$ ,then $H$ is called induced subgraph of $G$ and is denoted by $G_U. $
From here both the definition of a subgraph and a induced subgraph seem same to me..
I can't understand what is the difference between them...
Please help with this..
graph-theory
graph-theory
asked Nov 9 '14 at 11:14
patangpatang
2891212
asked Nov 9 '14 at 11:14
patangpatang
2891212
edited Nov 9 '14 at 11:22
patang
asked Nov 9 '14 at 11:14
patangpatang
2891212
asked Nov 9 '14 at 11:14
patangpatang
2891212
asked Nov 9 '14 at 11:14
patangpatang
2891212
2891212
1
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
1
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
1
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
1
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49
|
show 3 more comments
1
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
1
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
1
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
1
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49
1
1
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
1
1
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
1
1
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
1
1
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49
|
show 3 more comments
4 Answers
4
active
oldest
votes
$begingroup$
A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and
$v$ are adjacent in $H$ if and only if they are adjacent in $G$.
In other words, $H$ has the same edges as $G$ between the vertices in $H$.
A general subgraph can have less edges between the same vertices than the original one.
So, an induced subgraph can be constructed by deleting vertices (and with them all
the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
$endgroup$
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
|
show 10 more comments
$begingroup$
For an original graph G(V, E), select set of nodes V' from V.
All the existing edges E' that connect between nodes in V' must remain.
This subgraph G' is called induced subgraph.
If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.
answered Dec 19 '17 at 1:58
user3492040user3492040
111
$endgroup$
add a comment |
$begingroup$
Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=max{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
$endgroup$
add a comment |
$begingroup$
Say you have a graph $G(V,E,phi)$ now any graph $G'(V',E',phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' subseteq V$
- $E' subseteq E$
$phi'(e)=phi(e)$ for all e belonging E'
While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
$endgroup$
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
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',
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%2f1013143%2fdifference-between-a-sub-graph-and-induced-sub-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and
$v$ are adjacent in $H$ if and only if they are adjacent in $G$.
In other words, $H$ has the same edges as $G$ between the vertices in $H$.
A general subgraph can have less edges between the same vertices than the original one.
So, an induced subgraph can be constructed by deleting vertices (and with them all
the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
$endgroup$
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
|
show 10 more comments
$begingroup$
A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and
$v$ are adjacent in $H$ if and only if they are adjacent in $G$.
In other words, $H$ has the same edges as $G$ between the vertices in $H$.
A general subgraph can have less edges between the same vertices than the original one.
So, an induced subgraph can be constructed by deleting vertices (and with them all
the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
$endgroup$
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
|
show 10 more comments
$begingroup$
A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and
$v$ are adjacent in $H$ if and only if they are adjacent in $G$.
In other words, $H$ has the same edges as $G$ between the vertices in $H$.
A general subgraph can have less edges between the same vertices than the original one.
So, an induced subgraph can be constructed by deleting vertices (and with them all
the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
$endgroup$
A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and
$v$ are adjacent in $H$ if and only if they are adjacent in $G$.
In other words, $H$ has the same edges as $G$ between the vertices in $H$.
A general subgraph can have less edges between the same vertices than the original one.
So, an induced subgraph can be constructed by deleting vertices (and with them all
the incident edges), but no more edges. If additional edges are deleted, the subgraph is not induced.
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
edited Dec 19 '15 at 16:26
Jan Hrcek
1158
1158
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
answered Nov 9 '14 at 12:03
PeterPeter
48.1k1139133
48.1k1139133
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
|
show 10 more comments
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
2
2
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
$begingroup$
The edges incident with a vertex are simply the edges having the vertex as an endpoint.
$endgroup$
– Peter
Nov 9 '14 at 12:20
1
1
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
$begingroup$
The edges of the REMAINING vertices are not allowed to be deleted, but deleting a vertex, of course, deletes the edges ending in this vertex.
$endgroup$
– Peter
Nov 9 '14 at 12:23
1
1
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
$begingroup$
Ah, now I see what you mean. The edge $2-4$ has an endpoint in $U$, is this the problem ?
$endgroup$
– Peter
Nov 9 '14 at 13:35
1
1
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
$begingroup$
Probably, it is meant that BOTH endpoints must belong to $U$, then everything is all right. Otherwise, the formulation would probably be : with at least one endpoint in $U$.
$endgroup$
– Peter
Nov 9 '14 at 13:38
1
1
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
$begingroup$
ah ..seems to be clear now...thanks.
$endgroup$
– patang
Nov 9 '14 at 13:43
|
show 10 more comments
$begingroup$
For an original graph G(V, E), select set of nodes V' from V.
All the existing edges E' that connect between nodes in V' must remain.
This subgraph G' is called induced subgraph.
If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.
answered Dec 19 '17 at 1:58
user3492040user3492040
111
$endgroup$
add a comment |
$begingroup$
For an original graph G(V, E), select set of nodes V' from V.
All the existing edges E' that connect between nodes in V' must remain.
This subgraph G' is called induced subgraph.
If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.
answered Dec 19 '17 at 1:58
user3492040user3492040
111
$endgroup$
add a comment |
$begingroup$
For an original graph G(V, E), select set of nodes V' from V.
All the existing edges E' that connect between nodes in V' must remain.
This subgraph G' is called induced subgraph.
If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.
answered Dec 19 '17 at 1:58
user3492040user3492040
111
$endgroup$
For an original graph G(V, E), select set of nodes V' from V.
All the existing edges E' that connect between nodes in V' must remain.
This subgraph G' is called induced subgraph.
If you continue to remove some edge from E', then G' is still a subgraph of G, but no longer an induced subgraph of G.
answered Dec 19 '17 at 1:58
user3492040user3492040
111
answered Dec 19 '17 at 1:58
user3492040user3492040
111
answered Dec 19 '17 at 1:58
user3492040user3492040
111
answered Dec 19 '17 at 1:58
user3492040user3492040
111
111
add a comment |
add a comment |
$begingroup$
Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=max{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
$endgroup$
add a comment |
$begingroup$
Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=max{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
$endgroup$
add a comment |
$begingroup$
Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=max{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
$endgroup$
Let G(V, E) be a graph and U is subset of V. For a induced subgraph, say H(U, F) we proceed as
Collect all possible subgraphs, say $H_1(U, F_1)$, $H_2(U, F_2)$ ,..., $H_n(U, F_n)$ of the graph G fixing set of vertices U in $H_i$, where $F_1, F_2,...,F_n$ are subsets of E.
Find F=max${F_1, F_2,...,F_n}$
Thus, $H(U, F)=max{H_1(U, F_1), H_2(U, F_2) ,..., H_n(U, F_n)}$ is a induced subgraph of the graph G with respect to U.
M. Javaid
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
edited Sep 8 '16 at 7:45
user99914
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
answered Feb 14 '15 at 9:52
M. JavaidM. Javaid
111
111
add a comment |
add a comment |
$begingroup$
Say you have a graph $G(V,E,phi)$ now any graph $G'(V',E',phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' subseteq V$
- $E' subseteq E$
$phi'(e)=phi(e)$ for all e belonging E'
While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
$endgroup$
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
add a comment |
$begingroup$
Say you have a graph $G(V,E,phi)$ now any graph $G'(V',E',phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' subseteq V$
- $E' subseteq E$
$phi'(e)=phi(e)$ for all e belonging E'
While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
$endgroup$
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
add a comment |
$begingroup$
Say you have a graph $G(V,E,phi)$ now any graph $G'(V',E',phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' subseteq V$
- $E' subseteq E$
$phi'(e)=phi(e)$ for all e belonging E'
While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
$endgroup$
Say you have a graph $G(V,E,phi)$ now any graph $G'(V',E',phi')$ can be a sub-graph of G only if it satisfies all the 3 conditions
- $V' subseteq V$
- $E' subseteq E$
$phi'(e)=phi(e)$ for all e belonging E'
While for constructing an induces subdigraph you first take a subset say W of vertex set V, then draw all the edges that lie between all those vertices(unlike a subgraph here you don't have the option to not chose an edge) be careful not to choose an edge that has one vertex in W but one not belonging to W.
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
edited Jan 22 at 18:29
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
answered Jan 21 at 16:48
Divesh KumarDivesh Kumar
11
11
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
add a comment |
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
1
1
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
$begingroup$
Hi! Welcome to MSE. Please use MathJax to format your answer so that it's much easier to understand
$endgroup$
– Ankit Kumar
Jan 21 at 17:15
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.
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%2f1013143%2fdifference-between-a-sub-graph-and-induced-sub-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
1
$begingroup$
Consider an induced subgraph, and then remove some of its edges. Is it still an induced subgraph? Is it a subgraph?
$endgroup$
– Tuomo Lempiäinen
Nov 9 '14 at 11:31
1
$begingroup$
An INDUCED subgraph has the same edges as the original graph between the given set of vertices. A minor is, for example, a subgraph, but in general not an induced subgraph. An important difference is the merging of vertices, for example, a chain u-v-w can be replaced by u-w. If u and w are not connected in the original graph, such a subgraph would be not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:37
$begingroup$
@Peter can you just elaborate your example as I don't know what a minor is ?
$endgroup$
– patang
Nov 9 '14 at 11:40
1
$begingroup$
Suppose, u and w are the only neighbours of v. Then, replacing the edges u-v and v-w by a single edge u-w produces a MINOR. A minor is a graph that can be constructed by the original graph by deleting vertices, deleting edges or merging vertices as shown. If the edge u-v does not exist in the original graph, the subgraph is not induced.
$endgroup$
– Peter
Nov 9 '14 at 11:46
1
$begingroup$
Merging vertices does not produce an indeced subgraph in general, but it produces a subgraph.
$endgroup$
– Peter
Nov 9 '14 at 11:49