Penerapan Teori Graf dalam Kehidupan Sehari-Hari

M. Fiqram Chan Safetra; Nayla Desviona; Helmina Helmina; Amelia Rianti; M.Rezan Prayogi

doi:10.62383/algoritma.v4i1.923

Authors

M. Fiqram Chan Safetra Universitas Muhammadiyah Jambi
Nayla Desviona Universitas Muhammadiyah Jambi
Helmina Helmina Universitas Muhammadiyah Jambi
Amelia Rianti Universitas Muhammadiyah Jambi
M.Rezan Prayogi Universitas Muhammadiyah Jambi

DOI:

https://doi.org/10.62383/algoritma.v4i1.923

Keywords:

Cycle Detection Algorithm, Digital Social Networks, Discrete Mathematics, Graph Theory, Transportation Systems

Abstract

Graph theory as a branch of discrete mathematics has experienced significant development in its application to modern complex network systems, particularly in digital social networks and transportation systems. This research aims to analyze fundamental concepts of graph theory, examine characteristics of cycle detection algorithms along with their computational complexity, investigate their application in digital social network analysis, and explore their implementation in digital transportation system optimization. The research method employs a qualitative approach with library research focusing on scientific literature from 2020-2025 period from accredited academic databases such as Scopus, Web of Science, and IEEE Xplore, utilizing thematic analysis techniques to identify meaningful patterns from the examined literature. Research findings indicate that fundamental graph theory concepts including vertices, edges, and graph classifications form the foundation for relational structure modeling. Cycle detection algorithms such as Depth-First Search, Union-Find, and Tarjan demonstrate effectiveness with O(V+E) complexity for large-scale graphs. Applications in digital social networks facilitate community identification through Multi-View Clustering, centrality analysis for influencer detection, and understanding viral information dissemination patterns. Implementation in digital transportation systems demonstrates route planning optimization using Dijkstra and Bellman-Ford algorithms, vulnerability analysis through articulation point and bridge identification, and bottleneck detection with betweenness centrality. The research concludes that integration of graph theory in discrete mathematics education enhances critical thinking skills and real-world application understanding, with recommendations for algorithm development for massive dynamic graphs and machine learning integration in graph algorithm optimization.

Downloads

Download data is not yet available.

References

Andriani, A., Damanik, N. G., Damanik, T., Kembaren, S. N. B., Hutagalung, C. F., Harahap, D. M., Manik, S. G., Silitonga, N. S. S., & Haris, D. (2025). Studi literatur: Pembelajaran teori graf sebagai alat untuk meningkatkan keterampilan berpikir kritis siswa. Jurnal Riset HOTS Pendidikan Matematika, 5(2), 670–680. https://doi.org/10.51574/kognitif.v5i2.2381

Awanis, Z. Y., Aini, Q., Switrayni, N. W., Wardhana, I. G. A. W., & Asmarani, Y. (2023). Pengenalan konsep teori graf di Madrasah Aliyah Manhalul Ma’Arif Darek, Lombok Tengah, Nusa Tenggara Barat. Jurnal Pepadu, 4(1), 95–102.

Fang, S. G., Huang, D., Cai, X. S., Wang, C. D., He, C., & Tang, Y. (2024). Efficient multi-view clustering via unified and discrete bipartite graph learning. IEEE Transactions on Neural Networks and Learning Systems, 35(8), 11436–11447. https://doi.org/10.1109/TNNLS.2023.3261460

Gao, P., Kamiński, B., MacRury, C., & Prałat, P. (2022). Hamilton cycles in the semi-random graph process. European Journal of Combinatorics, 99, 103423. https://doi.org/10.1016/j.ejc.2021.103423

Goldenberg, D. (2021). Social network analysis: From graph theory to applications with Python. Proceedings of the Israeli Python Conference (PyCon ’19), 1–9. https://doi.org/10.13140/RG.2.2.36809.77925

Guze, S. (2019). Graph theory approach to the vulnerability of transportation networks. Algorithms, 12(2), Article 270. https://doi.org/10.3390/a12020270

Indah, R. P., & Farida, A. (2023). Efikasi diri mahasiswa pada perkuliahan matematika diskrit. Jurnal Derivat: Jurnal Matematika dan Pendidikan Matematika, 10(3), 169–179. https://doi.org/10.31316/jderivat.v10i3.4744

Kalpokas, N., & Radivojevic, I. (2021). Adapting practices from qualitative research to tell a compelling story: A practical framework for conducting a literature review. The Qualitative Report, 26(5), 1546–1566. https://doi.org/10.46743/2160-3715/2021.4749

Karoński, M., Overman, E., & Pittel, B. (2020). On a perfect matching in a random digraph with average out-degree below two. Journal of Combinatorial Theory, Series B, 143, 226–258. https://doi.org/10.1016/j.jctb.2020.03.004

Majeed, A., & Rauf, I. (2020). Graph theory: A comprehensive survey about graph theory applications in computer science and social networks. Inventions, 5(1), Article 10. https://doi.org/10.3390/inventions5010010

Maro, L., & Djaha, K. M. T. (2022). Penerapan himpunan dominasi pada graf untuk optimalisasi pembocoran pipa air minum di Kelurahan Kalabahi Barat. Jurnal Kadikma (Matematika dan Pendidikan Matematika), 13(2). https://doi.org/10.19184/kdma.v13i2.32374

Mutianingsih, N., Hadi, S., Prayitno, L. L., Sugandi, E., & Maftuh, M. S. (2025). Eksplorasi konstruksi bukti matematis mahasiswa menyelesaikan soal graf Euler: Perspektif Toulmin. Jurnal Wahana Pendidikan, 12(1), 41–52.

Pramartha, I. N. B., Kusumawati, N. M. R., Dewi, N. P. T. T., Sudiatmika, I. P. G. A., & Jayanti, N. W. S. (2024). Implementasi e-assessment higher order thinking skills (HOTS) pada model problem posing pada mata kuliah matematika diskrit. Jurnal Riset dan Inovasi Pembelajaran, 4(3), 1925–1937. https://doi.org/10.51574/jrip.v4i3.2060

Putri, T. N., Nasution, D. A., Sari, N., Soraya, H., Ramadhani, H. P., Tania, N. S., Wahidah, K., Sipahutar, I. Z., & Haris, D. (2024). Analisis teori graf pada jaringan komunikasi dengan model pembelajaran kolaboratif di kelas matematika menggunakan Microsoft NodeXL. Jurnal Cendekia Ilmiah, 4(1), 1771–1777.

Siahaan, F. B., Harahap, L. M., Sinaga, L. L., Agustina, N., & Febriana, I. (2025). Analisis kesalahan berbahasa pada buku matematika diskrit berdasarkan Pedoman Umum Ejaan Bahasa Indonesia (PUEBI). Morfologi: Jurnal Ilmu Pendidikan, Bahasa, Sastra dan Budaya, 3(2), 169–179.

Snyder, H. (2019). Literature review as a research methodology: An overview and guidelines. Journal of Business Research, 104, 333–339. https://doi.org/10.1016/j.jbusres.2019.07.039

Sulistiyah, N., Rahayuningsih, S., & Prayitno, A. (2025). Implementasi teori graf dalam pengenalan rangkaian listrik di kelas VI MI Hasyim Asy’Ari Kota Malang. Laplace: Jurnal Pendidikan Matematika, 8(1), 70–81.

Ucer, S., Ozyer, T., & Alhajj, R. (2022). Explainable artificial intelligence through graph theory by generalized social network analysis-based classifier. Scientific Reports, 12(1), Article 19419. https://doi.org/10.1038/s41598-022-19419-7

Zaman, S., Ahmed, W., Sakeena, A., Rasool, K. B., & Ashebo, M. A. (2023). Mathematical modeling and topological graph description of dominating David derived networks based on edge partitions. Scientific Reports, 13(1), Article 42340. https://doi.org/10.1038/s41598-023-42340-6

Zhan, Y., Han, R., Tse, M., Ali, M. H., & Hu, J. (2021). A social media analytic framework for improving operations and service management: A study of the retail pharmacy industry. Technological Forecasting and Social Change, 163, 120504. https://doi.org/10.1016/j.techfore.2020.120504