عرض الزمرة

في نظرية المخططات ، يُعدّ عرض الزمرة (clique-width) للمخطط G مُعاملًا يصف التعقيد البنيوي للمخطط؛ وهو يرتبط ارتباطًا وثيقًا بعرض الشجرة (treewidth) ، ولكنه على عكس عرض الشجرة، يمكن أن يكون صغيرًا في المخططات الكثيفة . ويُعرَّف بأنه الحد الأدنى لعدد التسميات اللازمة لإنشاء G باستخدام العمليات الأربع التالية  :

1. إنشاء رأس جديد v يحمل التسمية i (يرمز لها بـ i ( v ) )
2. الاتحاد المنفصل للرسمين البيانيين المسميين G و H (يرمز لهما بـ${\displaystyle G\oplus H}$)
3. يتم ربط كل رأس يحمل الرمز i بكل رأس يحمل الرمز j (ويرمز له بـ η ( i , j ) ) بواسطة حافة ، حيث i ≠ j
4. إعادة تسمية العلامة i إلى العلامة j (يرمز لها بـ ρ ( i , j ) )

تشمل الرسوم البيانية ذات عرض الزمرة المحدود الرسوم البيانية التكميلية والرسوم البيانية الوراثية للمسافة . على الرغم من أن حساب عرض الزمرة يُعدّ مسألةً صعبةً حسابيًا (NP-hard ) عندما يكون غير محدود، ومن غير المعروف ما إذا كان بالإمكان حسابه في وقت متعدد الحدود عندما يكون محدودًا، إلا أن هناك خوارزميات تقريبية فعّالة معروفة لعرض الزمرة. استنادًا إلى هذه الخوارزميات ونظرية كورسيل ، يمكن حلّ أو تقريب العديد من مسائل تحسين الرسوم البيانية الصعبة حسابيًا (NP-hard) لأي رسم بياني بسرعة على الرسوم البيانية ذات عرض الزمرة المحدود.

صاغ كورسيل وإنجلفريت وروزنبرغ في عام 1990 ^{[ 1 ]} ووانكي (1994) التسلسلات البنائية التي يقوم عليها مفهوم عرض الزمرة. واستخدمت تشليبيكوفا (1992) مصطلح "عرض الزمرة" لمفهوم مختلف . وبحلول عام 1993، كان المصطلح قد اكتسب معناه الحالي. ^{[ 2 ]}

الرسوم البيانية التكميلية هي تحديدًا الرسوم البيانية التي لا يتجاوز عرض زمرتها 2. ^{[ 3 ]} كل رسم بياني وراثي للمسافة له عرض زمرة لا يتجاوز 3. مع ذلك، فإن عرض زمرة الرسوم البيانية ذات الفترات الوحدوية غير محدود (استنادًا إلى بنيتها الشبكية). ^{[ 4 ]} وبالمثل، فإن عرض زمرة الرسوم البيانية للتباديل الثنائية غير محدود (استنادًا إلى بنية شبكية مماثلة). ^{[ 5 ]} استنادًا إلى توصيف الرسوم البيانية التكميلية بأنها الرسوم البيانية التي لا تحتوي على رسم بياني فرعي مستحث متماثل مع مسار ذي أربعة رؤوس، تم تصنيف عرض الزمرة للعديد من فئات الرسوم البيانية المعرفة بواسطة الرسوم البيانية الفرعية المستحثة المحظورة. ^{[ 6 ]}

تشمل الرسوم البيانية الأخرى ذات عرض الزمرة المحدود قوى الأوراق من الرتبة k لقيم k المحدودة ؛ وهي الرسوم البيانية الفرعية المستحثة لأوراق الشجرة T في الرسم البياني ذي القوة T ^k . ومع ذلك، فإن قوى الأوراق ذات الأسس غير المحدودة لا تمتلك عرض زمرة محدود. ^{[ 7 ]}

أثبت كل من كورسيل وأولاريو (2000) وكورنيل وروتيكس (2005) الحدود التالية لعرض الزمرة لبعض الرسوم البيانية:

• إذا كان عرض الزمرة في الرسم البياني لا يتجاوز k ، فإن كل رسم بياني فرعي مستحث من الرسم البياني له يكون كذلك. ^{[ 8 ]}
• الرسم البياني المكمل لرسم بياني ذي عرض زمرة k يكون عرض الزمرة فيه على الأكثر 2 k . ^{[ 9 ]}
• تتميز الرسوم البيانية ذات عرض الشجرة w بعرض زمرة لا يتجاوز 3 × 2w ^{- 1.} ويُعدّ الاعتماد الأسي في هذا الحد ضروريًا: إذ توجد رسوم بيانية يكون عرض زمرتها أكبر أُسّيًا من عرض شجرتها. ^{[ 10 ]} في المقابل، يمكن أن يكون للرسوم البيانية ذات عرض الزمرة المحدود عرض شجرة غير محدود؛ على سبيل المثال، ^الرسوم البيانية الكاملة ذات n رأسًا لها عرض زمرة يساوي 2 وعرض شجرة يساوي n - 1. ومع ذلك، فإن الرسوم البيانية ذات عرض الزمرة k التي لا تحتوي على رسم بياني ثنائي كامل K( _{t , t)} كرسم بياني فرعي ، يكون عرض شجرتها لا يتجاوز 3k ( t - 1) - 1. لذلك، بالنسبة لكل عائلة من الرسوم البيانية المتفرقة ، فإن امتلاك عرض شجرة محدود يُكافئ امتلاك عرض زمرة محدود. ^{[ 11 ]}
• معلمة أخرى للرسم البياني، وهي عرض الرتبة ، محدودة في كلا الاتجاهين بعرض الزمرة: عرض الرتبة ≤ عرض الزمرة ≤ 2 ^{عرض الرتبة +} 1. ^{[ 12 ]}

بالإضافة إلى ذلك، إذا كان للرسم البياني G عرض زمرة k ، فإن عرض زمرة قوة الرسم البياني G  c  لا يتجاوز 2kc  k . [ 13 ] على الرغم من وجود فجوة أسية في كل من حد عرض الزمرة من عرض الشجرة وحد عرض زمرة قوى الرسم البياني، فإن هذه الحدود لا تتراكم: إذا كان للرسم البياني G عرض شجرة w ، فإن عرض زمرة G c  لا يتجاوز 2( c + 1) w + 1 - 2 ، وهو أسّي واحد فقط في عرض الشجرة. [ 14 ]

يمكن حل العديد من مسائل التحسين التي تُصنف ضمن فئة NP-hard لأنواع أعم من الرسوم البيانية بكفاءة عالية باستخدام البرمجة الديناميكية على الرسوم البيانية ذات عرض الزمرة المحدود، وذلك عند معرفة تسلسل بناء هذه الرسوم البيانية. ^{[ 15 ] [ 16 ]} وعلى وجه الخصوص، فإن كل خاصية من خصائص الرسم البياني التي يمكن التعبير عنها في منطق الرتبة الثانية الأحادي MSO ₁ (وهو شكل من أشكال المنطق يسمح بالقياس الكمي على مجموعات الرؤوس) لها خوارزمية خطية للرسوم البيانية ذات عرض الزمرة المحدود، وذلك باستخدام شكل من أشكال نظرية كورسيل . ^{[ 16 ]}

من الممكن أيضًا إيجاد تلوينات مثالية للرسوم البيانية أو دورات هاميلتونية للرسوم البيانية ذات عرض الزمرة المحدود في وقت متعدد الحدود، عندما يكون تسلسل الإنشاء معروفًا، ولكن يزداد أس متعدد الحدود مع عرض الزمرة، وتشير الأدلة من نظرية التعقيد الحسابي إلى أن هذا الاعتماد من المرجح أن يكون ضروريًا. ^{[ 17 ]} الرسوم البيانية ذات عرض الزمرة المحدود هي رسوم بيانية محدودة من نوع χ ، مما يعني أن عددها اللوني هو على الأكثر دالة لحجم أكبر زمرة فيها. ^{[ 18 ]}

يمكن التعرف على الرسوم البيانية ذات عرض الزمرة 3، وإيجاد تسلسل إنشائي لها، في وقت متعدد الحدود باستخدام خوارزمية تعتمد على التفكيك المجزأ . ^{[ 19 ]} بالنسبة للرسوم البيانية ذات عرض الزمرة غير المحدود، يُعد حساب عرض الزمرة بدقة مسألة صعبة حسابيًا (NP-hard)، وكذلك الحصول على تقريب بخطأ إضافي دون الخطي. ^{[ 20 ]} مع ذلك، عندما يكون عرض الزمرة محدودًا، فمن الممكن الحصول على تسلسل إنشائي ذي عرض محدود (أكبر أُسّيًا من عرض الزمرة الفعلي) في وقت متعدد الحدود، ^{[ 21 ]} وخاصةً في وقت تربيعي بالنسبة لعدد الرؤوس. ^{[ 22 ]} يبقى السؤال مطروحًا حول إمكانية حساب عرض الزمرة الدقيق، أو تقريب أدق له، في وقت قابل للمعالجة بمعاملات ثابتة ، أو إمكانية حسابه في وقت متعدد الحدود لكل حد ثابت لعرض الزمرة، أو حتى إمكانية التعرف على الرسوم البيانية ذات عرض الزمرة أربعة في وقت متعدد الحدود. ^{[ 20 ]}

تشبه نظرية الرسوم البيانية ذات عرض الزمرة المحدود نظرية الرسوم البيانية ذات عرض الشجرة المحدود ، ولكنها، على عكس عرض الشجرة، تسمح بوجود رسوم بيانية كثيفة . إذا كانت مجموعة من الرسوم البيانية ذات عرض زمرة محدود، فإما أن يكون لها عرض شجرة محدود، أو أن كل رسم بياني ثنائي الأجزاء كامل هو رسم بياني فرعي من رسم بياني في تلك المجموعة. ^{[ 11 ]} يرتبط عرض الشجرة وعرض الزمرة أيضًا من خلال نظرية الرسوم البيانية الخطية : تتمتع مجموعة من الرسوم البيانية بعرض شجرة محدود إذا وفقط إذا كانت رسومها البيانية الخطية ذات عرض زمرة محدود. ^{[ 23 ]}

تتميز الرسوم البيانية ذات عرض الزمرة المحدود أيضًا بعرض التوأم المحدود . ^{[ 24 ]}