اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدخوارزمية أمثلية لتحديد ثخانة البيان التام والثنائي التام
A optimization algorithm for determining the thickness of complete graphs and complete bipartite graphs
1655
1 17
0
(
0
)
نشر من قبل
جامعة البعث ورقة بحثية
تاريخ النشر
2014
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
العربية
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
نرمز نظرياً لثخانة البيان G ب( Φ(G وتعرف ثخانة البيان بأنها العدد الأصغري من البيانات الجزئية المسطحة(المستوية ) والتي نستطيع الحصول عليها من تحميل البيان الأصلي G والبيان المسطح هو كل بيان يمكن إعادة رسمه في المستوي بدون أن تتقاطع أضلاعه (خطوط التوصيّل بين الر ؤوس)، لذلك عرفت مسألة تحديد ثخانة البيان كمسألة تنتمي إلى صف المسائل .NP-complete سنقدم في هذا البحث تطبيقاً لخوارزمية تجريبية Heuristic Algorithm تعتمد على مفهوم محاكاة تلدين الفلزات الأمثلScheme Simulated Annealing Optimization New- hick الذي يساعد في تحسين نتائج الخوارزمية التجريبية المقترحة حيث أعطى حلاً فعالاً وسريعاً في إيجاد ثخانة البيانات التامة والثنائية التامة عندما يكون عدد رؤوس البيان n<=30 وأبطأ عندما يكون أكبر من ذلك. أخيرا نعرض نتائج تطبيق هذه الخوارزمية على الخوارزمية التجريبية فنلاحظ بأنها أعطت حلاً أمثلياً لتحديد ثخانة البيانات التامة والثنائية التامة. كما تمّت برمجة هذه الخوارزمية باستخدام لغة عالية المستوى ++C بمفهوم غرضي التوجه وقد حصلنا على النتائج بتنفيذ البرنامج على حاسوب بمواصفات RAM 2GB, CPU, M350 2.27GHZ
The graph-theoretical thickness (shortly thickness)of graph G, denoted by Φ(G), is the minimum number of planar subgraphs into which the graph can be decomposed, and a graph that can be drawn in the plane without any of its edges intersecting is called a planar graph. determining the thickness of a given graph is known to be an NP-complete problem. In this paper we introduce an application heuristic algorithm for determining the thickness. Our algorithm is based on simulated annealing optimization scheme which provide the results of the New-thick (1). We show that the simulated annealing is a efficient method to obtain good approximation for the thickness when the number vertices are at most 30 otherwise it is slower. Finally, we apply this algorithm on the heuristic algorithm Newthick and we show that the algorithm produces a good approximation and optimization solution for the thickness, and we program this algorithm with C++, and running it by laptop has RAM 2GB and CPU 2.27GHZ.
المراجع المستخدمة
BONDY, J and MURTY, U. S 2008-Graph Theory . Springer
artrand,G 1993-Applied and Algorithmic Graph Theory. McGraw-Hill,Inc, International Edition United States of America, 395
Daniel Liang,Y 2010-Introduction to Programming With C++. Pearson Education International, second edition United States of America, 694
Eles, P 2010- Simulated Annealing.Department of Computer and Information Science (IDA)Linköpings Universitet
JOHN,M. MICHAEL,J and JEFFRY,L 2008-Combinatorics and Graph Theory, second edition Springer, 392
قيم البحث
اقرأ أيضاً
الهدف من هذا البحث هو دراسة و تعميم بعض النتائج المتعلقة بالاستمرار التام لمؤثر أوريسون بمتحولين, و المعطى بمعادلة تكاملية على مجموعة قيوسة وفق قياس لوبيغ, من خلال دراسة التقارب المنتظم لمتتالية من مؤثرات أوريسون , المعطاة بالتوابع , و ذلك باستخدام ا
لتقارب بالقياس من خلال الإعتماد على شرط كاراثيودوري للمجموعات القيوسة.
على الرغم من التقدم الكبير في الجراحة، مازال اختيار الطريقة المناسبة لمعالجة هبوط المستقيم التام موضع جدل بالنظر لقلة حدوث الإصابة، الأمر الذي يعد سبباً لعدم وجود دراسات معشاة واسعة تؤكد تفوق طريقة على أخرى.
تسليط الضوء على عملية جراحية قلما ذكرت ف
ي الأدب الطبي، و هي عملية زودك (1922) Sudeck's operation و التعديلات التي أجريتها عليها، علماً أنها تجري عبر البطن و تمتاز بأّنها تتناول إصلاح أكثر من جانب مرضي لهبوط
المستقيم التام لدى البالغين و بنتائج مشجعة جداً.
كما هو معروف فإن مسألة تلوين بيان باستخدام أقل عدد من الألوان هي مسألة معقدة
(NP-Hard) المشكلة تتلخص في كيفية تلوين عقد بيان بأقل عدد ممكن من الألوان .
و بحيث لا يكون لأي عقدتين متجاورتين اللون نفسه، أو كيف يمكن تلوين أضلاع هذا
البيان بأقل عدد ممك
ن من الألون بحيث لا يكون لضلعين يشتركان بعقدة اللون نفسه.
نقدم في هذه الورقة البحثية خوارزمية تلوين جديدة لأضلاع بيان. هذه الخوارزمية تُمكننا
من الحصول على تلوين ضلعي مستمر لصف من البيانات الشهيرة.
نقدم في هذا البحث خوارزمية فعالة لإيجاد المسار الأقصر في بيان متعدد المنابع, و ذلك باختيار المسار بين المنبع و المسافة التي تعطي طول المسار الأقل وصولا إلى المصب. تعتمد هذه الخوارزمية على مبدأ التكرار للوصول إلى الحل الأمثل لمسألة المسار الأقصر, حيث
يتم تكرار خطوات الخوارزمية على جميع الأسهم في البيان. أثبتنا بأن زمن تنفيذ الخوارزمية المقترحة في هذا البحث هو زمن خطي قدره (O(n+L و هو يعتبر أفضل أزمنة الخوارزميات على الإطلاق.
مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار
الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
الأسئلة المقترحة
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
