EVOLUTION-MANAGER

Edit File: min_separators.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: Minimum size vertex separators</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<link rel="stylesheet" type="text/css" href="R.css" />
</head><body>

<table width="100%" summary="page for min_separators {igraph}"><tr><td>min_separators {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table>

<h2>Minimum size vertex separators</h2>

<h3>Description</h3>

<p>Find all vertex sets of minimal size whose removal separates the graph into
more components
</p>

<h3>Usage</h3>

<pre>
min_separators(graph)
</pre>

<h3>Arguments</h3>

<table summary="R argblock">
<tr valign="top"><td><code>graph</code></td>
<td>
<p>The input graph. It may be directed, but edge directions are
ignored.</p>
</td></tr>
</table>

<h3>Details</h3>

<p>This function implements the Kanevsky algorithm for finding all minimal-size
vertex separators in an undirected graph. See the reference below for the
details.
</p>
<p>In the special case of a fully connected input graph with <i>n</i> vertices,
all subsets of size <i>n-1</i> are listed as the result.
</p>

<h3>Value</h3>

<p>A list of numeric vectors. Each numeric vector is a vertex
separator.
</p>

<h3>References</h3>

<p>Arkady Kanevsky: Finding all minimum-size separating vertex sets
in a graph. <em>Networks</em> 23 533&ndash;541, 1993.
</p>
<p>JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs,
<em>Algorithmica</em> 15, 351&ndash;372, 1996.
</p>
<p>J. Moody and D. R. White. Structural cohesion and embeddedness: A
hierarchical concept of social groups. <em>American Sociological Review</em>,
68 103&ndash;127, Feb 2003.
</p>

<p><code><a href="is_separator.html">is.separator</a></code>
</p>

<h3>Examples</h3>

<pre>
# The graph from the Moody-White paper
mw &lt;- graph.formula(1-2:3:4:5:6, 2-3:4:5:7, 3-4:6:7, 4-5:6:7,
                    5-6:7:21, 6-7, 7-8:11:14:19, 8-9:11:14, 9-10,
                    10-12:13, 11-12:14, 12-16, 13-16, 14-15, 15-16,
                    17-18:19:20, 18-20:21, 19-20:22:23, 20-21,
                    21-22:23, 22-23)

# Cohesive subgraphs
mw1 &lt;- induced.subgraph(mw, as.character(c(1:7, 17:23)))
mw2 &lt;- induced.subgraph(mw, as.character(7:16))
mw3 &lt;- induced.subgraph(mw, as.character(17:23))
mw4 &lt;- induced.subgraph(mw, as.character(c(7,8,11,14)))
mw5 &lt;- induced.subgraph(mw, as.character(1:7))

min_separators(mw)
min_separators(mw1)
min_separators(mw2)
min_separators(mw3)
min_separators(mw4)
min_separators(mw5)

# Another example, the science camp network
camp &lt;- graph.formula(Harry:Steve:Don:Bert - Harry:Steve:Don:Bert,
                      Pam:Brazey:Carol:Pat - Pam:Brazey:Carol:Pat,
                      Holly   - Carol:Pat:Pam:Jennie:Bill,
                      Bill    - Pauline:Michael:Lee:Holly,
                      Pauline - Bill:Jennie:Ann,
                      Jennie  - Holly:Michael:Lee:Ann:Pauline,
                      Michael - Bill:Jennie:Ann:Lee:John,
                      Ann     - Michael:Jennie:Pauline,
                      Lee     - Michael:Bill:Jennie,
                      Gery    - Pat:Steve:Russ:John,
                      Russ    - Steve:Bert:Gery:John,
                      John    - Gery:Russ:Michael)
min_separators(camp)
</pre>

<hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div>
</body></html>