In this paper the questions of definition optimum allocation of the service centres of some territory are observed. It is supposed that territory is described by fuzzy graph. In this case a task of definition optimum allocation of the service centres may be transformed into the task of definition of fuzzy antibases of fuzzy graph. The method of definition of fuzzy antibases is considered in this paper. The example of founding optimum allocation of the service centres as definition of fuzzy antibases is considered too.
There are many tasks of optimum allocation of the service centres [1]. They are an allocation of radio and TV station in some region; an allocation of military bases, which control some territory; an allocation of shops, which serve some region and so on.
However, the information about the allocation of the service centres is inaccurate or not reliable very frequently [2]. The calculation of a service degree (or quality) can be carried out by several, including to contradicting each other, criteria. For example, the definition of number and allocation of shops can be made by taking into account quality of roads, cost of ground in the given area, distance from other areas, and other criteria. Ranking of such criteria is frequently made subjectively, on the basis of the human factor.
We consider that some territory is divided into n areas. There are k service centres, which may be placed into these areas. It is supposed that each centre may be placed 1 This work has been supported by the Russian Foundation for Basic Research project № 10-01-00029а. into some stationary place of each area. From this place the centre serves all area, and also some neighbor areas with the given degree of service. The service centres can fail during the exploitation (for example, for planned or extraordinary repair). It is necessary for the given number of the service centres to define the places of their best allocation. In other words, it is necessary to define the places of k service centres into n areas such that the control of all territory is carried out with the greatest possible degree of service.
In this paper we suppose that the service degree of region is defined as the minimal meaning of service degrees of each area. Taking into account, that the service degree can not always have symmetry property (for example, by specific character and relief ~ ~ of the region) the model of such task is a fuzzy directed graph G=(X, U) [3]. Here, set X={xi}, i ∈ I={1,2,...,n} is a set of vertices and U~={<µ U < xi,x j > / < xi ,x j >> } , < xi , x j >∈ X 2 is a fuzzy set of directed edges with a membership function µ U:X2→[0,1]. The membership function µ U < xi , x j > of graph G~ = ( X ,U ) defines ~ a service degree of area j in the case when a service center is placed into area i. We assume, that the service degree has property of transitivity, i.e. if the service centre is in the area xi and serves area xj with a degree µ U < xi , x j > , and if the service centre is in area xj and serves area xk with a degree µ U < x j , xk > then a degree of service of area xk from area xi not less than µ U < xi , x j > &µ U < x j , xk > .
For consideration of questions of optimum allocation of the service centres we shall consider concepts of a fuzzy directed way and fuzzy antibase of the fuzzy graph [4].
~ ~ ~ Definition 1. Fuzzy directed way L(xi ,xm ) of fuzzy directed graph G=(X,U) is called the sequence of fuzzy directed edges from vertex xi to vertex xm: ~ L(xi , x m ) =< µ U < x i , x j > / < x i , x j >>,< µ U < x j, x k > / < x j, x k >>,.., < µ U < x l , x m > / < x l, x m >> .
~ Conjunctive durability of way µ (L (xi ,x m )) is defined as:
~ µ (L(xi ,xm )) = <xα,xβ >&∈L~(xi,xm ) µ U < xα ,xβ >.
~ Fuzzy directed way L(xi ,xm ) is called simple way between vertices xi and xm if its part is not a way between the same vertices.
Obviously, that this definition coincides with the same definition for nonfuzzy graphs. ~ ~ Definition 2. Vertex y is called fuzzy accessible of vertex x in the graph G=(X, U) if exists a fuzzy directed way from vertex x to vertex y.
The accessible degree of vertex y from vertex x, (x≠y) is defined by expression: ~ γ(x,y) = max (µ (Lα(x,y)), α =1,2,...,p, α 0,7 0,4 x2 x3 an accessible degree γ(x,x)=1.
Example 1. For the fuzzy graph 1 presented on Fig.1, vertex x5 is fuzzy accessible vertex from x1 with an accessible degree: γ (x1, x 5 ) = max{( 0,7 & 0,3); (0,6 & 0,8)} = max{0,3;0,6} = 0,6. (∀x j ∈ X )[µ Γk (xi ) (x j ) = ∀x∨l∈X µ Γk−1(xi ) (xl ) & µ U < xl , x j >] .
It is obvious, that Γ~ k(xi ) is a fuzzy subset of vertices, which it is accessible to reach from xi, using fuzzy ways of length k.
Example 2. For the fuzzy graph presented on Fig.1, we Γ 1(x1) = {< 0,7 /(x2 ) >, < 0,6 / x3 >} , Γ~ 2 (x1) = {< 0,6 / x5 >} . ~
) Definition 3. Fuzzy transitive closure Γ~(xi ) is fuzzy multiple-valued reflection: have: ~) ~ ~ Γ(xi ) = Γ 0(xi ) ∪ Γ(xi ) ∪ Γ~ 2(xi ) ∪ ... = U∞ Γ~ j(xi ) .
j=0 Here, by definition: Γ~0(xi ) = { < 1/xi > } .
) In other words, Γ~(xi ) is fuzzy subset of vertices, which it is accessible to reach from xi by some fuzzy way with the greatest possible conjunctive durability. As we consider final graphs, it is possible to put, that: ) Γ(xi ) = Un−1 Γ~ j(xi ) . ~
j=0 Γ~ −1(xi ) = Γ~ −1{Γ~ −1(xi )} , Γ~−3(xi ) = Γ~−1{Γ~−2(xi )}, ..., Γ~−k(xi ) = Γ~−1{Γ~−(k−1)(xi )} = {< µ Γ−k (xi ) (x j ) / x j >}, here x1 is defined as Γ~(x1) ={<1/ x1 >,< 0,7/ x2 >,< 0,6/ x3 >,< 0,5/ x4 >,< 0,6/ x5 >}. Example 3. For )the fuzzy graph presented on Fig.1, fuzzy transitive closure of vertex Let's define fuzzy reciprocal multiple-valued reflections Γ~ −1 , Γ~ −2 , Γ~ −3 ,..., Γ~−k as: Γ~ −1(xi ) = {< µ Γ−1(xi ) (x j ) /(x j ) >} , here (∀x j ∈ X )[µ Γ−1(xi ) (x j ) = µ U < x j , xi >] , (∀x j ∈ X )[µ Γ−k (xi ) (x j ) = ∀x∨l∈X µ Γk−1(xi ) (xl ) & µ U < x j , xl >] .
It is obvious, that Γ~−k(xi ) is a fuzzy subset of vertices, from which it is accessible to reach vertex xi, using fuzzy ways of length k.
Example 4. For the fuzzy graph presented on Fig.1, we have Γ~ −1(x1) = {< 0,4 / x4 >}, Γ~−2 (x1) = {< 0,4 / x5 >} . ) Definition 4. Fuzzy reciprocal transitive closure Γ~−(xi ) is fuzzy reciprocal multiplevalued reflection: ) Γ~ −(xi ) = Γ~ 0(xi ) ∪ Γ~ −1(xi ) ∪ Γ~ −2(xi ) ∪ ... = Un−1 Γ~ − j(xi ) .
j=0 ) In other words, Γ~−(xi ) is fuzzy subset of vertices, from which it is accessible to reach vertex xi by some fuzzy way with the greatest possible conjunctive durability. Example 5. For the )fuzzy graph presented on Fig.1, fuzzy reciprocal transitive closure of vertex x1 is Γ~− (x1) ={<1/ x1 >,< 0,3/ x2 >,< 0,4/ x3 >,< 0,4/ x4 >,< 0,4/ x5 >}.
~ ~ Definition 5. Graph G=(X,U) is named fuzzy strongly connected graph if the condition is satisfied: (∀xi ∈ X)(SΓ~) (xi ) = X) .
) ~ is the carrier of fuzzy transitive closure Γ(x i ) .
Here S) Γ~(xi )
~ ~ Differently, graph G=(X,U) is fuzzy strongly connected graph if between any two vertices there is a fuzzy directed way with the conjunctive durability which is distinct from 0.
It is easy to show, that expression (
j=1,n i=&1,n µ ij (x j ) we name a degree of strong connectivity of fuzzy graph ~ G .
~ ~ ~ Let G=(X,U) is fuzzy graph with degree of strong connectivity ρ (G) , and ~ ~ ~ G′=(X ′,U ′) is fuzzy subgraph with degree of strong connectivity ρ (G′) .
~ ~ Definition 7. Fuzzy subgraph G′=(X ′,U ′) we name maximum strong connectivity fuzzy subgraph or fuzzy strong component connectivity if there is no other subgraph ~ ~ ~ ~ ~ ~ G′′=(X ′′,U ′′) for which G′ ⊂ G′′ , and ρ (G′) ≤ ρ (G′′) .
Definition 8. A subset vertices Bα ⊂ X is called fuzzy antibase with the degree α∈[0,1], if some vertex y ∈ Bα may be accessible from any vertex x ∈ X / Bα with a degree not less α and which is minimal in the sense that there is no subset B ′ ∈ Bα , having the same accessible property.
~ Let's designate through R(B ) a fuzzy set of vertices, from which the subset B is accessible, i.e.: ~ ) R (B ) = U Γ~ −(xi ) ,
xi ∈B ) Here, Γ~ −(x i ) is a fuzzy reciprocal transitive closure of the vertex xi. Then the set Bα is fuzzy antibase with a degree α in only case, when the conditions are carried out: ~ R(Bα ) = { < µ j /x j > |x j ∈ X&(∀j=1,n )(µ j ≥ α)} ,
~
(∀B′ ⊂ Bα )[R(B′)={ < µ ′j /x j > |x j ∈ X&(∃j=1,n)(µ ′j < α)}] .
(
Property 3. In any fuzzy circuit-free graph there is just one fuzzy antibase with degree α.
Property 4. If in a fuzzy circuit-free graph an inequality α 1 < α 2 is executed, then inclusion Bα1 ⊃ Bα 2 is carried out.
Let's note interrelation between fuzzy antibases and strong connectivity fuzzy subgraphs. Following properties are true.
Property 5. If subset Bα is fuzzy antibase with degree α, then there is such subset ~ ~ X′ ⊆ X , that Bα ⊂ X ′ , and fuzzy subgraph G ′ = (X ′, U ′) has degree of strong connectivity not less α.
Property 6. If subset Bα is fuzzy antibase with degree α, then there is not such ~ ~ subset X′ ⊆ X , that X′ ⊆ Bα and fuzzy subgraph G′ = (X′, U′) has degree of strong connectivity α.
The following consequence follows from property 6:
~ Consequence 1. That in fuzzy graph G there was fuzzy antibase with degree α, ~ consisting of only one vertex, it is necessary that fuzzy graph G was strong connectivity with degree α.
Property 7. Let γ(xi,xj) is an accessible degree of vertex xj from vertex xi. Then the
following statement is true:
(∀xi,xj∈Bα)[γ(xi,xj)<α].
(
Let a set τk={Xk1, Xk2,…,Xkl} be given, where Xki is a fuzzy k-vertex antibase with the degree of αki. We define as α k = max {α k ,α k ,..., α k } . In the case τk=∅ we define 1 ~2 l αk=αk-1. Volume αk means that fuzzy graph G includes k-vertex subgraph with the accessible degree αk and doesn’t include k-vertex subgraph with an accessible degree more than αk.
Definition 5. A fuzzy set ~ B− ={<α1 /1>,<α2 / 2 >,...,<αn / n >} ~ is called a fuzzy set of antibases of fuzzy graph G .
Property 8. The following proposition is true:
0 ≤ α1 ≤ α2 ≤ ... ≤ αn = 1 .
The fuzzy set of antibases defines the greatest degree of service of all territory by the k centres of service (k∈{1,2,…,n}).
Thus, it is necessary to determine a fuzzy set of antibases for a finding of the greatest degree. 3
We will consider the method of finding a family of all fuzzy antibases with the highest degree. The given method is an analogue method for definition of all minimal fuzzy dominating vertex sets [5] and it is a generalization of the Maghout’s method for crisp graphs [6]. ~ Assume that a set Bα is a fuzzy base of the fuzzy graph G with the degree α. Then for an arbitrary vertex xi∈X, one of the following conditions must be true. a) xi∈Bα; b) if xi∉Bα, then there is a vertex xj such that it belongs to the set Bα with the degree γ(xi,xj)≥α.
In other words, the following statement is true:
(∀xi ∈ X)[xi ∈ Bα ∨ (xi ∉ Bα → (∃x j ∈ Bα|γ(xi ,x j ) ≥ α))] .
To each vertex xi∈X we assign Boolean variable pi that takes the value 1, if xi∈Bα
and 0 otherwise. We assign a fuzzy variable ξiji=α for the proposition γ(xi,xj)≥α.
Passing from the quantifier form of proposition (
Then the expression (7) may be rewrite as:
Taking into account interrelation between implication operation and disjunction
operation (α→β=α∨β ), we receive:
(
i j Φ = & (pi ∨ pi ∨ ∨ (p j&γij )) .
i j Φ = & ( ∨ (p j&γij )) .
i j Property 9. If in expression (9) further simplification on the basis of rules (8) is impossible, then everyone disjunctive member i defines antibase with the highest degree αi.
Proof. Let's consider, that further simplification is impossible in expression (9). Let, for definiteness, disjunctive member ( p1 & p 2 & ... & p k & α ), k < n,α ∈ (0,1]
Φ = i=∨1,l ( p1i & p2i & ... & pki & α i ) . is included in the expression (9).
Let's assume, that the subset X ' = {x1, x2 ,..., xk } is not antibase with degree α. Then there is some vertex, for example xk +1 ∈ X / X ' , for which the statement (∀i = 1, k )(γ ( x k +1 , xi ) < α ) is true. In other words, the accessible degree of any vertex of subset X’ from vertex xk+1 is less than value α.
We present the expression (7) in a kind: (9) (10) (11) Φ = (1p1 ∨ ξ12 p2 ∨ ... ∨ ξ1n pn ) & (ξ 21 p1 ∨ 1p2 ∨ ... ∨ ξ 2n pn ) & ... & (ξ k+1,1 p1 ∨ ξ k+1,2 p2 ∨ ...ξ k+1,k pk ∨ 1pk+1 ∨ ... ∨ ξ k+1,n pn ) & ...
& (ξ n1 p1 ∨ ξ n2 p2 ∨ ... ∨ 1pn ).
In expression (11) all coefficients ξ k +1,i < α , ∀i = 1, k . Therefore, in expression (9) all disjunctive members which do not contain variables pk +1, pk +2 ,..., pn , necessarily contain coefficients smaller value α. From here follows, that the disjunctive member (10) is not included in the expression (9). The received contradiction proves, that subset X '= {x1, x2 ,..., xk } is antibase with degree α.
Let's prove now, that the disjunctive member (10) is minimum member. We will assume the return. Then following conditions should be carried out: a) subset X ' = {x1, x2 ,..., xk } is antibase with degree β> α; or b) there is a subset X "⊂ X ' which is antibase with degree α.
Let the condition a) is satisfied. Then the next statement is true:
(∀x j , j = k + 1, n)(∃xi , i ∈ 1, k | γ ( x j , xi ) ≥ β ) .
Let's present expression Φ in the form of (11). If to make logic multiplication of each bracket against each other without rules of absorption (8) we will receive n2 the disjunctive members containing exactly n of elements, and, on one element from each bracket of decomposition (11). We will choose one of n2 disjunctive members as follows: - From the first bracket we will choose element 1p1 ; - From the second bracket - element 1p2 ; …; - From kth bracket - element 1pk ; - From (к+1)th bracket we will choose element ξ k +1,i1 pi1 such, that index i1 ∈ [1, k ] , and volume ξ k +1,i1 > β ; ξ k + 2,i2 > β , etc.; - From (к+2)th bracket - element ξ k + 2,i2 pi2 , for which index i2 ∈ [1, k ] , and volume - From nth bracket - element ξ n,in−k1 pin−k , for which index in−k ∈ [1, k ] , and volume ξ n,in−k1 > β .
Using rules of absorption (8), the received disjunctive member can be led to kind ( p1 & p 2 & ... & p k & β ' ) , in which the volume β ' = min{ ξ k +1,i2 ,ξ k + 2,i2 ,..., ξ n,in − k } ≥ β > α and which will be necessarily absorbed disjunctive member (10). (Decomposition (9) the disjunctive member cannot include the received contradiction (10)) proves impossibility of case a). Let's assume now, that the condition is satisfied. Let, for definiteness, X "= {x1, x2 ,..., xk −1} . Considering expression Φ in the form of decomposition (8), we will choose a disjunctive member as follows: - From the first bracket we will choose element 1p1 , - From the second bracket - element 1p2 , …, - From (к-1)th bracket - element 1pk −1 , - From kth bracket we will choose element ξ k ,i1 pi1 such, that index i1 ∈ [1, k − 1] , and volume ξ k ,i1 ≥ α , - From (к+1)th bracket - element ξ k +1,i2 pi2 , for which index i2 ∈ [1, k − 1] , and volume ξ k +1,i2 ≥ α , etc., - From nth bracket - element ξ n,in−k+11 pin−k+1 volume ξ n,in−k +1 ≥ α .
Using rules of absorption (8) the received disjunctive member can be led to kind ( p1 & p 2 & ... & p k −1 & α ) , in which size β = min{ξ k ,i2 ,ξ k +1,i2 ,..., ξ n,in−k +1 } ≥ α and which will be necessarily absorbed by a disjunctive member (10). (Decomposition (9) the disjunctive member cannot include the received contradiction (10)) proves impossibility of case b).
Property 9 is proved.
The following method of foundation of fuzzy antibases may be proposed on the base of property 9: ~ - We write proposition (7) for given fuzzy graph G ; - We simplify proposition (7) by proposition (8) and present it as proposition (9); - We define all fuzzy antibases, which correspond to the disjunctive members of proposition (9).
Example 6. Find all fuzzy antibases for the fuzzy graph 2 presented in Fig.2: , for which index in−k +1 ∈ [1, k − 1] , and 0,8 0,7 0,1 0,6 The vertex matrix for this graph has the following form: On the basis of the made above definition of fuzzy accessible vertex we can construct an accessible matrix N, containing accessible degrees for all pairs of vertices: Here, γij=γ(xi,xj), xi, xj∈X, Rk – the vertex matrix power k for graph. Matrix R0 is an identity matrix: We raise the contiguity matrix to 2, 3 powers. Uniting them, we find an accessible matrix: 1 0,7 N = R0 ∪ R ∪ R2 ∪ R3 = 0,6 0,6 0,8 1 0,6 0,6 0,6 0,6 1 0,6 0,6
0,6 . 1 1 The corresponding expression (7) for this graph has the following form:
Multiplying parenthesis 1 and 2, parenthesis 2 and 4 and using rules (8) we finally obtain:
~ It follows from the last equality that the graph G has 7 fuzzy antibases, and fuzzy set of antibases is defined as: ~
B− = {< 0,6 /1 >,< 0,8/ 2 >,<1/ 3 >,<1/ 4 >}.
The fuzzy set of antibases defines the next optimum allocation of the service centres: If we have 3 or more service centres then we must place these centres into vertices 1, 2, and 4. The degree of service equals 1 in this case. If we have 2 service centres then we must place these centres into vertices 2, and 4. The degree of service equals 0,8 in this case. If we have only one service centre then we can place it in any vertex. The degree of service equals 0,6 in last case.
The task of definition of optimal allocation of the service centres as the task of definition of fuzzy antibases of fuzzy graph was considered. The definition method of fuzzy antibases is the generalization of Maghout’s method for nonfuzzy graphs. It is necessary to mark that the suggested method is the method of ordered full selection, because these tasks are reduced to the task of covering, i.e. these tasks are NPcompete tasks. However, this method is effective for the graphs which have not homogeneous structure and not large dimensionality.