رسم بياني قوي الوتر

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

تتميز الرسوم البيانية الوترية القوية بوجود رسم بياني فرعي ممنوع، وهي الرسوم البيانية التي لا تحتوي على دورة مستحثة يزيد طولها عن ثلاثة، أو _على رسم بياني فرعي مستحث من الرتبة n ( _حيث n  ≥  3) . ^{[ 2 ]} الرسم البياني من الرتبة n هو رسم بياني وتري مكون من 2n _رأسًا ، مقسم إلى مجموعتين فرعيتين U = { u1 , u2 _, ...} و W = { w1 , w2 _, ...}، بحيث يكون لكل رأس w1 في W جارين فقط، u1 و u _{( i + 1) mod n} . لا _{يمكن أن يكون الرسم البياني من} الرتبة n وتريًا قويًا، لأن الدورة u1 _w1 u2 w2 ... ليس لها وتر فردي _.          

يمكن أيضًا وصف الرسوم البيانية الوترية القوية بأنها رسوم بيانية ذات ترتيب حذف مثالي قوي، وهو ترتيب للرؤوس بحيث تشكل جيران أي رأس يأتي لاحقًا في الترتيب زمرة، وبحيث أنه لكل i  < j < k < l ، إذا كان الرأس i في الترتيب مجاورًا للرأسين k و l ، وكان الرأسان j و k متجاورين، فإن الرأسين j و l يجب أن يكونا متجاورين أيضًا. ^{[ 3 ]}     

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

يكون الرسم البياني وتريًا بقوة إذا وفقط إذا كان كل رسم بياني فرعي مستحث منه رسمًا بيانيًا وتريًا مزدوجًا . ^{[ 6 ]}

يمكن أيضًا وصف الرسوم البيانية الوترية القوية من حيث عدد الرسوم البيانية الفرعية الكاملة التي يشارك فيها كل ضلع. ^{[ 7 ]} وهناك وصف آخر مذكور في ^{[ 8 ] .}

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

توجد الآن خوارزميات بديلة معروفة يمكنها تحديد ما إذا كان الرسم البياني وتريًا بقوة، وإذا كان كذلك، فإنها تُنشئ ترتيب حذف مثالي قوي بكفاءة أكبر، في وقت O(min( n ² , ( n + m ) log n )) للرسم البياني الذي يحتوي على n رأسًا و m حافة. ^{​​[ 10 ]}

تُعدّ فئة القوى ذات الأوراق من الرتبة k فئة فرعية مهمة (مبنية على علم الوراثة ) ، وهي الرسوم البيانية المُشكّلة من أوراق الشجرة بربط ورقتين بحافة عندما تكون المسافة بينهما في الشجرة على الأكثر k . وتُعرّف القوة الورقية بأنها رسم بياني يُمثّل قوة من الرتبة k لبعض قيم k . وبما أن قوى الرسوم البيانية الوترية القوية هي قوى وترية قوية، والأشجار وترية قوية، فإن القوى الورقية تُشكّل بدورها فئة فرعية مناسبة من الرسوم البيانية الوترية القوية، والتي تشمل بدورها الرسوم البيانية العنقودية كقوى ذات ورقتين. ^{[ 11 ]} وتُعدّ الرسوم البيانية الفاصلية فئة فرعية مهمة أخرى من الرسوم البيانية الوترية القوية . وقد بيّن ^{[ 12 ]} أن الرسوم البيانية الفاصلية والفئة الأكبر من الرسوم البيانية ذات المسارات الموجهة الجذرية هي قوى ورقية.

بما أن الرسوم البيانية الوترية القوية هي رسوم بيانية وترية ورسوم بيانية وترية مزدوجة في آنٍ واحد ، فإنه يمكن حل العديد من مسائل NP-complete بكفاءة عالية، مثل مسائل المجموعة المستقلة، والزمرة، والتلوين، وتغطية الزمرة ، والمجموعة المهيمنة ، وشجرة شتاينر. وتُعدّ مسألة تماثل الرسوم البيانية مسألة تماثل كاملة للرسوم البيانية الوترية القوية. ^{[ 13 ]} كما تبقى مسألة الدائرة الهاميلتونية مسألة NP-complete للرسوم البيانية الوترية القوية المنقسمة . ^{[ 14 ]}

• براندشتات، أندرياس ؛ دراغان، فيودور؛ تشيبوي، فيكتور؛ فولوشين، فيتالي (1998)، "الرسوم البيانية الوترية المزدوجة"، مجلة SIAM للرياضيات المتقطعة ، 11 (3): 437-455 ، doi : 10.1137/s0895480193253415.
• براندشتات، أندرياس ؛ هوندت، كريستيان؛ مانشيني، فيديريكو؛ فاغنر، بيتر (2010)، "مخططات المسار الموجه الجذرية هي قوى الأوراق"، الرياضيات المتقطعة ، 310 (4): 897-910 ، doi : 10.1016/j.disc.2009.10.006.
• براندشتات، أندرياس ؛ لي، فان بانغ (2006)، "التعرف على بنية وقوى الأوراق الثلاثية في الزمن الخطي"، رسائل معالجة المعلومات ، 98 (4): 133-138 ، doi : 10.1016/j.ipl.2006.01.004.
• براندشتات، أندرياس ؛ لي، فان بانغ؛ سريثاران، ر. (2008)، "بنية وتعرف زمني خطي على قوى الأوراق الأربع"، معاملات ACM في الخوارزميات ، 5 11، doi : 10.1145/1435375.1435386 ، S2CID 6114466 .
• براندشتات، أندرياس ؛ لي، فان بانغ؛ سبينراد، جيريمي (1999)، فئات الرسوم البيانية: دراسة استقصائية ، سلسلة دراسات SIAM في الرياضيات المتقطعة وتطبيقاتها، ISBN 0-89871-432-X.
• تشانغ، جي جي (1982)،مسائل الهيمنة من النوع K وتغطية الرسوم البيانية ، أطروحة دكتوراه، جامعة كورنيل.
• دالهاوس، إي.؛ مانويل، بي. دي.؛ ميلر، إم. (1998)، "توصيف للرسوم البيانية الوترية القوية"، الرياضيات المتقطعة ، 187 ( 1-3 ): 269-271 ، doi : 10.1016/S0012-365X(97)00268-9.
• دي كاريا، ب.؛ ماكي، ت. أ. (2014)، "خصائص ماكسكليك وقرص الوحدة للرسوم البيانية الوترية القوية"، مناقشات الرياضيات في نظرية الرسوم البيانية ، 34 (3): 593-602 ، doi : 10.7151/dmgt.1757 ، hdl : 11336/32705.
• فاربر، م. (1983)، "خصائص الرسوم البيانية الوترية القوية"، الرياضيات المتقطعة ، 43 ( 2-3 ): 173-189 ، doi : 10.1016/0012-365X(83)90154-1.
• لوبيو، أ. (1987)، "الترتيبات المعجمية المزدوجة للمصفوفات"، مجلة SIAM للحوسبة ، 16 (5): 854-879 ، doi : 10.1137/0216057.
• ماكي، تي. أ. (1999)، "توصيف جديد للرسوم البيانية الوترية القوية"، الرياضيات المتقطعة ، 205 ( 1-3 ): 245-247 ، doi : 10.1016/S0012-365X(99)00107-7.
• مولر، هـ. (1996)، "دوائر هاميلتونية في الرسوم البيانية الثنائية الوترية"، الرياضيات المتقطعة ، 156 ( 1-3 ): 291-298 ، doi : 10.1016/0012-365x(95)00057-4.
• نيشيمورا، ن.؛ راغدي، ب.؛ ثيليكوس، د.م. (2002)، "حول قوى الرسم البياني للأشجار المصنفة حسب الأوراق"، مجلة الخوارزميات ، 42 : 69-108 ، doi : 10.1006/jagm.2001.1195.
• بايج، ر.؛ تارجان، ر. إي. (1987)، "ثلاث خوارزميات لتحسين التقسيم"، مجلة SIAM للحوسبة ، 16 (6): 973-989 ، doi : 10.1137/0216062 ، S2CID 33265037 .
• راوتنباخ، د. (2006)، "بعض الملاحظات حول جذور الأوراق"، الرياضيات المتقطعة ، 306 (13): 1456-1461 ، doi : 10.1016/j.disc.2006.03.030.
• سبينراد، ج. (1993)، "الترتيب المعجمي المزدوج للمصفوفات الكثيفة 0-1"، رسائل معالجة المعلومات ، 45 (2): 229-235 ، doi : 10.1016/0020-0190(93)90209-R.
• أوهارا، ر.؛ تودا، س.؛ ناغويا، ت. (2005)، "اكتمال تماثل الرسوم البيانية للرسوم البيانية الوترية الثنائية والوترية القوية"، الرياضيات التطبيقية المنفصلة ، ​​145 (3): 479-482 ، doi : 10.1016/j.dam.2004.06.008.