اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدخوارزمية تلوين ضلعي مستمر لصف من البيانات
An Algorithm for Continuously Edge Coloring a Set of Graphs
1660
0 45
0
(
0
)
تأليف
محمد فراس الحلبي( باحث )
تمت اﻹضافة من قبل
Shamra Editor
اسأل ChatGPT حول البحث
كما هو معروف فإن مسألة تلوين بيان باستخدام أقل عدد من الألوان هي مسألة معقدة (NP-Hard) المشكلة تتلخص في كيفية تلوين عقد بيان بأقل عدد ممكن من الألوان . و بحيث لا يكون لأي عقدتين متجاورتين اللون نفسه، أو كيف يمكن تلوين أضلاع هذا البيان بأقل عدد ممكن من الألون بحيث لا يكون لضلعين يشتركان بعقدة اللون نفسه. نقدم في هذه الورقة البحثية خوارزمية تلوين جديدة لأضلاع بيان. هذه الخوارزمية تُمكننا من الحصول على تلوين ضلعي مستمر لصف من البيانات الشهيرة.
As it’s known, The Graph k-Colorability Problem (GCP) is a wellknown NP-Hard Problem. This problem consists in finding the k minimum number of colors to paint the vertices of a graph in such a way that any two adjoined vertices, which are connected by an edge, have always different colors. In another words how can we color the edges of a graph in such a way that any two edges joined by a vertex have always different colors? In this paper we introduce a new effective algorithm for coloring the edges of the graph. Our proposed algorithm enables us to achieve a Continuously Edge Coloring (CEC) for a set of known graphs.
المراجع المستخدمة
BARENBOIM, L.; ELKIN, M., 2009 - Distributed (Δ+1)-coloring in linear (in Δ) time, Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, ISBN 978-1-60558-506-2
BEIGEL, R., 2005 - 3-coloring in time O(1.3289n), Journal of Algorithms, 54 (2): 168–204
BRÉLAZ, D., 1979 - New Methods to Color the Vertices of a Graph, Communications of the ACM, 22 (4): 251–256
قيم البحث
اقرأ أيضاً
نقدم في هذا البحث خوارزمية جديدة لحل بعض المشاكل التي تعاني منها
خوارزميات عنقدة البيانات كالK-Means. هذه الخوارزمية الجديدة قادرة على
عنقدة مجموعة من البيانات بشكل منفرد دون الحاجة لخوارزميات عنقدة أخرى.
نرمز نظرياً لثخانة البيان G ب( Φ(G وتعرف ثخانة البيان بأنها العدد الأصغري من البيانات الجزئية المسطحة(المستوية ) والتي نستطيع الحصول عليها من تحميل البيان الأصلي G والبيان المسطح هو كل بيان يمكن إعادة رسمه في المستوي بدون أن تتقاطع أضلاعه (خطوط التو
صيّل بين الر ؤوس)، لذلك عرفت مسألة تحديد ثخانة البيان كمسألة تنتمي إلى صف المسائل
.NP-complete
سنقدم في هذا البحث تطبيقاً لخوارزمية تجريبية Heuristic Algorithm تعتمد على مفهوم محاكاة تلدين الفلزات الأمثلScheme Simulated Annealing Optimization
New- hick الذي يساعد في تحسين نتائج الخوارزمية التجريبية المقترحة
حيث أعطى حلاً فعالاً وسريعاً في إيجاد ثخانة البيانات التامة والثنائية التامة
عندما يكون عدد رؤوس البيان n<=30 وأبطأ عندما يكون أكبر من ذلك.
أخيرا نعرض نتائج تطبيق هذه الخوارزمية على الخوارزمية التجريبية
فنلاحظ بأنها أعطت حلاً أمثلياً لتحديد ثخانة البيانات التامة والثنائية التامة. كما تمّت برمجة هذه الخوارزمية باستخدام لغة عالية المستوى ++C بمفهوم غرضي التوجه وقد حصلنا على النتائج بتنفيذ البرنامج على حاسوب بمواصفات RAM 2GB, CPU, M350 2.27GHZ
نقترح نسخ المتداول من تخصيص Dirichlet الكامن، يسمى Rollinglda. من خلال نهج متتابع، فإنه يتيح بناء سلسلة الزمن القائم على LDA من الموضوعات التي تتفق مع الدول السابقة لنماذج LDA. بعد النمذجة الأولي، يمكن حساب التحديثات بكفاءة، مما يسمح للرصد في الوقت ا
لفعلي والكشف عن الأحداث أو الاستراتيجات الهيكلية. لهذا الغرض، نقترح تدابير تشابه مناسبة للموضوعات وتوفير دليل محاكاة على التفوق على النهج الأخرى الشائعة الاستخدام. يتم توضيح كفاية الطريقة الناتجة من خلال تطبيق على مثال Corpus. على وجه الخصوص، نحسب التشابه المتمثل في توزيعات الموضوعات التي تم الحصول عليها بالتتابع على فترات زمنية متتالية. للحصول على مثال تمثيلي، تتكون من مقالات نيويورك تايمز من عام 1980 إلى 2020، نقوم بتحليل تأثير العديد من خيارات المعلمات ضبطها وندير طريقة Rollinglda على مجموعة البيانات الكاملة التي تبلغ حوالي 4 ملايين مادة لإظهار جدوائها.
يتم استرداد الشبكة من الفشل عبرَ آليات و خوارزميات مُختلفة تُطبَّق في مستويات شبكيّة
مختلفة و تدرجات زمنيّة معينة. لا تأخذ طرق استرداد الشبكة الضوئيّة المبنية على
GMPLS من الفشل أي اعتبار لتكامل الاتصال عِند إعداد المسار الاحتياطي, حيثُ
يُمكن أن
يؤدي ذلك إلى أذى أكبر مثل حصول الفشل في وصلة أو مسار يتركز فيه عدد
كبير من الاتصالات. كذلك فإنّ تركيز مثل تلك الحركة يؤدي إلى تأثير سلبي
بمصطلحات قابليّة الشبكة للنجاة.
مسألة المسار الأقصر لجميع العقد في البيان هي , بلا شك , واحدة من أكثر المسائل الأساسية في خوارزميات نظرية البيان . نقدم في هذا البحث خوارزمية بسيطة و فعالة من أجل مسألة المسارات الأقصر في بيان موجه ( أو غير موجه ) . في هذه المسألة نقوم بإيجاد المسار
الأقصر من عقدة منبع معطاة إلى جميع العقد الأخرى في هذا البيان و الذي يكون المسار الأقصر فيه هو المسار الذي يملك أقل كلفة ( أي مجموع أوزان الأضلاع ) . أثبتنا بأن تعقيد الخوارزمية المقترحة في هذا البحث يعتمد فقط على أضلاع البيان , و بينا بأن زمن تنفيذها هو زمن خطي قدره (O(m , و هذا يعتبر أفضل أزمنة الخوارزميات على الإطلاق . ثم أجرينا مقارنة بين تعقيد الخوارزمية المقترحة و تعقيد الخوارزمية المقترحة هو الأفضل .
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
