Поиск максимального независимого множества в нечетком графе
Another Title
Search for the maximum-size independent set in a fuzzy graph
Bibliographic entry
Герман, Ю. О. Поиск максимального независимого множества в нечетком графе / Ю. О. Герман, О. В. Герман // Прикладная информатика. - 2015. - Т. 10, № 2. - С. 132-138.
Abstract
Представлен оригинальный подход к отысканию максимального независимого множества (максимальной клики) в нечетком графе. Подход базируется на представлении нечетких отношений формулами многозначных логик Я. Лукасевича и использованием их для интерпретации модальных отношений. Модальность типа «возможно» интерпретируется формулой трехзначного исчисления со значением истинности не ниже 0,5, модальность типа «необходимо» интерпретируется формулой трехзначного исчисления со значением истинности, равным 1. Введены правила исчисления выводов в нечетких модальных системах, позволяющие находить трехзначные эквиваленты произвольных модальных формул.
Abstract in another language
Аn original approach to find a maximum-size independent set in a fuzzy graph is presented together with the necessary formalization technique. The approach is oriented at practical usage in applied artificial intelligent systems using fuzzy logic and modal logic concepts. The problem may be encountered in face recognition with some possible distortions. The vertices stand for the points in the face image with approximately similar color and brightness. Obviously, in the case of image distortion the arcs in the graph may be assigned with the values in 0,1-diapason. A fuzzy graph contains some nodes (arcs) with indefinite measure of their belonging to the graph. The situation may appear when no constrict classifying rules exist as explained in the paper. One can use a measure of 0.5 to interpret indefiniteness. This an interpretation enables one to apply modal logic for problem formalization and solving. The modality of the type «possible» is interpreted by the 3-valued formula with truth value not less than 0.5; the modality of the type «necessary» is interpreted by the 3-valued formula with the truth value equal to 1. The approach represented in the paper may be interesting for the researchers engaged in the recognition and classifying problems.