حل مشكلة حذف الحافات في الرسم البياني الكامل
DOI:
https://doi.org/10.21123/bsj.2024.10128الكلمات المفتاحية:
الرسم البياني المعدل، الرسم البياني الكامل، قطر الرسم البياني، مشكلة حذف الحافات، الرسم البيانيالملخص
مع زيادة حجم الشبكة فان احتمالية الفشل في بعض مكوناتها (العقد او الحافات) يزداد، لذلك من الضروري ان تكون الشبكة قادرة على التواصل بين مكوناتها في حالة وجود خلل في بعض مكوناتها. ان احتمالية حدوث عطل في التوصيلات بين محطات الشبكة أكبر من احتمالية حدوث عطل في المحطات نفسها بسبب طبيعة عمل العديد من الشبكات. يمكن دراسة فعالية وموثوقية الشبكة باستخدام مجموعة من تقنيات نظرية البيان. ان التواصل في الشبكة هو ما يحدد مدى صلابتها (موثوقيتها) حيث ان فعالية الشبكة تتأثر عند حدوث تلف في أحد مكوناتها. يستخدم قطر الرسم البياني لقياس كفاءة عمل الشبكة من خلال قياس اقصى تأخير في استلام إشارة (رسالة) معينة او حدوث خلل في الاستلام. في هذا البحث ندرس مدى زيادة القطر للرسم البياني الناتج بعد حذف من الحافات من الرسم البياني . وايجاد أكبر قطر للرسم بياني الذي يحتوي من الرؤوس ونحصل عليه بعد حذف من الحافات من وتحديد بعد حساب
Received 08/11/2023
Revised 18/02/2024
Accepted 20/02/2024
Published Online First 20/06/2024
المراجع
Saibavani TNP, Parvathi N. Power Domination in Different Graphs with Applications. Math Model Eng Probl. 2023; 10(2): 546-550. https://doi.org/10.18280/mmep.100222.
Al-Jarah R, Kashmola MY. Modeling the Power Grid Network of Iraq. Baghdad Sci J. 2023; 20(3): 879-892. https://doi.org/10.21123/bsj.2022.6959.
Revathy AS, Nair RR, Chithra MR. A Survey on-How the Diameter of a Graph is Affected by the Removal and the Addition of Edges. Int J Appl Eng Res. 2015; 10(16): 36169–36174.
Ekinci GB, Gauci JB. The Diameter Vulnerability of the Generalized Petersen Graph {GP [tk,k]}. Turk J Math. 2018; 42(6): 2897–2915. https://doi.org/10.3906/MAT-1802-66.
Abdul-Ghani SA, Abdul-Wahhab RD, Abood EW. Securing Text Messages Using Graph Theory and Steganography. Baghdad Sci J. 2022; 19(1): 189-196. http://dx.doi.org/10.21123/bsj.2022.19.1.0189.
Schoone AA, Bodlaende HLF, Van Leeuwen J. Diameter Increase Caused by Edge Deletion. J Graph Theory. 1987; 11(3): 409–427. https://doi.org/10.1002/jgt.3190110315.
Rappoport AM, Kurochkin II. The Graph Diameter of a Distributed System with a Given Dominant Set. 9th International Conference "Distributed Computing and Grid Technologies in Sci and Edu" (GRID 2021) Dubna, Russia. 5-9 July 2021; 246–250.
Yannakakis M. Edge-Deletion Problems. SIAM J Comput. 1981; 10(2). https://doi.org/10.1137/0210021.
Chen LH, Hung LJ, Lotze H, Rossmanith P. Online Node- and Edge-Deletion Problems with Advice. Algorithmica 2021; 83. 2719–2753. https://doi.org/10.1007/s00453- 021-00840-9.
Chung FRK, Garey MR. Diameter Bounds for Altered Graphs. J Graph Theory. 1984; 8: 511–534.
Kim EJ, Milanič M, Monnot J, Picouleau C. Complexity and Algorithms for Constant Diameter Augmentation Problems. Theor Comput Sci. 15 February 2022; 904: 15 – 26. https://doi.org/10.1016/j.tcs.2021.05.020.
Swart CS. Distance Measures in Graphs and Subgraphs. Durban: University of Natal; 1996.
Alochukwu A, Dankelmann P. Edge-Fault Diameter of C_4-Free Graphs. Discrete Math. January 2024; 347(1). https://doi.org/10.1016/j.disc.2023.113678
Bouabdallah A, Delorme C, Djelloul S. Edge Deletion Preserving the Diameter of the Hypercube. Discrete Appl Math. 27 October 1995; 63(1): 91 – 95. https://doi.org/10.1016/0166-218X(95)00023-K.
Wang J-J, Ho T-Y, Ferrero D, Sung T-Y. Diameter Variability of Cycles and Tori. Inf Sci. 15 July 2008; 178(14): 2960–2967. https://doi.org/10.1016/j.ins.2008.03.008.
Fundikwa BT, Mazorodze JP, Mukwembi S. An Upper Bound on the Diameter of a 3-Edge-Connected C4-Free Graph. Indian J Pure Appl Math. 2020; 51: 1931–1938. https://doi.org/10.1007/s13226-020-0505-6.
Najim AA, Xu JM. Edge Addition and Edge Deletion of Graphs. J Univ Sci Technol China. 2006; 36(3): 254-257.
Swadi SA, Najim AA, Swadi KA. Some Exact Values for p (t, d). J Discret Math Sci Cryptogr. 2020; 23(7): 1399 – 1407. https://doi.org/10.1080/09720529.2020.1714889.
Abu-Khzam FN, Makarem N, Shehab M. An Improved Fixed-Parameter Algorithm for 2-Club Cluster Edge Deletion. Theor Comput Sci. 22 May 2023; 958: 113864. https://doi.org/10.1016/j.tcs.2023.113864.
Xu J. Topological Structure and Analysis of Interconnection Networks. Network Theory and Applications (NETA, volume 7). New York: Springer; 2001. 342 p. https://doi.org/10.1007/978-1-4757-3387-7.
التنزيلات
إصدار
القسم
الرخصة
الحقوق الفكرية (c) 2024 Anwar N. Jasim , Alaa A. Najim
هذا العمل مرخص بموجب Creative Commons Attribution 4.0 International License.
كيفية الاقتباس
