Forests and Fuzzy Trees Fuzzy

Forests and Fuzzy Trees Fuzzy

S. Sangeetha, P. Priya

Dhanalakshmi Srinivasan College of Arts and Science for Women Autonomus Perambalur

Abstract:- In 1965, Loft A.Zadeh introduced the notion of a fuzzy subset of a set as a method for representing uncertainty. It provoked at first, a strong Abstract Fuzzy Set theory is a paradigm shift that first gained acceptance in the Far East and its successful application has ensured its adoption around the world.

INTRODUCTION:

This paper work and in designed and written to study detail about FUZZY GRAPH THEORY.

Negative reaction from influential scientists and mathematicians whom turned openly hostile. The mathematical community itself has indulged in lengthy discussions concerning the necessity, soundness and adequacy of fuzzy set theory.

It seems that although fuzzy set theory has been contested on purely theoretical grounds, most of the debate is due to its supposed rivalry with probability theory, the predominant uncertainty calculus of the past and present.

The invitation among the followers of probability theory is not without reason though even Zadeh made it quite clear right from the beginning that then option of a fuzzy set is completely non statistical in nature. Fuzzy set theory and its relatives, in particular possibility theories have been recognized as accessible means treating uncertainty, thereby entering the territory probability theory and challenging its prescriptive sovereignty.

Inspite of the controversy, the subject also attracted the attention of other mathematicians and in the following years, the field grew enormously finding applications in areas as diverse as washing machines to handwriting recognition. In its trajectory of stupendous growth, it has also come to include the theory of fuzzy algebra, fuzzy graph, fuzzy topology etc., and for the past five decades, several researchers have been working on concepts fuzzy tree, domination in fuzzy graph and so on. Based on the definitions of fuzzy sets and fuzzy relations, Azriel Rosenfeld defined fuzzy graph and studied many properties.

Nature has provided us with a mind that allows certain sloppiness in the descriptions of our environment. This sloppiness is sometimes at conflict with the rigor of formal analysis, as the following example demonstrates.

If the low blood pressure of a patient increases by a small amount, say 1 mmHg, then, because nothing significant has happened, it will still be considered low. A mean arterial blood pressure of 70 mmHg is certainly low. Therefore, by induction, every blood pressure above 70 mmHg should be low, which is, of course, not true.

This old paradox is easily resolved if one accepts that the denotation of the word low is not as sharply defined as would be required for induction to be applicable. Clearly, if 70 mmHg means low blood pressure, then 71 mmHg may still rightfully be called low, even though it is not quite as low as 70 mmHg. The higher blood pressure gets, however, the less adequate the description at all. Symbols, like the words of a language, are names that denote concepts, and concepts are abstractions from the concrete entities that constitute reality.

To formally assign the symbols a meaning they are usually associated with sets, collections of entities that represent what the symbol stands for. There are situations, however, in which the meaning of a word or symbol cannot be captured adequately by an ordinary set. The term cold for example denotes the range of cold temperatures, which may vary from context to context but, clearly, always lacks a sharp boundary.

Analogously, the set of people one might call ones friends is not as sharply defined as would be required if classical sets were to be used. It is Zadehs contribution that he provided us with a formal framework that allows it to capture the meaning of vague concepts; the theory of fuzzy sets.

Fuzzy Set theory is very much a paradigm shift that first gained acceptance in the Far East and its successful application has ensured its adoption around the world.

Definition:

A fuzzy graph G = (,) is called fuzzy forest if it has a fuzzy spanning subgraph F = (, v) which is a forest, where all arcs (x, y) not in F.

(x, y) < v (x, y)

In other words, if (x, y) G but F, there is a path in F between x and y whose strength is greater than (x, y). A connected fuzzy forest is called a fuzzy tree.

Theorem:

G is a fuzzy forest iff in any cycle of G, there is an arc

(x, y) (x, y) < (x, y) , where the prime denotes deletion of the arc (x, y) from G.

Proof:

If there is no cycle in G, the G is forest and we are done.

Let (x, y) be an arc of a cycle (x, y) < (x, y). If we delete (x, y), the resulting fuzzy graph satisfies that path

property of a fuzzy forest.

If there are still cycles in this graph, this process can be repeated.

Note at each stage no previously deleted arc is stronger than the arc currently being deleted.

Hence the path guaranteed by the property of theorem involves only arcs that have not yet been deleted. When no cycles remain, the resulting fuzzy graph is fuzzy forest F.

Let (x, y) not be an arc of F.

Thus (x, y) is one of the arcs that we deleted in the process of constructing F, and that does not involve (x, y) nor any of the arcs deleted prior to it.

If this path involves arcs that were deleted later, it can be diverted around them using a path of still stronger arcs, if any of these were deleted later, the path can be further diverted, and so on.

This process eventually stabilizes with a path consisting entirely of arcs of F. Thus G is a fuzzy forest.

Conversely,

If G is a fuzzy forest, let be any cycle, then some arc (x, y) of is not in F.

Thus by definition of a fuzzy forest we have (x, y) < v (x, y) (x, y)

Which proves the ony if part.

Theorem:

If there is at most one strongest path between any two nodes of G, the G must be a fuzzy forest.

Proof:

Suppose that there is not at most one strongest path between any two nodes of G, then there would be a cycle in G

for all arcs (x, y) of , we have (x, y) (x, y)

Thus (x, y) itself constitutes a strongest path from x to y.

If we choose (x, y) to be a weakest arc of it follows that the rest of is also a strongest path from x to y, a contradiction.

Theorem:

If G is a fuzzy forest, the arcs of F are just fuzzy bridges of G.

Proof:

An arc (x, y) not in F is certainly not a fuzzy bridge.

Since

(x, y) < v (x, y) (x, y).

Conversely,

Let (x, y) be an arc in F

If it were not a fuzzy bridge, we would have a path from x to y, not involving (x, y), of strength (x, y).

This path must involve arcs not in F.

Since F is a fuzzy forest and has no cycles.

However, by definition, any such arc (u1, v1) can be replaced by a path 1 in F of strength (u, v).

Now 1 cannot involve (x, y).

Since all its arcs are strictly stronger than (u, v) (x, y).

Thus by replacing each (u1, v1) by 1.

We can construct a path in F from x to y that does not involve (x, y) giving us a cycle in F, a contradiction. Theorem:

If G is a fuzzy tree, then internal nodes of F are fuzzy cut nodes of G.

Proof:

Let w be any node in G which is not a fuzzy end node of G.

Then by previous theorem, it is a common node of at least arc in F which are fuzzy bridges of G and by previous is

not a fuzzy cut node, for if so, there exists u,v distinct from w W is on every strongest u – v path and one such path certainly lies in F.

But w being a fuzzy end node of F, this is not possible.

Theorem:

If G = (,) is a fuzzy tree iff the following are equivalent.

Proof:

(u, v) is a fuzzy bridge (u, v) < (u, v)

Let G = (,) be a fuzzy tree and Let (u, v) be a fuzzy bridge,

Then, by previous theorem, (u, v) = (u, v).

Now, let (u, v) be an arc in G

(u, v) = (u, v).

If G* is a tree, then clearly (u, v) is a fuzzy bridge, otherwise, it follows from previous theorem that (u, v) is in F and (u, v) is a fuzzy bridge.

Conversely,

Assume that 1 2. Construct a maximum spanning tree T = (,) for G. if (u, v) is in T then (u, v) = (u, v) and hence (u, v) is a fuzzy bridge.

Now these are the only fuzzy bridge of G for if possible let (u -v ) be a fuzzy bridge of G which is not in T.

Consider a cycle C consisting of (u – v ) path being fuzzy bridges they are not weakest arcs of C and hence cannot be a fuzzy bridge.

Moreover, for all arcs (u , v ) not in T.

We have (u , v ) v (u , v ) for if possible. Let (u , v ) v (u , v ) for if possible.

Let (u , v ) < (u , v ).

since (u , v ) is not a fuzzy bridge

so v (u , v ) < (u , v ) which gives a contradiction.

since v (u , v ) is the strength of the unique u -v path in T and hence, (u , v ) = v (u , v ).

Thus T is the required spanning subgraph F, which is a tree and hence G is a fuzzy tree.

FUZZY END NODES AND FUZZY TREES

Definition:

A strong path from x to y will be called geodesic if there is no shorter strong path from x to y. for all node x, the singleton path {x} will also be called a geodesic.

The length of a geodesic from x to y will be called geodesic distance from x to y and will be denoted by dg (x, y).

Definition:

Let G be connected and

Let v be a set of nodes of G.

We define (geodesic) closure (V) of V as the set of all nodes that lie on geodesics nodes of V. Since singleton paths are geodesics, (V) V.

We say that v is a (geodesic) cover of G if (V) = G.

A minimal cover of G will be called (geodesic) basis for G.

Theorem:

If G is a tree, it has a unique basis consisting of its end nodes.

Proof:

Let z is a non-fuzzy end node of G

Then z has atleast two strong neighbors x0 and y0.

If x0 is not a fuzzy end node, it has another strong neighbor x1, if x1 had not a fuzzy end node; it has another strong

neighbor x2, and so on.

Since G had no cycles, the x is must all be distinct and since G is finite, this process must stop, so that some x must be a fuzzy end node.

Similarly some yj must be a fuzzy end node,

Hence z0 is on a geodesic between the fuzzy end nodes xi and yj.

Thus the fuzzy end nodes are a cover of G, so that by previous theorem, they must be the unique basis of G. The converse of previous theorem is false; G need not be a tree even if its fuzzy end nodes cover it.

For example, let G be a cycle with four nodes a, b, c, d and attach two additional nodes of e, f to a end c, so that e and f are fuzzy end nodes.

Evidently {e, f} is a basis of G, but G is not a tree.

Theorem:

Proof:

A connected graph G has only fuzzy end nodes iff it has only two nodes.

If G has two nodes u, v that are not neighbors, there is a geodesic from u to v has length 2.

Hence there is a node w not equal to u, v on and has two neighbors on , contradiction.

Thus any two nodes of G must be neighbors, so if G has three nodes u, v, w each of them has two neighbors contradiction. Theorem:

Deleting a fuzzy end node from G cannot change the geodesic distance between any two other nodes.

Proof:

As we saw in theorem,

An end node cant be on a strong path between any two other nodes.

A fuzzy end node cant lie on a path of length dg (x,y) between any two other nodes x and y.

Theorem:

The center of a tree consists of either one node or two neighboring nodes.

Proof:

by 1.

Let G be a tree

Let x be any node of G1 and

Let y be a node of G that is farthest form x than y.

Hence strong paths from x to u and v, together with y, from a strong cycle, which is impossible, Since G is a tree. Hence y has only one strong neighbor,

ie., it is a fuzzy end node.

Thus, removing the fuzzy end nodes from G, yielding G, decreases the eccentricity of every non-fuzzy end node of G

So that the center of G is the same as that of G. moreover, G is a connected subgraph of G, so it is still a tree.

Since a nontrivial tree has atleast two fuzzy end nodes, this process can be repeated and since G is a finite, it cant be

repeated indefinitely.

It can only stop at a tree G* which is either trivial or consists entirely of fuzzy end nodes, but in the later case G* has only two nodes, which obviously must be neighbors.

Since the center of G is the same as that of G*, is consists of either one node or two neighboring nodes.

CONCLUSION

Though the concept of the path and connectedness in fuzzy graph is analogous to crisp graph, the other concept like fuzzy tree, fuzzy bridge etc., differ from those in crisp graph. In crisp graph, a cut node whose removal from the graph disconnects the graph. But in fuzzy graph, the crisp analogues concepts fuzzy cut node, fuzzy bridge, fuzzy tree etc., have been discussed with suitable examples.

REFERENCES

1. P.Bhattacharya, some remarks on fuzzy graphs Pattern Recognition Letter 6: 297 302, 1987.

2. K.R.Bhutani, onautomorphisms of fuzzy graphs.Pattern Recognition Letter 9: 159 162, 1989.

3. K.R.Bhutani, Ohm-strong fuzzy graphs.Information science, 155(2): 103 109, 2003.

4. K.R.Bhurani and A.Rosenfeld, Geodesics in fuzzy graphs.Electronic notes in Discrete Mathematics.

5. Frank Harary, Graph theory.Addison Wesley, reading mass, 1969.

6. A Kaufmann, Introduction a law theory des Sous Ensembles, Flous. Masson, Paris ch.2: 41 189, 1973

7. C.L.Liu, Introduction to Combinatorial Mathematics.McGraw Hill, 1965.

8. J.N.Mordeson and P.S.Nair, Fuzzy Mathematics,McGraw Hill, 1965

9. J.N.Mordeson and P.S.Nair, Fuzzy graphs and Fuzzy hypergraphs.Physica-Verla, Heidelberg, 2001.

10. A.Nagoorgan and K.Ratha, On Regualr fuzzy graphs, Journal of physical science, Vol.12, 2008, 33-40.

11. M.S.Sunitha and A.Vijaykumar, Complement of Fuzzy graph. Indian J.Pure appl. Math, 33(No.9): 1451 1464, Sep2002.

12. L.A.Zadeh, Fuzzy logic and the Calculi of fuzzy rules and fuzzy graphs. A Precis, Multi. Vol. Logic, 1: 1 38, 1996.

.