1
$\begingroup$

An induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset. For example:

Graph[{"A" <-> "B", "A" <-> "C", "A" <-> "F", "B" <-> "D", 
  "B" <-> "E", "D" <-> "E", "A" <-> "E", "B" <-> "F"}, 
 VertexLabels -> Automatic]

enter image description here

There is only one subgraph induced by {A, B, D, E} in the above graph: enter image description here

The InduceSubgraph function does not seem to be directly available from Mathematica.

When I use the Combinatorica package, it breaks mathematica's own Graph function.

enter image description here

So I wanted to get the induced subgraph by extracting sub-matrix. But I am not very clear how the vertex labels of the graph correspond to the labels of its adjacency matrix. So the code below is elementary and not very reliable.

Inducedgraph[g_, vlist_] := Module[{sub}, AdjacencyMatrix[g];
   sub = s[[vlist, vlist]];
   AdjacencyGraph[sub]];

Especially when vertices of a graph are labeled with letters rather than numbers, it seems more important to find reliable code.

Edit: Thanks yode for the reminder that Subgraph can do that. But I'm also interested in a custom implementation of this function.

$\endgroup$
4
  • $\begingroup$ Why don't you use code to represent your graph? Is it because you want the responser to construct? $\endgroup$
    – yode
    Aug 17, 2022 at 13:36
  • $\begingroup$ Subgraph is your after? $\endgroup$
    – yode
    Aug 17, 2022 at 13:37
  • $\begingroup$ @yode Thanks. We can get it straight away. I was under the illusion that subgraph functions can only input edges. I'll delete this simple question shortly. $\endgroup$
    – licheng
    Aug 17, 2022 at 13:59
  • $\begingroup$ @yode Or change the question to how to customize a function to get a induced subgraph. The implementation is also that I'm interested in, too $\endgroup$
    – licheng
    Aug 17, 2022 at 14:05

1 Answer 1

2
$\begingroup$
g1 = Graph[{"A" <-> "B", "A" <-> "C", "A" <-> "F", "B" <-> "D", "B" <-> "E", "D" <-> "E", "A" <-> "E", "B" <-> "F"}, VertexLabels -> Automatic]  
vlist={"A", "B", "D", "E"}

Using the built in function:

Subgraph[g1, vlist]

enter image description here

Custom Function: (Creates a graph from edges where both vertices are in the list)

InducedGraph[g_, v_] := Module[{},
  Graph[Select[EdgeList[g], 
    MemberQ[v, First[#]] && MemberQ[v, Last[#]] &], 
   VertexLabels -> Automatic]]
InducedGraph[g1, vlist]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.