Subgraph Enumeration

LA home
Computing
Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Subgraphs
  Brackets
  Self-Ref
  Subgraphs

also see
 Graphs
Given a graph G, enumerate all connected, vertex-induced subgraphs of G up to a given size limit.
A subgraph S of G induced by the vertices {vi1, ..., vim} of G consists of those vertices with ⟨vip, viq being an edge in S iff it is an edge in G.
G may be undirected or directed; in the latter case generate weakly connected subgraphs.
Note that a (sub-)graph must have at least one vertex although having zero edges (the empty graph) is just fine.
 
First enumerate all subgraphs containing the seed vertex v0.
Next enumerate all subgraphs containing the seed vertex v1 but not v0.
Then enumerate all subgraphs containing the seed vertex v2 but neither v0 nor v1,
and so on.
 
Given a seed, the process is recursive. At each stage a vertex that is a neighbour of the current subgraph, and that has not yet been considered, is eligible to be added to the subgraph.
An eligible vertex, v, may be added or not added to the subgraph; those are the two options for v and they are both explored recursively.
If v is added to the subgraph it may cause other vertices to become neighbours of the enlarged subgraph.
The process backtracks whenever the maximum size is reached or there are no eligible vertices to add.
The current subgraph is processed whenever a new vertex is added to it.
G= limit=

-- L. A.,  Fri. 5th, Wed. 10th Sept. 2014.

Also search for [enumerate subgraph] in the [Bib].

www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Friday, 29-Mar-2024 07:36:58 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.