التبديل القابل للفصل

هيكلة كتلية لمصفوفة التبديل (المُنقلة) للتبديل القابل للفصل (4، 5، 2، 1، 3، 8، 6، 7) والشجرة الثنائية المُصنفة المُقابلة؛ تشير الألوان إلى العمق في الشجرة

في الرياضيات التوافقية ، التبديل القابل للفصل هو تبديل يمكن الحصول عليه من التبديل التافه 1 عن طريق الجمع المباشر والجمع المائل . ^{[ 1 ]} يمكن تمييز التبديلات القابلة للفصل بأنماط التبديل المحظورة 2413 و3142؛ ^{[ 2 ]} وهي أيضًا التبديلات التي تكون رسومها البيانية رسومًا بيانية مكملة ، والتبديلات التي تحقق الترتيبات الجزئية المتسلسلة المتوازية . من الممكن اختبار ما إذا كان تبديل قابل للفصل معين يمثل نمطًا في تبديل أكبر، أو إيجاد أطول نمط فرعي مشترك بين تبديلين قابلين للفصل، وذلك في وقت متعدد الحدود .

عرّف بوز، بوس، ولوبيو (1998) التبديل القابل للفصل بأنه تبديل له شجرة فاصلة : شجرة ثنائية جذرية تظهر فيها عناصر التبديل (بترتيب التبديل) عند أوراق الشجرة، وتشكل فيها فروع كل عقدة من الشجرة مجموعة فرعية متصلة من هذه العناصر. كل عقدة داخلية في الشجرة إما عقدة موجبة حيث تكون جميع فروع الابن الأيسر أصغر من جميع فروع الابن الأيمن، أو عقدة سالبة حيث تكون جميع فروع الابن الأيسر أكبر من جميع فروع الابن الأيمن. قد توجد أكثر من شجرة واحدة لتبديل معين: إذا كانت لعقدتين متجاورتين في الشجرة نفسها الإشارة نفسها، فيمكن استبدالهما بزوج مختلف من العقد باستخدام عملية تدوير الشجرة .

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

كما أثبت بوز، بوس ولوبيو (1998) ، يمكن أيضًا وصف التبديلات القابلة للفصل من حيث أنماط التبديل : يكون التبديل قابلاً للفصل إذا وفقط إذا لم يحتوي على النمط 2413 أو 3142. ^{[ 2 ]}

تتميز التبديلات القابلة للفصل أيضاً بخاصية من الهندسة الجبرية : إذا كانت مجموعة من كثيرات الحدود الحقيقية المختلفة لها جميعها قيم متساوية عند عدد ما x ، فإن التبديل الذي يصف كيفية تغير الترتيب العددي لكثيرات الحدود عند x يكون قابلاً للفصل، ويمكن تحقيق كل تبديل قابل للفصل بهذه الطريقة. ^{[ 3 ]}

تُحسب التباديل القابلة للفصل باستخدام أعداد شرودر . أي أن هناك تبديلاً قابلاً للفصل بطول واحد، وتباديل بطول اثنين، وبشكل عام، يكون عدد التباديل القابلة للفصل ذات طول معين (بدءًا من الطول واحد) هو

1، 2، 6، 22، 90، 394، 1806، 8558، .... (التسلسل A006318 في OEIS )

تم إثبات هذه النتيجة لفئة من مصفوفات التبديل المكافئة للتبديلات القابلة للفصل بواسطة شابيرو وستيفنز (1991) ، وذلك باستخدام شكل معياري لشجرة الفصل حيث يكون للابن الأيمن لكل عقدة إشارة مختلفة عن إشارة العقدة نفسها، ثم تطبيق نظرية الدوال المولدة على هذه الأشجار. وقدّم ويست (1995) برهانًا آخر ينطبق بشكل مباشر على التبديلات القابلة للفصل نفسها . ^{[ 4 ]}

أظهر Bose و Buss و Lubiw (1998) أنه من الممكن تحديد ما إذا كان التبديل القابل للفصل المعطى يمثل نمطًا في تبديل أكبر في وقت متعدد الحدود ، على عكس نفس المشكلة بالنسبة للتبديلات غير القابلة للفصل، والتي تعتبر NP-كاملة .

يمكن حل مشكلة إيجاد أطول نمط قابل للفصل مشترك بين مجموعة من تباديل الإدخال في وقت متعدد الحدود لعدد ثابت من تباديل الإدخال، ولكنها تصبح مشكلة صعبة من نوع NP عندما يكون عدد تباديل الإدخال متغيرًا، وتبقى كذلك حتى عندما تكون جميع المدخلات قابلة للفصل. ^{[ 5 ]}

ظهرت التباديل القابلة للفصل لأول مرة في عمل Avis & Newborn (1981) ، الذين أظهروا أنها بالضبط التباديل التي يمكن فرزها بواسطة عدد عشوائي من مجموعات الإزالة المتسلسلة، حيث أن مجموعة الإزالة هي شكل مقيد من المكدس حيث تقوم أي عملية إزالة بإزالة جميع العناصر دفعة واحدة.

أعاد شابيرو وستيفنز (1991) دراسة التباديل القابلة للفصل في بحثهما حول ترشيح بوتستراب ، وهي عملية يتم فيها تعديل مصفوفة التبديل الأولية عن طريق تغيير أي معامل من معاملات المصفوفة، الذي له جاران متعامدان أو أكثر يساويان واحدًا، إلى واحد بشكل متكرر. وكما أوضحا، فإن فئة التباديل التي يتم تحويلها بهذه العملية إلى مصفوفة جميع عناصرها تساوي واحدًا هي بالضبط فئة التباديل القابلة للفصل.

تم تقديم مصطلح "التبديل القابل للفصل" لاحقًا بواسطة Bose و Buss و Lubiw (1998) ، الذين درسوا خصائصها الخوارزمية.

يمكن استخدام كل تبديل لتعريف رسم بياني للتبديل ، وهو رسم بياني رؤوسه هي عناصر التبديل وحوافه هي معكوسات التبديل. في حالة التبديل القابل للفصل، يمكن استنتاج بنية هذا الرسم البياني من شجرة الفصل الخاصة بالتبديل: يكون رأسان في الرسم البياني متجاورين إذا وفقط إذا كان سلفهما المشترك الأدنى في شجرة الفصل سالبًا. تُسمى الرسوم البيانية التي يمكن تكوينها من الأشجار بهذه الطريقة بالرسوم البيانية التكميلية (اختصارًا للرسوم البيانية القابلة للاختزال التكميلي)، وتُسمى الأشجار التي تُشكل منها بالأشجار التكميلية. بالتالي، فإن التبديلات القابلة للفصل هي تحديدًا التبديلات التي تكون رسومها البيانية التكميلية رسومًا بيانية تكميلية. ^{[ 6 ]} يتوافق توصيف الرسوم البيانية التكميلية بأنها رسوم بيانية ممنوعة (وهي الرسوم البيانية التي لا تحتوي على مسار مُستحث بأربعة رؤوس ) مع نمطي العناصر الأربعة الممنوعين في التبديلات القابلة للفصل.

ترتبط التباديل القابلة للفصل ارتباطًا وثيقًا بالترتيبات الجزئية المتسلسلة المتوازية ، وهي مجموعات مرتبة جزئيًا تكون رسومها البيانية للمقارنة هي الرسوم البيانية التكميلية. وكما هو الحال مع الرسوم البيانية التكميلية والتباديل القابلة للفصل، يمكن أيضًا تمييز الترتيبات الجزئية المتسلسلة المتوازية بترتيبات فرعية ممنوعة مكونة من أربعة عناصر. يُعرّف كل تبديل ترتيبًا جزئيًا بُعده الترتيبي اثنان، حيث تكون العناصر المراد ترتيبها هي عناصر التبديل، ويكون x  ≤ y عندما تكون قيمة x العددية أصغر من y وتقع على يسارها في التبديل. والتباديل التي يكون فيها هذا الترتيب الجزئي متسلسلًا متوازيًا هي تحديدًا التباديل القابلة للفصل. 

يمكن أيضًا استخدام التباديل القابلة للفصل لوصف التقسيمات الهرمية للمستطيلات إلى مستطيلات أصغر (ما يسمى "مخططات تقسيم الأرضيات"، المستخدمة على سبيل المثال في تصميم الدوائر المتكاملة ) باستخدام الإشارات الموجبة والسالبة لشجرة الفصل لوصف الشرائح الأفقية والرأسية للمستطيل إلى مستطيلات أصغر. ^{[ 7 ]}

تشمل التباديل القابلة للفصل كحالة خاصة التباديل القابلة للفرز على المكدس ، والتي تتجنب النمط 231.

• أكرمان، إيال؛ باريكيت، جيل؛ بينتر، رون واي. (2006)، "التقابل بين التباديل والمخططات الأرضية، وتطبيقاته"، الرياضيات التطبيقية المنفصلة ، ​​154 (12): 1674-1684 ، doi : 10.1016/j.dam.2006.03.018 ، MR 2233287 
• أفيس، ديفيد ؛ نيوبورن، مونرو (1981)، "حول مجموعات النبضات المتسلسلة"، Utilitas Mathematica ، 19 : 129-140 ، MR 0624050 .
• بوفيل، ماتيلد؛ روسين، دومينيك؛ فياليت، ستيفان (2007)، "أطول نمط قابل للفصل بين التباديل"، مطابقة الأنماط التوافقية (CPM 2007) ، سلسلة محاضرات في علوم الحاسوب، المجلد  4580، سبرينغر، الصفحات 316-327 ، doi : 10.1007/978-3-540-73437-6_32 ، ISBN  978-3-540-73436-9.
• بوز، بروسنجيت ؛ بوس، جوناثان؛ لوبيو، آنا (1998)، "مطابقة الأنماط للتباديل"، رسائل معالجة المعلومات ، 65 (5): 277-283 ، doi : 10.1016/S0020-0190(97)00209-3 ، MR 1620935 .
• غيس ، إتيان (2017)، متنزه رياضي فريد ، ليون: ENS Éditions، arXiv : 1612.06373 ، ISBN 978-2-84788-939-0MR 3702027​ 
• كيتايف، سيرجي (2011)، "2.2.5 التباديل القابلة للفصل"، أنماط في التباديل والكلمات ، دراسات في علوم الحاسوب النظرية. سلسلة EATCS، برلين: سبرينغر-فيرلاغ ، ص 57-66 ، doi : 10.1007/978-3-642-17333-2 ، ISBN  978-3-642-17332-5Zbl 1257.68007​ .
• شابيرو، لويس؛ ستيفنز، آرثر ب. (1991)، "الترشيح التمهيدي، وأعداد شرودر، ومسألة الملوك - ن "، مجلة SIAM للرياضيات المتقطعة ، 4 (2): 275-280 ، doi : 10.1137/0404025 ، MR 1093199 .
• Szepieniec, AA; Otten, RHJM (1980)، "النهج الجينيالوجي لمشكلة التخطيط"، المؤتمر السابع عشر حول أتمتة التصميم (DAC 1980) ، الصفحات 535-542 ، doi : 10.1145/800139.804582 ، ISBN  0-89791-020-6، S2CID 2031785 .
• ويست، جوليان (1995)، "توليد الأشجار وأعداد كاتالان وشرودر"، الرياضيات المتقطعة ، 146 ( 1-3 ): 247-262 ، doi : 10.1016/0012-365X(94)00067-1 ، MR 1360119 .