To describe node-tearing in rigorous mathematical terms, let the set
denote the nodes of a graph
and let
denote the edges in
, or
.
Partition the node set
into two arbitrary subsets
and
, and partition the edge set
into two subsets
and
such that:
Definition --- Section Graph Given a graph , let
, then a section graph is defined as:
where:
is incident only with
[34].
The topological condition for graph connectivity requires that the
section graph can be partitioned into m,
disconnected sub-graphs such that:
Given the topological condition, we can define the two partitions of the node set N:
where: ¯In the case of block-diagonal-bordered form matrices,
is the set of nodes in the mutually independent sub-blocks
is the set of nodes in the coupling equations
The edge-coupling condition simply requires that the edges in are not connected to edges in
and
. Consequently,
has no edges in common with
,
, and there are no edges directly interconnecting any nodes in
and
,
.
Connectivity between
and
,
, is not direct and must go through nodes in
.
Reference [34] contains the straight forward proof that
these conditions yield a block-diagonal-bordered form matrix when the
corresponding graph
is ordered by node-tearing.
In addition to ordering matrices into block-diagonal-bordered form
using node-tearing, we require that the number of coupling equations,
, is minimized over all distinct partitions
of
. The tearing
optimization problem attempts to minimize
given that:
The technique chosen to solve the graph optimization problem is based
on examining the contour of the graph [34], by developing a
contour tableau to identify independent sub-graphs. A contour-tableau
consists of three columns as illustrated in figure 13 and
a separate contour-tableau is developed for each diagonal block. The
leftmost column contains the iterating sets or the potential elements
of a set of nodes in the sub-graph . The middle
column contains the adjacency set, which contains the set of nodes
adjacent to, but not including any elements in the corresponding
iterating set. The remaining column contains the contour number or
the cardinality of the corresponding adjacency set.
Figure 13: Sample Contour Tableau for the Diagonal Block
The contour tableau is constructed by selecting the initial iterating
set element and placing
in
. Next,
all nodes adjacent to
,
, are stored in
: then
is placed in
. The next
iterating set is constructed by forming the union of the previous
iterating set and the next iterating node:
The adjacency set is updated by the formula:
and
What remains to be described are the methods to select an initial node,
select the next node, and to select an independent graph partition from
the contour tableau. Because the algorithm is attempting to minimize
, it can be shown that the selection of both the
initial node and the next node should always be the node with the
smallest number of adjacent nodes or select
such that
If there are ties, then a node is selected arbitrarily. Lastly, the
criteria to select an independent graph partition from the contour
tableau requires identifying the iterating set that has
a local minimum value of
,
. This selection
criteria is obvious because at any location in the contour tableau,
three disjoint sets are specified:
because represents the nodes adjacent to but not
included within the set
. According to the topological
condition, these nodes must be part of the coupling equations.
An example illustrating the node-tearing technique is presented in appendix B.