Presenting a Mathematical Programming Model for Discovering Eulerian Paths (EP) in Certain Specific Graphs
DOI:
https://doi.org/10.59615/ijie.3.2.1DOR:
https://dorl.net/dor/20.1001.1.27831906.2023.3.2.1.9Keywords:
Operations Research, Optimization, Graph Theory, Discrete Mathematics, Eulerian Path, PathfindingAbstract
In the modern era, graph theory is considered a useful tool for quantification and simplification of various dynamic components in complex systems. By representing elements as nodes and their connections as edges, graph theory can transform anything from urban planning to computer data into a meaningful mathematical language. Nowadays, numerous practical applications have been designed and developed based on graph theory. Graph theory is a branch of discrete mathematics that aims to describe and solve problems with discrete structures using points and edges. One of the problems concerning graphs is the Eulerian path problem. This research demonstrates that this problem can also be investigated from the perspective of Operations Research (OR). In a more general sense, the Eulerian path problem is a routing problem. This paper presents a pure mathematical model to describe the relationship between the variables of the Eulerian path problem. One of the features of the proposed mathematical model is its solvability by most optimization software. Finally, several numerical examples are provided to enhance the understanding of this model, and they are solved using the proposed approach. All the analyses in this research are conducted using one of the most advanced optimization software, MATLAB. The proposed mathematical model provides a systematic and efficient approach to discover Eulerian paths in specific graphs, contributing to the advancement of graph theory and its practical applications.
Downloads
References
Jafari, H., and Jafari, M. (2017). Introduction A New Approach in Engineering Economics. Journal of System Management, 3(3), 41-50.
Jafari, H., & Sheykhan, A. (2021). Integrating Developed Evolutionary Algorithm and Taguchi Method for Solving Fuzzy Facility’s Layout Problem. Fuzzy Optimization and Modeling Journal, 2(3), 24-35.
Wu, Z., Xu, W., Li, C., and Meng, X.(2022).A new approach for generator startup sequence online decision making with a heuristic search algorithm and graph theory.Energy Reports,8,678-686.
Newman, M.(2010).Networks:An Introduction.Oxford University Press.
Biggs, N., Lloyd, E., and Wilson, R.(1986).Graph Theory.Oxford University Press,1736-1936.
Mashaghi, A.(2004).Investigation of a protein complex network. European Physical Journal, 41(1),113-121.
Grandjean, M.(2016). A social network analysis of Twitter: Mapping the digital humanities community. Cogent Arts & Humanities, 3(1),117-145.
Alspach, B., Durnberger, E., and Parsons, T.D. (1985).Hamilton Cycles in Metacirculant Graphs with Prime Cardinality Blocks. North-Holland Mathematics, 115,27-34
Biggs, N. L.(1981).Mathematician.The Bulletin of the London Mathematical Society,13(2),97-120.
Pevzner, P.A., Tang, H., and Waterman, M.S.(2001).An Eulerian trail approach to DNA fragment assembly. Proceedings of the National Academy of Sciences of the United States of America,98 (17),9748-9753.
Roy, K.(2007).Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations. Journal of Computing and Information Technology, 15(1),85-92.
Watkins, J.J.(2004).Chapter 2: Knight's Tours. Across the Board: The Mathematics of Chessboard Problems, Princeton University Press,25-38.
Euler, L.(1736).Solutio problematis ad geometriam situs pertinentis.Comment. Acad. Sci. U. Petrop 8, 128-40.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Hossein Jafari, Elham Bakhsheshi, Amir-Reza Feizi-Derakhshi
This work is licensed under a Creative Commons Attribution 4.0 International License.
Owner
