آلة حاسبة تلوين الرسم البياني — لوّن رسمًا بيانيًا بحيث لا تتطابق العقد المتجاورة
تُخصص آلتنا الحاسبة لتلوين الرسم البياني لونًا لكل رأس في الرسم البياني بحيث لا يشترك أي رأسين متصلين مباشرة في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة (تُرتب العقد تنازليًا حسب الدرجة)، مع إدخال رسمك البياني كقائمة حواف نصية بسيطة (مثل A-B, A-C, B-C).
إجابة سريعة
أدخل رسمك البياني كقائمة حواف لتلوين كل رأس فورًا بحيث لا تشترك عقدتان متصلتان في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة.
أدخل حوافًا بصيغة عقدةA-عقدةB، مثل A-B, A-C, B-C.
كيفية استخدام آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت
- 1
أدخل رسمك البياني كقائمة حواف مفصولة بفواصل، مثل A-B, A-C, B-C.
- 2
انقر على 'احسب' لتلوين كل رأس باستخدام خوارزمية Welsh-Powell.
- 3
راجع اللون المُخصص لكل عقدة والعدد الإجمالي للألوان المستخدمة.
لماذا تستخدم آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت؟
يُخصص تلوين الرسم البياني تسميات ('ألوان') للرؤوس بحيث لا تربط أي حافة رأسين من نفس اللون — وهو التجريد الكلاسيكي وراء مشاكل الجدولة (لا تتشارك امتحانان متعارضان نفس الفترة الزمنية) وتلوين الخرائط (لا تتشارك منطقتان متجاورتان نفس اللون). إيجاد العدد الأدنى الحقيقي من الألوان (العدد اللوني) هو مسألة NP-صعبة بشكل عام، لكن أسلوب Welsh-Powell — تلوين الرؤوس بترتيب تنازلي حسب الدرجة، واختيار أصغر لون متاح دائمًا — ينتج تلوينًا جيدًا وسريعًا يقترب بشكل مثبت من الأمثل للعديد من الرسوم البيانية العملية، وهو بالضبط ما تحسبه هذه الآلة الحاسبة.
الأسئلة الشائعة
أدوات ذات صلة
آلة حاسبة الشجرة الممتدة الصغرى — خوارزمية كروسكال عبر الإنترنت
أوجد الشجرة الممتدة الصغرى لرسم بياني موزون باستخدام خوارزمية كروسكال. آلة حاسبة مجانية بإدخال بسيط لقائمة الحواف واكتشاف الدورات عبر Union-Find.
مدقق تسلسل درجات الرسم البياني — نظرية Erdős–Gallai عبر الإنترنت
تحقق مما إذا كان تسلسل من الأرقام تسلسل درجات صالحًا (قابلًا للتحقيق كرسم بياني) باستخدام نظرية Erdős–Gallai. آلة حاسبة مجانية بتحقق خطوة بخطوة.
آلة حاسبة مصفوفة التجاور — ابنِ مصفوفة رسم بياني عبر الإنترنت
ابنِ واعرض مصفوفة تجاور رسم بياني من إدخال بسيط لقائمة الحواف، مع تسلسل الدرجات. آلة حاسبة مجانية، موزونة أو غير موزونة.
حلّال مشكلة الزواج المستقر — خوارزمية Gale-Shapley عبر الإنترنت
أوجد تطابقًا مستقرًا بين مجموعتين متساويتي الحجم من قوائم تفضيلاتهما باستخدام خوارزمية Gale-Shapley. آلة حاسبة مجانية، نتائج مستقرة مضمونة.