رسم بياني للتباديل

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

لو${\displaystyle \rho =(\sigma _{1},\sigma _{2},...,\sigma _{n})}$أي تبديل للأرقام من${\displaystyle 1}$ل${\displaystyle n}$ثم يمكن تعريف رسم بياني للتباديل من${\displaystyle \sigma }$حيث يوجد${\displaystyle n}$الرؤوس${\displaystyle v_{1},v_{2},...,v_{n}}$والتي يوجد فيها حافة${\displaystyle v_{i}v_{j}}$لأي مؤشرين${\displaystyle i<j}$والتي${\displaystyle j}$يطلع قبل${\displaystyle i}$في${\displaystyle \rho }$أي مؤشران${\displaystyle i}$و${\displaystyle j}$تحديد حافة في الرسم البياني للتباديل بالضبط عندما يحددون انعكاسًا في التبديل.

بافتراض وجود تبديل${\displaystyle \sigma }$ويمكن أيضاً تحديد مجموعة من القطع المستقيمة${\displaystyle s_{i}}$مع نقاط النهاية${\displaystyle (i,0)}$و${\displaystyle (k,1)}$بحيث${\displaystyle \sigma _{k}=i}$تقع نهايتا هذه القطع على الخطين المتوازيين${\displaystyle y=0}$و${\displaystyle y=1}$ويكون لقطعتين تقاطع غير فارغ إذا وفقط إذا كانتا تمثلان انعكاسًا في التبديل. وبالتالي، فإن الرسم البياني للتبديل هو${\displaystyle \sigma }$يتطابق مع الرسم البياني لتقاطع القطع المستقيمة. لكل خطين متوازيين، ولكل مجموعة منتهية من القطع المستقيمة التي تقع نهاياتها على كلا الخطين، يكون الرسم البياني لتقاطع القطع المستقيمة رسمًا بيانيًا للتباديل؛ في حالة كون نهايات القطع المستقيمة جميعها مختلفة، يمكن إيجاد تبديل يكون الرسم البياني للتباديل فيه عن طريق ترقيم القطع المستقيمة على أحد الخطين بالتسلسل، وقراءة هذه الأرقام بالترتيب الذي تظهر به نهايات القطع المستقيمة على الخط الآخر.

تتمتع مخططات التبديل بالعديد من الخصائص المكافئة الأخرى:

• رسم بياني${\displaystyle G}$يكون الرسم البياني عبارة عن رسم بياني للتباديل إذا وفقط إذا${\displaystyle G}$^{[ 2 ]} هو رسم بياني دائري يقبل خط استواء ، أي وتر إضافي يتقاطع مع كل وتر آخر.
• رسم بياني${\displaystyle G}$يكون الرسم البياني عبارة عن رسم بياني للتباديل إذا وفقط إذا كان كلاهما${\displaystyle G}$ومكملها​${\displaystyle {\overline {G}}}$هي رسوم بيانية للمقارنة . ^{[ 3 ]}
• رسم بياني${\displaystyle G}$يكون الرسم البياني عبارة عن رسم بياني للتباديل إذا وفقط إذا كان رسمًا بيانيًا للمقارنة لمجموعة مرتبة جزئيًا يكون بُعد ترتيبها اثنين على الأكثر. ^{[ 4 ]}
• إذا كان الرسم البياني${\displaystyle G}$هو رسم بياني للتباديل، وكذلك مكمله. التبديل الذي يمثل مكمل لـ${\displaystyle G}$يمكن الحصول عليها عن طريق عكس التبديل الذي يمثل${\displaystyle G}$.

من الممكن اختبار ما إذا كان الرسم البياني المعطى هو رسم بياني للتبديل، وإذا كان الأمر كذلك، فقم بإنشاء تبديل يمثله، في وقت خطي . ^{[ 5 ]}

باعتبارها فئة فرعية من الرسوم البيانية المثالية ، يمكن حل العديد من المشكلات التي تُصنف ضمن فئة NP-complete للرسوم البيانية العشوائية بكفاءة عالية بالنسبة للرسوم البيانية التبديلية. على سبيل المثال:

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

تُعد الرسوم البيانية للتباديل حالة خاصة من الرسوم البيانية الدائرية ، والرسوم البيانية للمقارنة ، ومكملات الرسوم البيانية للمقارنة، والرسوم البيانية شبه المنحرفة .

تشمل الفئات الفرعية لرسوم التبديل رسوم التبديل الثنائية (التي وصفها سبينراد، براندشتات وستيوارت 1987 ) والرسوم البيانية المشتركة .

• بيكر، كيربي أ.؛ فيشبورن، بيتر س .؛ روبرتس، فريد س. (1971)، "الترتيبات الجزئية ذات البعد 2"، الشبكات ، 2 (1): 11-28 ، doi : 10.1002/net.3230020103.
• بودليندر، هانز ل .؛ كلوكس، تون؛ كراتش، ديتر (1995)، "عرض الشجرة وعرض المسار لرسوم بيانية التبديل"، مجلة SIAM للرياضيات المتقطعة ، 8 (4): 606-616 ، doi : 10.1137/S089548019223992X ، hdl : 1874/16657.
• براندشتات، أندرياس ؛ لي، فان بانغ؛ سبينراد، جيريمي ب. (1999)، فئات الرسوم البيانية: دراسة استقصائية ، سلسلة دراسات SIAM في الرياضيات المتقطعة وتطبيقاتها، ISBN 0-89871-432-X.
• دوشنيك، بن؛ ميلر، إدوين دبليو. (1941)، "المجموعات المرتبة جزئيًا"، المجلة الأمريكية للرياضيات ، 63 (3): 600-610 ، doi : 10.2307/2371374 ، JSTOR 2371374 .
• جولومبيك، مارتن سي. (1980)، نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية ، علوم الحاسوب والرياضيات التطبيقية، دار النشر الأكاديمية، ص  159.
• ماكونيل، روس م.؛ سبينراد، جيريمي ب. (1999)، "التحليل المعياري والتوجيه المتعدي"، الرياضيات المتقطعة ، 201 ( 1-3 ): 189-241 ، doi : 10.1016/S0012-365X(98)00319-7 ، MR 1687819 .
• سبينراد، جيريمي ب.؛ براندشتات، أندرياس ؛ ستيوارت، لورنا ك. (1987)، "مخططات التبديل الثنائية"، الرياضيات التطبيقية المنفصلة ، ​​18 (3): 279-292 ، doi : 10.1016/s0166-218x(87)80003-3.

• "مخطط التبديل" ، نظام معلومات حول فئات المخططات ومحتوياتها
• وايسشتاين، إريك دبليو ، "مخطط التبديل" ، عالم الرياضيات