|
x1 becomes |
π(T) becomes |
R becomes | |
|
s = f |
x1 + q(tγ(1)) |
(7r(2),...,7r(t),7r(f))_______________ |
R + E(π(l)) |
|
1 < s < t + 1 |
x1 |
(TΓ(1), ...,7Γ(S),7Γ(S - 1), ...,7r(t)) |
R |
|
s = t + 1 |
x1 — q(π(t)) |
(7Γ(h),7r(l),...,7Γ(h - f))___________ |
R — E(π(t)) |
Without loss of generality we may assume that the algorithm is initiated at an
infeasible integral point v. Notice that every simplex σ(x1 ,π(T)) generated by
the algorithm lies in A(T) and is a Nsimplex of the simpIicial subdivision of A(T)
induced by the ∕<1-triangulation of Rn. Now in order to prove the convergence of
the algorithm, we need to borrow some notions from graph theory. First, let us
define a graph consisting of nodes and edges, denoted by Γ. We say a simplex σ is
a node if and only if it satisfies one of the following conditions:
(1) σ = {υ};
(2) σ is a Nsimplex in A(T) for some proper subset T of N with t = ∖T∖ ≥ 1 and
at least one facet of σ is ^-complete.
We say two nodes σ1 and σ2 in the graph Γ are adjacent and therefore connected
by an edge if and only if both σ1 and σ2 are in A(T) for some proper subset T of
.∖ . and one of the following cases occurs:
(1) σ1 and σ2 are both Nsimplices and share a common Т-complete facet;
(2) either σ1 is a Т-complete facet of σ2 and σ2 is a Nsimplex or σ2 is a ^-complete
facet of σ1 and σ1 is a Nsimplex.
Observe that since the above relationship is symmetric, the edges are not necessarily
ordered. Finally, we define the degree of a node σ in the graph by the number of
nodes being connected by an edge to σ, denoted by deg(σ). By adopting the
standard argument in van der Laan and Talman [5, 6], we come to the following
observation.