Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 02, 1996, pp. 11–28 Submitted: April 11, 1996. Published: August 5, 1996.

SET-THEORETICAL PROPERTIES OF EXTREME COMBINATORIAL PROBLEMS

Anatoly D. Plotnikov

Abstract. Concepts of constructive combinatorial problem and, in particular, of extreme combinatorial problem (ECP) are defined. It is announced a sequential principle of construction of the constructive combinatorial problems’ solution. This principle leads to necessity to consider ECP as system of independence with weighted elements. Auxiliary sets, which are connected to the solution of optimization problem, are defined. Concept of a normal form of the ECP is introduced. It is established that representation of a problem in normal form in some cases permits essentially to simplify an initial problem. It is introduced concepts of dual and self-dual problems. Two classes of combinatorial optimization problems, which are discerned by method of search of the admissible solution, are considered. Concept of the canonical form the ECP is introduced. It is shown that the problem in canonical form – new problem which is equivalent to initial, i.e. all optimum solutions of a problem in canonical form are the optimum solutions of an initial problem as well. The fulfilled researches in some cases simplify the search of the optimization problem solution.

(1991) A.M.S. Subject Classification Codes. 05

Key Words and Phrases. extreme combinatorial problem, auxiliary sets,normal form, canonical form, optimum solutions

Department of Applied Mathematics and Computing systems Vinnitsa State Technical University E-mail Address: aplot@cec.vstu.vinnica.ua \begin{matrix}c \\ ◯ \end{matrix}1996 Cameron University

Typeset by AMS-TEX