The name is absent

24

for all к, I E N. Now it immediately follows from (4.2) that

λ^k_h^3k = 0

for all h and k. Hence x^k = x⁰ and l(x^k) = 0. It is a contradiction. We complete
the proof.                                                                       □

Theorem 2.4 is a straightforward result of the above results.

5 Extension to general п-dimensional polytopes

Let M denote the set of integers { 1, ∙ ∙ ∙ , m }. The problem is to test the integral
property of a general n-dimensional polytope P given by

P = { _x ∈ Rⁿ I Ax ≤ b },

where ¾^τ = (а_г1, ...,c⅛_n) is the г-th row of the m by n matrix A for i = 1, ..., m,
and b = (δι, ∙ ∙ ∙ , δ_m)^τ is a vector of R^m. It is clear that m ≥ n ⅛ 1. As usual we
may assume that ɑɪ,..., a_m are integral vectors of Rⁿ, and b = (b₁,   , b_m)^τ is an

integral vector of R^m. Finally we assume that none of the constraints ɑʃæ ≤ bi,
i ∈ M ,is redundant, and that there is a subset J, with cardinality n ⅛ 1, of M such
that

{ x ∈ Rⁿ I ɑɪx ≤ bi, i ∈ ,J }

is an п-dimensional simplex. In the sequel we take J = N for simplicity of notation.
Compared with the labeling rule in Section 2, we have the following generalized
labeling rule.

Generalized Labeling Rule: If there is an index i E M for which ajx — bi > 0,
we assign x E Zⁿ with the label

/(æ) = min{ j E N ∖ aj x — b_j = max{ ɑɪæ — ∕y} }.

<<   23   24   25   26   27   28   29   >>

More intriguing information