توضیحات
ABSTRACT
We present a taxonomy of fuzzy graphs that treats fuzziness in vertex existence, edge existence, edge connectivity, and edge weight. Within that framework, we formulate some standard graph-theoretic problems (shortest paths and minimum cut) for fuzzy graphs using a uni”ed approach distinguished by its uniform application of guiding principles such as the construction ofmembership grades via the ranking offuzzy numbers, the preservation ofmembership grade normalization, and the “collapsing” of fuzzy sets of graphs into fuzzy graphs. Finally, we provide algorithmic solutions to these problems, with examples. c 2002 Elsevier Science B.V. All rights reserved
INTRODUCTION
Graph theory has numerous applications to problems in systems analysis, operations research, transportation, and economics. In many cases, however, some aspects ofa graph-theoretic problem may be uncertain. For example, the vehicle travel time or vehicle capacity on a road network may not be known exactly. In such cases, it is natural to deal with the uncertainty using fuzzy set theory. This paper presents a taxonomy offuzzy graphs, providing a catalog ofthe vari- ous types of“fuzziness” possible in graphs. We also give a uni”ed presentation ofsome standard graphtheoretic problems (shortest paths and minimum cut) in terms offuzzy graphs, and provide algorithmic solutions to these problems, with examples. Fuzzy logic has developed into a large and deep subject. Zadeh [27] addresses the terminology and stresses that fuzzy graphs are a generalization of the calculi ofcrisp graphs. Several other formulations of fuzzy graph problems have appeared in the literature. Koczy [16] also gives a taxonomy offuzzy graphs – our taxonomy is larger, however, and hence extends to more applications. Klein [14] discusses a number of alternative methods for assigning membership grades to paths in a graph. Lin and Chern [19] treat the shortest path problem in terms ofa fuzzy linear program. The shortest path problem is also addressed by Okada and Gen [23], but their method is only applicable when edge weights are fuzzy numbers in the interval representation.
Year: 2002
Publisher : ELSEVIER
By : M. Blue , B. Bush , J. Puckett
File Information: English Language/ 14 Page / size: 210 KB
Download: click
سال : 2002
ناشر : ELSEVIER
کاری از : M. Blue , B. Bush , J. Puckett
اطلاعات فایل : زبان انگلیسی / 14 صفحه / حجم : KB 210
لینک دانلود : روی همین لینک کلیک کنید
نقد و بررسیها
هنوز بررسیای ثبت نشده است.