خوارزميات لهيمنات متنوعة في نظرية البيان
Algorithms for Various Dominations in Graph Theory
- الباحث
- احسان مزهر رشيد حسون
- المشرف
- احمد عبد علي عمران
- الجامعة
- جامعة بابل
- الكلية / القسم
- كلية التربية للعلوم الصرفة / الرياضيات
- الشهادة
- دكتوراه
- السنة
- 2022
- لغة الرسالة
- انكليزي
- الكلمات المفتاحية
- Domination; Graph Theory; Algorithms; Fuzzy Graphs
الملخص
أدت التطبيقات المختلفة للهيمنة والعمل الحديث على أشكال مختلفة من الهيمنة في نظرية البيان إلى اهتمامنا باستكشاف أنواع خاصة جديدة من الهيمنة في نظرية البيان في هذه الدراسة. حيث أن معظم العمل الذي تمت مناقشته في موضوع الهيمنة يركز أكثر على تهيئة الظروف للمجموعة المهيمنة للتوصل إلى مفهوم جديد للهيمنة. في هذه الأطروحة، تم تقديم المعاملين الجديدين للهيمنة في نظرية البيان وهما هيمنة المجموع الزوجي والهيمنة العكسية ذات المجموع الزوجي. وكذلك مفهوم هيمنة الأضلاع ذات المجموع الزوجي، وتمت دراسة ومناقشة العديد من خصائص هذه المفاهيم ووضع النظريات لها بشكل خاص على الرسوم البيانية المحددة كالدورة، المسار، الكامل، ثنائي الكامل، النجم، الفارغ، والعجلة والشوكة. علاوة على ذلك، تمت كتابة خوارزمية الوقت الخطي لمشكلة الهيمنة ES في العجلة والمسار وتم إثبات أن مسألة الهيمنة ES هي مسألة NP تامة. بالإضافة إلى ذلك، عملية الإكليل للرسم البيان الدائري وواحد من الرسوم البيانية المعينة مثل رسم البيان للعجلة والمسار والدورة والكامل والنجمة والثنائي الجزء الكامل والرسم الفارغ لهيمنة المجموع الزوجي. أيضًا، لكل حالة هناك بعض الأرقام التي تم تقديمها لتوضيح هذه الحالات. كما تمت دراسة الرسوم البيانية الضبابية وتطبيق المفاهيم الجديدة عليها كتعريف مجموعة المهيمنة ذات المجموع الزوجي الضبابية وكتابة بعض الخوارزميات لها.
Abstract
Various applications of domination and recent work on different forms of domination in graphs have given rise to our interest in exploring in this study new special types of graph domination. As most of the work discussed in domination focuses more on setting the conditions for the dominant group to come up with a new concept of domination. In this thesis, the two new parameter of domination in graph that called even sum domination (ESDS) and inverse even sum domination are introduced, and another new parameter which is edge even sum dominating set (ESEDS) Many of properties of these numbers are been discussed especially on the certain graphs as cycle, path, complete, complete bipartite, star, null, and wheel. Moreover, a linear-time algorithm for the ESDS and ESEDS domination problems in wheels is written and the NP-complete of ES domination problem is proved. In addition, the corona operation of a cycle graph and one of the certain graphs such as wheel, path, cycle, complete, star, complete bipartite, and null graph for even sum domination. Also, for each case there are some figures are been introduced to illustrated these cases. Moreover, the fuzzy even sum domination in strong graph is defended and studied for some certain graphs.
طلب نسخة من الملف
الملفات غير منشورة على الموقع. اترك بياناتك وسيتواصل معك موظفو قسم الشؤون الثقافية والفنون لإرسال النسخة مجاناً.