STRUCTURAL RELIABILITY ANALYSIS OF A TECHNICAL SYSTEM USING SPANNING TREES AND CYCLES
DOI:
https://doi.org/10.32782/mathematical-modelling/2025-8-1-21Keywords:
system reliability, graph theory, spanning tree, cyclic subgraph, DFS algorithm, Kirchhoff’s theorem, redundancy, critical sectionsAbstract
In this work, a study of the structural reliability of a technical system based on graph theory was conducted by analyzing spanning trees, cyclic subgraphs, and the total number of connected subgraphs modeling its topology. The focus was on examining the quantity of spanning trees, cyclic subgraphs, and the overall number of connected subgraphs passing through each section of the system. These indicators provide a quantitative assessment of the importance of individual structural elements and determine their impact on the overall system performance.The system’s reliability was evaluated based on the number of redundant paths that ensure functionality even in the event of individual element failures. Graph theory methods were employed for the analysis, including the depth-first search (DFS) algorithm for detecting cyclic subgraphs and Kirchhoff’s theorem for calculating the number of spanning trees.The study results revealed that the most critical sections of the structure are those through which the largest number of spanning trees and cyclic subgraphs pass. The edges providing the highest number of redundant connections are key to maintaining system functionality. Their failure significantly reduces reliability, while the failure of less significant sections, through which the fewest connected subgraphs pass, has minimal impact due to alternative paths. It was concluded that the reliability of a technical system depends on the number of connected subgraphs passing through each element.The practical application of the obtained results allows for optimizing the design of technical systems, enhancing their fault tolerance, and reducing failure risks by properly distributing resources and reserving critical sections. These findings can be applied to improve the reliability of engineering networks, computer systems, and infrastructure facilities.
References
Bouziane B., Belouchrani A., Benyettou A. Reliability Analysis of Electrical Power System Using Graph Theory and Reliability Block Diagram. Proceedings IEEE International Conference on Industrial Technology. Melbourne, Australia, February 13–15, 2019. URL: https://ieeexplore.ieee.org/document/8713175 (дата звернення: 01.04.2025).
Colbourn C.J., Dinitz J.H. (Eds.). The CRC Handbook of Combinatorial Designs. Boca Raton : CRC Press, 1996. 753 p.
Ball M.O., Provan J.S. Calculating bounds on reachability and connectedness in stochastic networks. Networks. 1983. Vol. 13, № 2. P. 253–278.
Ball M.O. Computational Complexity of Network Reliability Analysis: An Overview. IEEE Transactions on Reliability. 1986. Vol. 35, № 3. P. 230–239.
Colbourn C.J. The Combinatorics of Network Reliability. Oxford : Oxford University Press, 1987. 206 p.
Ball M. O. Complexity of network reliability computations. Networks. 1980. Vol. 10, № 2. P. 153–165.
Provan J.S., Ball M.O. The complexity of counting cuts and of computing the probability that a graph is connected. Journal on Computing. 1983. Vol. 12, № 4. P. 777–788.
Shier D.R. Network Reliability and Algebraic Structures. Oxford : Clarendon Press, 1991. 280 p.
Reinschke K.J. Graph-theoretic approach to symbolic analysis of linear descriptor systems. Linear Algebra and its Applications. 1994. Vol. 197–198. P. 217–244.
Reinschke K.J. Graph-theoretic characterization of fixed modes in centralized and decentralized control. International Journal of Control. 1984. Vol. 40, № 3. P. 449–465.
Röbenack K., Reinschke K.J. On generalized inverses of singular matrix pencils. International Journal of Applied Mathematics and Computer Science. 2011. Vol. 21, № 1. P. 161–172.
