الرسم البياني العنقودي

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
رسم بياني عنقودي يحتوي على عناقيد (رسوم بيانية فرعية كاملة) بأحجام 1، 2، 3، 4، 4، 5، و6

في نظرية المخططات ، وهي فرع من الرياضيات ، يُعرف المخطط العنقودي بأنه مخطط يتكون من اتحاد منفصل لمخططات كاملة . وبصورة مكافئة، يكون المخطط مخططًا عنقوديًا إذا وفقط إذا لم يكن به مسار مستحث بثلاثة رؤوس ؛ ولهذا السبب، تُسمى المخططات العنقودية أيضًا بالمخططات الخالية من P3 . وهي المخططات المكملة للمخططات متعددة الأجزاء الكاملة [ 1 ] وقوى الأوراق الثنائية [ 2 ] . المخططات العنقودية مغلقة متعدية ، وكل مخطط غير موجه مغلق متعدي هو مخطط عنقودي [ 3 ] .

الرسوم البيانية العنقودية هي الرسوم البيانية التي تكون فيها علاقة التجاور علاقة تكافؤ ، ومكوناتها المتصلة هي فئات التكافؤ لهذه العلاقة.

كل رسم بياني عنقودي هو رسم بياني كتلي ، ورسم بياني مُكمِّل ، ورسم بياني خالٍ من المخالب . [ 1 ] تختار كل مجموعة مستقلة قصوى في الرسم البياني العنقودي رأسًا واحدًا من كل عنقود، لذا فإن حجم هذه المجموعة يساوي دائمًا عدد العناقيد؛ ولأن جميع المجموعات المستقلة القصوى لها نفس الحجم، فإن الرسوم البيانية العنقودية مُغطاة جيدًا . تُعد رسوم توران البيانية رسومًا بيانية مُكمِّلة للرسوم البيانية العنقودية، حيث تكون جميع الرسوم البيانية الفرعية الكاملة متساوية أو شبه متساوية في الحجم. الرسوم البيانية العنقودية المحلية (الرسوم البيانية التي يكون فيها كل جوار رسمًا بيانيًا عنقوديًا) هي الرسوم البيانية الخالية من المعين ، وهي عائلة أخرى من الرسوم البيانية التي تحتوي على الرسوم البيانية العنقودية.

عندما يتشكل مخطط عنقودي من مجموعات فرعية متساوية الحجم، يكون المخطط الكلي مخططًا متجانسًا ، أي أن كل تماثل بين اثنين من مخططاته الفرعية المستحثة يمكن تمديده إلى تماثل ذاتي للمخطط بأكمله. باستثناء حالتين فقط، تُعد المخططات العنقودية ومكملاتها المخططات المتجانسة المحدودة الوحيدة، [ 4 ] كما تُشكل المخططات العنقودية اللانهائية أحد أنواع المخططات المتجانسة اللانهائية القابلة للعد، وهي قليلة العدد . [ 5 ]

المشاكل الحسابية

التلوين الفرعي للرسم البياني هو تقسيم رؤوسه إلى رسوم بيانية عنقودية مستحثة . وبالتالي، فإن الرسوم البيانية العنقودية هي بالضبط الرسوم البيانية ذات العدد الفرعي اللوني  1. [ 6 ]

تُسمى المسألة الحسابية المتمثلة في إيجاد مجموعة صغيرة من الحواف لإضافتها أو إزالتها من رسم بياني لتحويله إلى رسم بياني عنقودي بتحرير العناقيد . وهي مسألة NP-كاملة [ 7 ] ولكنها قابلة للحل باستخدام معلمات ثابتة . [ 8 ]

بالنظر إلى رسم بياني كامل ذي تكاليف حواف (موجبة وسالبة)، فإن مسألة تقسيم الزمر تطلب إيجاد رسم بياني فرعي يمثل رسمًا بيانيًا عنقوديًا بحيث يكون مجموع تكاليف حواف الرسم البياني العنقودي في حده الأدنى. [ 9 ] ترتبط هذه المسألة ارتباطًا وثيقًا بمسألة التجميع الارتباطي .

مراجع

  1. 1 2 الرسوم البيانية العنقودية ، نظام المعلومات حول فئات الرسوم البيانية ومحتوياتها، تم الوصول إليه في 2016-06-26.
  2. ↑ نيشيمورا، ن.؛ راغدي، ب.؛ ثيليكوس، د.م. (2002)، "حول قوى الرسم البياني للأشجار المصنفة حسب الأوراق"، مجلة الخوارزميات ، 42 : 69-108 ، doi : 10.1006/jagm.2001.1195.
  3. ↑ ماكول، دبليو إف؛ نوشيتا، ك. (1986)، "حول عدد الحواف في الإغلاق المتعدي للرسم البياني"، الرياضيات التطبيقية المنفصلة ، ​​15 (1): 67-73 ، doi : 10.1016/0166-218X(86)90020-X ، MR 0856101 
  4. ↑ غاردينر، أ. (1976)، "الرسوم البيانية المتجانسة"، مجلة نظرية التوافيق ، السلسلة ب، 20 (1): 94-102 ، doi : 10.1016/0095-8956(76)90072-1 ، MR 0419293 .
  5. ↑ لاكلان، أ.هـ؛ وودرو، روبرت إي. (1980)، "الرسوم البيانية غير الموجهة فائقة التجانس القابلة للعد"، معاملات الجمعية الرياضية الأمريكية ، 262 (1): 51-94 ، doi : 10.2307/1999974 ، JSTOR 1999974 ، MR 0583847  .
  6. ↑ ألبرتسون، م.و.؛ جاميسون، ر.إ.؛ هيديتنييمي، س.ت.؛ لوك، س.س. (1989)، "العدد شبه اللوني للرسم البياني"، الرياضيات المتقطعة ، 74 ( 1-2 ): 33-49 ، doi : 10.1016/0012-365X(89)90196-9.
  7. ↑ شامير، رون؛ شاران، روديد؛ تسور، ديكل (2004)، "مسائل تعديل الرسم البياني العنقودي"، الرياضيات التطبيقية المنفصلة ، ​​144 ( 1-2 ): 173-182 ، doi : 10.1016/j.dam.2004.01.007 ، MR 2095392 .
  8. ↑ بوكر، سيباستيان؛ باومباخ، يان (2013)، "تحرير المجموعات"، طبيعة الحوسبة ، سلسلة محاضرات في علوم الحاسوب، المجلد 7921، سبرينغر، هايدلبرغ، الصفحات 33-44 ، doi : 10.1007/978-3-642-39053-1_5 ، ISBN   978-3-642-39052-4MR 3102002​ .
  9. ↑ غروتشل، مارتن ؛ واكاباياشي، يوشيكو (1989)، خوارزمية القطع المستوي لمسألة التجميع ، البرمجة الرياضية، المجلد 45، سبرينغر، الصفحات 59-96 ، doi : 10.1007/BF01589097  .