Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mce.biophys.msu.ru/archive/doc16374/eng.pdf Дата изменения: Mon Oct 1 21:29:45 2012 Дата индексирования: Mon Oct 1 21:29:44 2012 Кодировка:

ON LOCALLY-BALANCED 2-PARTITIONS OF SOME BIPARTITE GRAPHS Balikyan S.V. Yerevan State University, Department of Informatics and Applied Mathematics, Subdepartment of Discrete Mathematics and Theoretical Informatics, Shinararner 10/1, apt. 118, Yerevan, 0038, Armenia, +374(10)39-66-16, E-mail: suren@rambler.ru In this article undirected connected graphs without loops and multiple edges [1] are considered. The set of vertices of a graph G is denoted by V(G), the set of edges by E(G). The greatest degree of a vertex of a graph G is denoted by (G ) . For v V (G ) let's set (v) { V (G ) /( , v) E (G )} . 2-partition of a graph G is a function f : V (G ) {0,1} . 2-partition f of a graph G is locally-balanced1 iff for v V (G ) || { (v) / f ( ) = 1} | - | { (v ) / f ( ) = 0} || 1 , (1) 2-partition f of a graph G is locally-balanced2 iff for v V (G ) || { ( v) {v} / f ( ) = 1} | - | { ( v) {v} / f ( ) = 0} || 1 . (2) The NP-completeness of the problem of existence of locally-balanced1 2-partition for bipartite graphs G with (G ) = 3 was proved in [2]. The NP-completeness of the problem of existence of locally-balanced2 2-partition for bipartite graphs G with (G ) = 4 was proved in [3]. The problems of existence and construction of 2-partitions described above are important since they correspond to the problems concerning distribution of influences of two opposite powers, which minimizes the probability of conflicts. The subjects of a simulated system may or may not have an ability of self-defence, thus during the modeling one should use the definitions (2) or (1) respectively. Let A be the set of graphs in which arbitrary two simple cycles [1] have at most one common vertex. Here, for bipartite graphs of A a necessary and sufficient condition for existence of locally-balanced1 2-partition is obtained. References 1. . . ­ : "", 1973. 302 . 2. .., .. NP- 2- G (G) = 3 // 105, 1, 2005. C. 21-27. 3. .., .. NP- 2- G (G) = 4 // 106, 3, 2006. C. 218-226