Information Technology Reference
In-Depth Information
0and
P
ð
p
0
Þ
l
p
0
Þ¼
realizable solution. When
M
1, by the non-
negative integer property of the solution,
p
0
has a single output arc.
Consider a nonleaf place
p
.Wehave
M
0
ð
ð
¼
p
Þ¼
M
ð
p
Þ
M
0
ð
p
Þ¼
Þ
P
ð
p
þ
P
ð
k
l
p
Þ
M
ð
p
Þ
¼
0. From item (iv) in Definition 5.4,
Þþ
P
ð
l
p
Þ
we have
M
ð
p
¼
1. Since
p
is a nonleaf place, we ha
ve
0, then
P
ð
p
Þ¼
M
ð
p
Þ¼
1 and
p
has only one output transition.
Theorem 5.5.
A solution is a basis solution if and only if it is a
nonnegative integer solution.
Proof:
From Theorems 5.3-5.4, it is obvious that if a solution is a
nonnegative integer solution, it is a basis solution. We prove the necessity
by contradiction that we show that the solution whose element is not a
nonnegative integer is not a basis solution.
Consider the solution whose element is not nonnegative integer. Its
SSE can be regarded as the composition of some CPs. There are two cases:
1.
Besides the leaf place of SSE, there does not exist a place with
M
ð
p
Þ >
0; and
2.
Besides the leaf place of SSE, there exists a place with
M
ð
p
Þ >
0.
In case (1), from the leaf places to the output transition of the root
place
p
0
, we add the column vectors successively. We can generate two
or more nonzero column vectors of which only the element correspond-
ing to the Web service place
p
0
is not 0, and the other elements are all 0.
This means that the column vectors are not linearly independent and the
solution is not a basis solution.
In case (2), we can extract the subgraph whose root place satisfies
M
Þ >
0 and its successive places and transitions from SSE. From the leaf
places to the output transition of the root place
p
, we add the column
vectors successively. We can then generate two or more nonzero column
vectors of which only the element corresponding to the Web service place
p
is not 0, and the other elements are all 0. This means that the column vectors
are not linearly independent, and the solution is not a basis solution.
ð
p
For example, SSE
1
in Figure 5.3 as given before satisfied the
condition of case (1). We can generate two nonzero column vectors of
which only the element corresponding to the Web service place
p
0
is 1,
