Subgraph Enumeration

LA home
  N-Queens 3D

also see
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,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Sunday, 16-Jun-2024 06:34:54 UTC.

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