An approach based on necessity measure to the fuzzy spanning tree problems

On the decision problems with defective information, the uncertain elements are often formulated as the random variables (the stochastic programming problems) even if they don’t themselves behave stochastically. However, when uncertainty is mainly derived from the lack of information, then it is proper to recognize them as having a kind of ‘fuzziness’ and formulate them as the possibility variables in fuzzy theory. In this paper, the authors propose fuzzy spanning tree problems, in which the edge costs of the graph are possibility variables. At the time of its formulation, they pay attention to the analogy between the random variables and the possibility variables and adopt a model corresponding to the probability maximum one on the chance constrained programming problems for the stochastic programming, that is, the necessity measure maximum model on the modality constrained programming problem for the possibilistic programming. Moreover, in the solution, the authors propose an efficient algorithm based on binary search, which fully exploits its problem structure. [In Japanese.]