تقسيم الرسوم البيانية المتصلة بشكل كبير: صياغة دقيقة وطرق الحل

لقد كانت تقسيم الرسوم البيانية (GP) وترابط النقاط مجالين دراسيين مختلفين تقليديًا. تقدم هذه الورقة مشكلة تقسيم الرسم البياني المتصل بشكل كبير (HCGP)، التي تقسم الرسم البياني إلى أجزاء متراصة ومتوازنة الحجم وQ- (نقطة) متصلة لأي Q ≥ 1. هذه المشكلة ذات قيمة في التطبيقات التي تسعى إلى التماسك والقدرة على التحمل داخل أجزائها، مثل اكتشاف المجتمعات في الشبكات الاجتماعية وتقسيم شبكات الطاقة مع التركيز على المرونة. تتركز الأبحاث الحالية في هذا الترابط الأساسي بشكل أساسي على تقديم ضمانات وجود نظرية للتقسيمات المتصلة بشكل كبير لمجموعة محدودة من الرسوم البيانية الكثيفة، ولا تشمل اعتبارات GP الكanonical مثل توازن الحجم والمتانة. المساهمة الرئيسية لهذه الورقة هي تقديم نهج عام للنمذجة والخوارزمية لـ HCGP، مستوحى من الأعمال الأخيرة في مشكلة الاقتراع السياسي، وهي حالة خاصة من HCGP مع Q=1. هذا النهج يقوم بنمذجة قيود الـ Q-اتصال كبرامج مختلطة صحيحة لأي Q ≥ 1 ويوفر طريقة فرعية وقص للتعامل مع HCGP. عندما تكون سرعة الحل أولوية على الأمثلية، تقدم هذه الورقة طريقة heurística مصممة خصيصًا لـ HCGP مع Q=2. تقوم تحليل حسابي بتقييم هذه الأساليب باستخدام مجموعة من الأمثلة من رسوم بيانية مختلفة في العالم الحقيقي. في هذا التحليل، تجد طريقة الفرع والقطع حلًا أمثلًا في غضون ساعة في 82.8% من الأمثلة التي تم حلها. بالنسبة لـ Q=2، تكون الأمثلة الصغيرة والنادرة صعبة بالنسبة للنهج heurístico، بينما تكون الأمثلة الكبيرة والنادرة صعبة بالنسبة للطريقة الدقيقة. علاوة على ذلك، تقوم هذه الدراسة بتQuantify تكلفة الحوسبة لضمان اتصالات أعلى باستخدام نهج الفرع والقطع، بالمقارنة مع أساس ضمان 1-الاتصال. بشكل عام، تعتبر هذه العمل أداة فعالة لتقسيم الرسم البياني إلى أجزاء مرنة ومتجانسة.