Hardware Reference
In-Depth Information
Fig. 6.5
(
a
)The
union
of
graphs G
.1;2/
and G
.1;3/
;(
b
)
the
union
of graphs G
.1;2/
and
G
.3;3/
. The graphs G
.1;2/
,
G
.1;3/
,andG
.3;3/
are shown in
Fig.
6.4
c,
6.4
d, and Fig.
6.4
f,
respectively
a
Link
(E
(1,3)
,E
(2,3)
)
F
Link
(E
(1,2)
,E
(2,3)
)
Link
(E
(1,1)
,E
(1,2)
)
Link
(E
(1,2)
,E
(1,3)
)
Link
(E
(1,1)
,E
(1,3)
)
A
C
B
Link
(E
(1,1)
,E
(2,2)
)
Link
(E
(1,2)
,E
(2,2)
)
E
Link
(E
(1,3)
,E
(2,2)
)
b
Link
(E
(3,2)
,E
(3,3)
)
Link
(E
(1,1)
,E
(1,2)
)
Link
(E
(1,1)
,E
(1,3)
)
Link
(E
(1,2)
,E
(1,3)
)
A
C
B
Link
(E
(2,3)
,E
(3,2)
)
Link
(E
(1,2)
,E
(2,2)
)
Link
(E
(1,3)
,E
(2,2)
)
Link
(E
(1,1)
,E
(2,2)
)
F
E
Link
(E
(2,3)
,E
(3,3)
)
Figure
6.5
bisthe
union
of graphs G
.1;2/
and G
.3;3/
. Graphs G
.1;2/
and G
.3;3/
can
be found in Fig.
6.4
c and f, respectively. Note in graph G
.1;2/
the edge between
nodes A and C is labeled as
Link
.E
.1;1/
;E
.1;3/
/
, and in graph G
.3;3/
the edge between
nodes A and C is labeled as
Link
.E
.3;2/
;E
.3;3/
/
. Therefore the merged graph G
.1;2/
[
G
.3;3/
has two edges between nodes A and C, i.e., G
.1;2/
[
G
.3;3/
is a multigraph.
From the structure of G
layout
and the acceptability of the pin-assignment
(Sect.
6.1
), the following lemma can be derived. Note that depending on the
mapping of control pins to electrodes, G
layout
may be a multigraph (either with a
self-loop or more than one edge between some pairs of nodes) or a simple graph
(no self-loop and no more than one edge between any two distinct nodes) [
12
].
Lemma 6.2.
A pin-assignment configuration satisfies Constraint
1
and Con-
straint
2
in Sect.
6.1
if and only if the graph
G
layout
is a simple graph.
Proof.
First we assume that Constraint
1
in Lemma
6.1
is violated. Thus, an
electrode group E
group
.x/
exists in which two elements share the same control pin.
According to the definition of edges for graph G
E
x
, there will be cyclic edges
and multiple edges between two nodes. Thus G
E
x
is a multigraph. Since G
E
x
is
a subgraph of G
layout
, G
layout
is also a multigraph.
t
