Biology Reference
In-Depth Information
that
φ
(
m
∗
)
v
,v
1
,v
2
,...,v
|W|
}
G
, we conclude
≥|W|
+1, and since
η
(
{
) solves
that
φ
(
m
∗
)=
|W|
+1.
Our next goal is to calculate
φ
(2) for acyclic graphs. The key observation in
this case is that the most complicated subgraphs induced by a solution are paths.
To motivate this intuition, consider the diversity graph in Fig. 6.2. Notice that both
η
(
v
1
,v
3
v
2
,v
4
w
1
) but that the path
v
1
,w
1
,v
3
{
}
) and
η
(
{
}
) are solutions to
γ
(
{
}
has the advantage over
v
2
,w
1
,v
4
since the single node
v
5
can be appended to
v
1
,v
3
,v
5
w
1
,w
2
the path so that
η
(
). If we had instead selected
v
2
,w
1
,v
4
, then both
v
3
and
v
5
would have been needed so that
η
(
{
}
) solves
γ
(
{
}
v
2
,v
3
,v
4
,v
5
{
}
)
). It is clear in this example that
φ
(2) = 3 and that
m
∗
=2.
The intuition is that we want to decompose the graph into longest paths, a process
explained by Algorithm 6.1. The fact that this technique minimizes the number of
paths is established in Theorem 6.8. The proof is by induction on
w
1
,w
2
solved
γ
(
{
}
|W|
and relates
φ
(2) as defined on (
V
,
W
,
E
) to
φ
(2) as defined on one of its subgraphs.
Algorithm 6.1.
Theorem 6.8 shows that this algorithm calculates
φ
(2).There-
moval of the path in Step 4 means that all nodes and edges in
P
k
are removed.
An Algorithm to Decompose the acyclic bipartite graph
(
V,W,E
)
into the Fewest Paths
Set
k
=0and (
V
k
,W
k
, E
k
)=(
V,W, E
).
Step 1:
Step 2:
Find the longest path in (
V
k
,W
k
, E
k
),say
P
k
. If no path exists, set
P
k
=
∅
.
If
P
k
=
∅
Step 3:
, stop.
Step 4:
Set (
V
k
+1
,W
k
+1
, E
k
+1
)=(
V
k
,W
k
, E
k
)
\P
v
.
Step 5:
Increase
k
by 1.
Step 6:
Go to Step 2.
Theorem 6.8.
Let
(
,η,γ
)
be an acyclic diversity graph. Then Algo-
rithm 6.1 calculates
φ
(2)
, and in particular, if
k
is the number of paths found
by the algorithm, then
φ
(2) =
V
,
W
,
E
|W|
+
k
.
Proof.
=1, Algorithm 6.1 clearly finds an optimal solution. Assume the
result is true as long as
If
|W|
|W| ≤
q
.Let(
V
,
W
,
E
,η,γ
) be an acyclic diversity graph
with
|W|
=
q
+1. Apply Algorithm 6.1 to (
V,W,E
) and let
P
1
,P
2
,...,P
k
be
the paths in non-increasing length found by the algorithm. Denote the last path as
P
k
=
v
1
,w
1
,v
2
,w
2
,...,w
r
,v
r
+1
.Let
W
=
w
r
E
=
(
w
r
,v
):
W\{
}
and
E\{
N
(
w
r
)
v
∈
}
.
Search WWH ::
Custom Search