Biology Reference
In-Depth Information
does support diversity. We only consider adding nodes to
V
since in real problems
the genotypic information corresponding to
W
is defined by the biological data.
For
w
∈
W
,define
T
(
w
)=
w
=
w
N
(
w
)) .
(
N
(
w
)
∩
So,
T
(
w
) is the collection of nodes in the neighborhood of
w
that are also in
the neighborhood of another node in
W
.
We extend the neighborhood of each
w
so that the number of points in
N
(
w
)
T
(
w
) plus the number of points in the
extension is at least the number of points in
T
(
w
).Let
ˆ
\
V
(
w
) be a collection
of nodes whose cardinality is either (2
|
T
(
w
)
|−|
N
(
w
)
|
)
+
or 1+(2
|
T
(
w
)
|−
ˆ
|
N
(
w
)
|
)
+
to ensure that
|
N
(
w
)
∪
V
(
w
)
|
is even or 0. Notice that if 2
|
T
(
w
)
|≤
|
N
(
w
)
|
,then
N
(
w
) is not extended. The extended vertex and edge sets are
(
w
)
and
¯
.
¯
ˆ
ˆ
V
=
V∪
V
E
=
E∪
{
(
v,w
):
v
∈
V
(
w
)
}
w∈W
w∈W
Lemma 6.2.
Any bipartite graph
(
)
with no isolated nodes can be
extended and labeled to become a diversity graph by adding no more than
w∈W
|
V
,
W
,
E
ˆ
. In particular,
(
¯
,
¯
V
(
w
)
|
nodes to
V
V
,
W
E
)
is an extension of
(
V
,
W
,
E
)
that adds this number of nodes to
V
that supports diversity.
Proof.
The proof follows by induction on
|W|
.Let(
V,W,E
) be a bipartite
graph with no isolated nodes such that
|W|
=1.Let
W
=
{
w
}
and notice that
T
(
w
)=
∅
. Hence, (2
|
T
(
w
)
|−|
N
(
w
)
|
)
+
=0, and we add a single node to
V
if
is odd. The resulting
¯
and only if
has an even number of nodes, and from
Theorem 6.3 we know that that this graph supports diversity.
Assume the result holds if
|V|
V
|W| ≤
k
.Let(
V
,
W
,
E
) be a bipartite graph with
=
k
+1. Select
w
1
V
,
W
,
E
) be
no isolated nodes such that
|W|
∈
W
,andlet(
w
1
N
(
w
1
)
T
(
w
1
) and edges
the subgraph of (
V
,
W
,
E
) with the vertices in
{
}∪
\
incident to
w
1
removed. Extend the subgraph so that (
¯
W
,
¯
V
,
E
,η
,γ
) is a di-
n
,
respectively. The functional descriptions of
η
and
γ
below depend on
η
and
γ
,
and a slight abuse of notation is used to describe this dependence. As an example,
if
η
(
v
)=(1
,
n
and
versity graph, where the image sets of
η
and
γ
are in
{−
1
,
1
}
{−
2
,
0
,
2
}
1
,
1), we assume that (
η
(
v
)
,
1
,
1
,
1) = (1
,
−
−
1
,
1
,
1
,
1
,
1),which
allows us to embed
η
into a larger collection of haplotypes.
The argument is established in 2 cases, each of which constructs
η
and
γ
so
that (
¯
,
¯
V
,
W
E
,η,γ
) is a diversity graph. Notice that the number of nodes added to
V
is additive over
W
, and hence,
+
ˆ
ˆ
ˆ
(
w
1
)
|
V
(
w
)
|
=
|
V
|
w∈W
|
V
(
w
)
|
.
w∈W
Search WWH ::
Custom Search