Distributive lattice of minimum cut sets of a directed graph

• Autorzy: Grishkevich A.A.
• Języki publikacji: EN

Abstrakty

EN

The algebraic operations above cut sets of a digraph are entered. Is demonstrated, that the set of minimum cut sets separating two vertices of the graph, bas structure of a distributive lattice. The concept of a undecomposable (nonreducible) cut set is reviewed and the representation of set of minimum cut sets is obtained on the basis of a subset of undecomposable cut sets. The special collections of cut sets are established, in which one the nonreducible cut set is extreme. The obtained results are illustrated by example.

Słowa kluczowe

EN

distributive lattice; directed graph

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2004
• Tom: R. 4, nr 7
• Strony: 7--22
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Grishkevich A.A.

• Czestochowa University of Technology Electrical Faculty

Bibliografia

• [1] Aigner M., Combinatorial theory. Springer-Verlag, 1979.
• [2] Butyrin P.A., Grishkevitch A.A. Gaiting's algebra of minimum cut sets II Problem of Theoretical Cybernetics: Abstracts of reports to the VII Conference. Irkutsk. 1985. Part 1. P. 38-39.
• [3] Butyrin P.A., Grishkevich AA, Applying of distributive lattices for Estimations of cohesion of composite systems II Design techniques and analysis Computing systems, webs and environments: the interuniversity accumulator cell. M.: MEI. 1985. N. 81. P. 47-51.
• [4] Gratzer G., General lattice theory. Akademie-Verlag Berlin, 1978.
• [5] Grishkevich A.A., Determination of a distributive lattice on a subset of nonreducible members II Problem of optimization and economical applications: Abstracts of reports. Omsk. 1997. P. 53.
• [6] Grishuhin V.P., Papernov B.A. Submodular problems, algorithms of their solution and adjacent problems II M.: ZEMI. 1982.
• [7] Diniz E.A, Karzanov A.V., Lomonosov M.V., About a structure of a system of minimum cut sets of the graph II Studies on discretic optimization. M.: SCIENCE. 1976. P. 290-306.
• [8] Ford L., Fullkerson D., Flows in Networks, Princeton Univ. Press, Princeton, N.J. 1962.
• [9] Hu T., Integer programming and Network Flows. Addison-Wesley, Reading, Mass., 1969.
• [10] Shikhanovitch Yu. A., Introducing in modern mathematics. M.: SCIENCE, 1965.
• [11] Butyrin P.A., Grishkevich A.A., Minimum structures of mathematical models for electric circuits II Electrical Technology. 1992. N 1. P. 41-56.
• [12] Cunningham W., Minimum cuts, modular functions and matroid polyhedra II Networks. 1985. V. 15. P. 205-215.
• [13] Grishkevich A.A., An algorithm for determining the minimum cut set of a directed graph II Theses of the second International conference "Mathematical algorithms". Nizhniy Novgorod: Publishing house of the Nizhniy Novgorod university. 1995. P. 15-16.
• [14] Iri M., Application of matroid theory to engineering systems problems II Proceedings of the 6-th Conf. On Probability Theory. Bucuresti. 1981. P. 107-127.
• [15] Iri M., Fujishige S. Use of matroid theory in operations research, circuits and systems theory II Int. J. Systems Sci. 1981. Vol. 12, N 1. P. 27-54.
• [16] Nakamura M., Boolean sublattices connected with minimization problems on matroids II Math. Programming. 1982. V. 22. P. 117-120.
• [17] Picard J.C., Queyranne M., On the structure of all minimum cuts in a network and applications II Mathematical Programming Study. 1980. V. 13. P. 8-16.
• [18] Tomizawa N., Fujishige S., Historial survey of extensions of the concept of principal partition and their unifying generalization to hypermatroids II Int. Symp. On Circuits and Systems. Rome. 1982. P. 142-145.