Proposing a Pure Binary Linear Programming(PBLP) Model to Discover Eulerian Circuits in Complete Graphs
DOI:
https://doi.org/10.59615/ijimes.3.2.52DOR:
https://dorl.net/dor/20.1001.1.27832678.2023.3.2.6.2Keywords:
Optimization, Graph Theory, Discrete Mathematics, Operations Research, Eulerian Circuit, PathfindingAbstract
Known as a branch of Discrete Mathematics (DM), Graph Theory (GT) describes and solves problems of discrete nature through nodes (i.e., vertices) and arcs (i.e., edges). In this regard, a prominent problem is to find the Eulerian circuits. This paper indicates that the problem can be analyzed through operations research methods. In more general terms, finding the Eulerian circuits could be considered a pathfinding problem. Hence, this paper proposes a pure binary mathematical model to describe the relationship between the variables employed to find the Eulerian circuits. All the analyses in this paper were performed in MATLAB. The proposed model can be solved by many optimization software applications. Finally, several numerical examples are presented and solved through the proposed method. All the analyses in this paper were performed in MATLAB. This paper indicated that the problem(Eulerian Circuits in Complete Graphs) could be studied and solved from the perspective of operations research.
Downloads
References
Dijkstra, E.W. (1959).A note on two problems in connexion with graphs.Numerische Mathematik, 1,269-271.
Murmu, M.K., Firoz, A., Meena, S., and Jain, S.(2016). A Distributed Minimum Spanning Tree for Cognitive Radio Networks. Procedia Computer Science,89, 162-169.
Das, K.C. (2004).Maximizing the sum of squares of the degrees of a graph,Discrete Math,285,57-66.
Hoshino, R., and Kaearabayashi, K.(2011).A multi-round generalization of the traveling tournament problem and its application to Japanese baseball.European Journal of Operational Research,215,481-497.
Newman, M.(2010).Networks:An Introduction.Oxford University Press.
Biggs, N., Lloyd, E., and Wilson, R.(1986).Graph Theory.Oxford University Press,1736-1936.
Quintela, F., Redondo, R., Melchor, N., and Redondo, M.(2009).A General Approach to Kirchhoff's Laws.Education.IEEE Transactions on Communications,52,273-278.
Mashaghi, A.(2004).Investigation of a protein complex network.European Physical Journal,41(1): 113-121.
Tilley, J.A.(2017). The a-graph coloring problem.Discrete Applied Mathematics,217(2),304-317.
Fabrici, I., and Madaras, T.(2007). The structure of 1-planar graphs. Discrete Mathematics,307, (7-8),854-865.
Kutnar, K., andMaru, D.(2009.).Hamilton cycles and paths in vertex-transitive graphs_Current directions.Discrete Mathematics,309(17),5491-5500.
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.
Honiden, S., Houle, M., Sommer, C., and Wolff, M. (2009).Approximate Shortest Path Queries in Graphs Using Voronoi Duals. 6th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2009, 53-62.
Agarwal, P.K., and Aronov, B.(1997). Quasi-planar graphs have a linear number of edges. Combinatorica,17,1-9.
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.
Cezar, A.N.S., and Haroldo, G.S.(2017).Drawing graphs with mathematical programming and variable neighborhood search. Electronic Notes in Discrete Mathematics,58,207-214.
Sommer, C., Houle, M.E., Wolf, M. and Honiden, S.(2008).Approximate shortest path queries in graphs using Voronoi Duals.Tokyo, Japan,105-111.
Amirteimoori, A.R.(2012).An extended shortest path problem: A data envelopment analysis approach.Applied Mathematics Letters,25(11),1839-1843.
Xu, C., Zhang, S., Ning, B., and Li, B.(2015). A note on the number of spanning trees of line digraphs.Discrete Mathematics,338(5),688-694
Bach, L., Lysgaard, J., and Wøhlk, S.(2016).A branch-and-cut-and-price algorithm for the mixed capacitated general routing problem.Networks,68(3),161-184.
Yaghoubi, A., and Akrami, F. (2019).Proposing a new model for location-routing problem of perishable raw material suppliers with using meta-heuristic algorithms.Heliyon,5(12),20-30.
Adamo, T., Ghiani, G., and Guerriero, E.(2020).An enhanced lower bound for the time dependent travelling salesman problem.Computers and Operations Research,113(5),1-9.
Jafari, H., and 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.
Mohammadi, H., Mirzaie, K., and Mollakhalili Meybodi, M.R.(2021).Finding the Shortest Hamiltonian Cycle Using the Combined Approach of Swarm Intelligence based on Complex Networks. Quarterly Journal of Transportation Engineering,12(4),973-997.
Pour Asghar, B., Izadkhah, H., Lotfi, S., and Salehi, K.(2022).A partition-based algorithm for clustering large-scale software systems. Journal Of Signal and Data Processing,18(4),37-48.
Mehregan, M.(1998).Operational research, linear planning and its applications.18th edition, University Publishing.Tehran.
Jafari, H., and Jafari, M. (2017). Introduction A New Approach in Engineering Economics. Journal of System Management, 3(3), 41-50.
Lyeme, H. A. (2021). Mathematical modeling of the impacts of the nanoparticle in River-Aquatic system with convective cooling.Mathematics and Computational Sciences,2(3),1-13.
Jafari, M. A., and Mousaviy, N (2022).An extension of stochastic differential models by using the Grunwald-Letnikov fractional derivative. Theory of Approximation and Applications,16(1),8-13.
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.
Knuth, D.E.(2013).Two thousand years of combinatorics.in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press,7-37.
Bondy, J.A., and Murty, U.S.R.(2008).Graph Theory.Graduate Texts in Mathematics.
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Hossein Jafari, Amir-Reza Feizi-Derakhshi, Setareh Salehfard
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publisher
