Representation of Fragmentary Structures by Oriented Graphs
- PDF / 127,997 Bytes
- 8 Pages / 594 x 792 pts Page_size
- 18 Downloads / 202 Views
REPRESENTATION OF FRAGMENTARY STRUCTURES BY ORIENTED GRAPHS
O. V. Kryvtsun
UDC 519.17
Abstract. This paper investigates properties of fragmentary structures and establishes a relation between them and marked acyclic digraphs with one source and also a correspondence between classes of isomorphic fragmentary structures and unmarked acyclic digraphs of certain type, which are called feasible graphs. The concepts of a dimension of a feasible graph and its corresponding isomorphic fragmentary structures are defined. An expression is obtained for the lower-bound estimate of a dimension. A theorem on properties of feasible graphs is proved. The numbers of fragmentary structures and classes of isomorphic fragmentary structures of small dimensions are counted. Keywords: fragmentary structure, partially ordered set, directed acyclic graph, hypercube. INTRODUCTION Fragmentary structures are generalizations of well-known combinatorial constructions such as matroids, greedoids, and hereditary systems [1–3]. They are frequently used to search for approximate optimal solutions to some discrete optimization problems [4–8] by applying a fragmentary algorithm for constructing a fragment that is maximal by inclusion and is a “greedy” algorithm on a fragmentary structure. By the definition from [9, 10], a fragmentary structure is an ordered pair ( X , F) , where X is a finite set, F = {E 0 , E1 , K , E n } is the family of its subsets, and E i Í X , i = 0, K , n , is such that "E i Î F, E i ¹ Æ, $ e Î E i , E i \ { e } ÎF. The elements of the set F are called feasible fragments (fragments); one-element sets are called elementary fragments; the fragment that is not a subset of any other fragment is called maximal [9]. The set X is called the universal set. It follows from the definition of the fragmentary structure ( X , F) that the family of subsets F always contains a feasible fragment, namely, the empty set (E 0 º Æ). By the definition of a fragmentary structure, each maximal fragment can be constructed by successively adding elements starting with the empty set under the condition that, at every step, the constructed set is a feasible fragment. Such an algorithm is called fragmentary. The result of operation of a fragmentary algorithm is determined by a specified linear order on the universal set X . Thus, any maximal fragment can be described by some permutation of elements from X . Let A ÎF, and let x Î X . The condition under which A È {x} Î F is called the condition of joining an element x. Note that a fragmentary algorithm is a peculiar generalization of the concept of a greedy algorithm. It is shown that if the time necessary for checking a joining condition is restricted to a polynomial of degree k , i.e., equals O ( n k ) , then the time complexity of this fragmentary algorithm equals O ( n k + 2 ) , where n is the number of elements of the universal set. Thus, if there is an algorithm of polynomial complexity by the number of elements of the universal set for checking a joining condition, then the problem of constructi
Data Loading...
