Rough set theory and digraphs. (English) Zbl 1400.05193

The authors apply rough set theory to information tables induced by the adjacency matrices of finite directed graphs in the aim to give a topological interpretation of rough set tools on digraphs. First, they interpret a generic indiscernibility relation in the digraph context as a kind of symmetry on the graph. They show that the indiscernibility relation is naturally connected to the action of the digraph automorphism group. The basic rough set tools of lower and upper approximation will then be studied on digraphs and the roughness and exactness of a digraph will be computed. Finally, the definition of extended core and its link with the discernibility matrix and the reduct hypergraph of an information table will be recalled. Interpretations for these notions in the digraph case are given and all introduced concepts will be studied on the four basic digraph families: complete bipartite digraphs, \(n\)-directed paths, \(n\)-directed cycles and \(n\)-transitive tournaments as well as on examples from social networks and patterns of flight routes between airports.


05C72 Fractional graph theory, fuzzy graph theory
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI