Graphical Partitions and Graphical Relations

• Autorzy: Shaheen Tanzeela , Stell John G.

Identyfikatory

DOI

10.3233/FI-2019-1777

• Języki publikacji: EN

Abstrakty

EN

We generalize the well-known correspondence between partitions and equivalence relations on a set to the case of graphs and hypergraphs. This is motivated by the role that partitions and equivalence relations play in Rough Set Theory and the results provide some of the foundations needed to develop a theory of rough graphs. We use one notion of a partition of a hypergraph, which we call a graphical partition, and we show how these structures correspond to relations on a hypergraph having additional properties. In the case of a hypergraph with only nodes and no edges these properties are exactly the usual reflexivity, symmetry and transitivity properties required for equivalence relations on a set. We present definitions for upper and lower approximations of a subgraph with respect to a graphical partition. These generalize the well-known approximations in Rough Set Theory. We establish fundamental properties of our generalized approximations and provide examples of these constructions on some graphs.

Słowa kluczowe

EN

equivalence relation; partitions; rough sets; set theory; hypergraphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 165, nr 1
• Strony: 75--98
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Shaheen Tanzeela

• Department of Mathematics, Air University, Islamabad, Pakistan

autor

Stell John G.

• School of Computing, University of Leeds, Leeds LS2 9JT, Leeds, U.K.

Bibliografia

• [1] Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences. 1982;11(5):341-356. doi:10.1007/BF01001956.
• [2] Hell P, Nešetřil J. Graphs and Homomorphisms. Oxford University Press; 2004. ISBN: 9780198528173.
• [3] Doreian P, Batageli V, Ferligoj A. Generalized Blockmodeling. Cambridge: Cambridge University Press; 2005. URL https://doi.org/10.1017/CBO9780511584176.
• [4] Stell JG, Worboys MF. Generalizing Graphs using Amalgamation and Selection. In: Güting RH, Papadias D, Lochovosky F, editors. Advances in Spatial Databases. 6th International Symposium, SSD’99. vol. 1651 of Lecture Notes in Computer Science. Springer-Verlag; 1999. pp. 19-32. doi:10.1007/3-540-48482-5_4.
• [5] Polkowski L. Rough Sets. Mathematical Foundations. Advances in Soft Computing. Heidelberg: Physica-Verlag; 2002. doi:10.1007/978-3-7908-1776-8.
• [6] Pagliani P, Chakraborty M. A Geometry of Approximation. Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns. vol. 27 of Trends in Logic. Springer; 2008. doi:10.1007/978-1-4020-8622-9.
• [7] Stell JG. Relations on Hypergraphs. In: Kahl W, Griffin TG, editors. Relational and Algebraic Methods in Computer Science. vol. 7560 of LNCS. Springer; 2012. pp. 326-341. doi:doi.org/10.1007/978-3-642-33314-9_22.
• [8] Stell JG. Symmetric Heyting Relation Algebras with Applications to Hypergraphs. Journal of Logical and Algebraic Methods in Programming. 2015;84(3):440-455. URL https://doi.org/10.1016/j.jlamp.2014.12.001.
• [9] Berge C. Hypergraphs: Combinatorics of Finite Sets. vol. 45 of North-Holland Mathematical Library. North-Holland; 1989. ISBN-10: 0444874895.
• [10] Stell JG. Relations in Mathematical Morphology with Applications to Graphs and Rough Sets. In: Winter S, Duckham M, Kulik L, Kuipers B, editors. Conference on Spatial Information Theory, COSIT 2007. vol. 4736 of LNCS. Springer; 2007. pp. 438-454. doi:10.1007/978-3-540-74788-8_27.
• [11] Stell JG. Relational Granularity for Hypergraphs. In: Szczuka M, Kryszkiewicz M, Ramanna S, Jensen R, Hu Q, editors. Rough Sets and Current Trends in Computing. vol. 6086 of LNAI. Berlin: Springer; 2010. pp. 267-266. doi:10.1007/978-3-642-13529-3_29.
• [12] Brown R, Morris I, Shrimpton J, Wensley CD. Graphs of morphisms of graphs. Electronic Journal of Combinatorics. 2008;15:(#A1) www.combinatorics.org/ojs/.
• [13] Davey BA, Priestley HA. Introduction to Lattices and Order. 1st ed. Cambridge University Press; 1990.
• [14] Stell JG. Granulation for Graphs. In: Freksa C, Mark D, editors. Spatial Information Theory. Cognitive and Computational Foundations of Geographic Information Science. International Conference COSIT’99. vol. 1661 of Lecture Notes in Computer Science. Springer-Verlag; 1999. pp. 417-432. doi:10.1007/3-540-48384-5_27.
• [15] Schmidt RA, Stell JG, Rydeheard DE. Axiomatic and Tableau-Based Reasoning for Kt(H,R). In: Goré R, et al., editors. Advances in Modal Logic. vol. 10. College Publications; 2014. pp. 478-497. ISBN:978-1-84890-151-3.
• [16] Stell JG, Schmidt RA, Rydeheard D. A bi-intuitionistic modal logic: Foundations and automation. Journal of Logical and Algebraic Methods in Programming. 2016;85(4):500-519. URL https://doi.org/10.1016/j.jlamp.2015.11.003.
• [17] Najman L, Talbot H. Mathematical Morphology. From theory to applications. Wiley; 2010. ISBN:978-1-848-21215-2.
• [18] Bloch I. On links between mathematical morphology and rough sets. Pattern Recognition. 2000; 33(9):1487-1496. doi:10.1016/S0031-3203(99)00129-6.
• [19] Pawlak Z. Rough Set Elements. In: Polkowski L, Skowron A, editors. Rough Sets in Knowledge Discovery 1. vol. 18 of Studies in Fuzziness and Soft Computing. Heidelberg: Physica-Verlag; 1998. pp. 10-30.
• [20] Serra J. Image Analysis and Mathematical Morphology. London: Academic Press; 1982. ISBN:0126372403, 9780126372403.
• [21] Bloch I, Heijmans HJAM, Ronse C. Mathematical Morphology. In: Aiello M, Pratt-Hartmann I, van Benthem J, editors. Handbook of Spatial Logics. Springer; 2007. pp. 857-944.
• [22] Cousty J, Najman L, Dias F, Serra J. Morphological Filtering on Graphs. Computer Vision and Image Understanding. 2013;117(4):370-385. URL https://doi.org/10.1016/j.cviu.2012.08.016.
• [23] Najman L, Cousty J. A graph-based mathematical morphology reader. Pattern Recognition Letters. 2014;47:3-17. URL https://doi.org/10.1016/j.patrec.2014.05.007.
• [24] Dias F, Cousty J, Najman L. Some Morphological Operators on Simplicial Complex Spaces. In: Debled-Rennesson I, et al., editors. Discrete Geometry for Computer Imagery. vol. 6607 of Lecture Notes in Computer Science. Springer Verlag; 2011. pp. 441-452. doi:10.1007/978-3-642-19867-0_37.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).