رسم بياني مختنق

في الرياضيات البيانية ، يُعرف الرسم البياني المختنق بأنه الرسم البياني الذي يؤدي حذف حواف أي دورة مستحثة يزيد طولها عن ثلاثة إلى فصل الرسم البياني المتبقي. أي أنها الرسوم البيانية التي تكون فيها كل دورة محيطية مثلثًا.

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

يُشكَّل مجموع الزمر لبيانين بتحديد زمرتين متساويتين في الحجم في كل بيان، ثم حذف بعض حواف الزمر إن أمكن. في حالة مجاميع الزمر المتعلقة بالبيانات المخنوقة، تُحذف خطوة حذف الحواف. ينتج عن مجموع الزمر من هذا النوع بين بيانين مخنوقين بيان مخنوق آخر، إذ يجب أن تقتصر كل دورة طويلة مستحثة في المجموع على جانب واحد (وإلا لكان لها وتر بين الرؤوس التي عبرت عندها من جانب المجموع إلى الآخر)، ويجب أن تبقى الأجزاء المنفصلة من ذلك الجانب، الناتجة عن حذف الدورة، منفصلة في مجموع الزمر. يمكن تحليل كل بيان وتري بهذه الطريقة إلى مجموع زمر لبيانات كاملة ، ويمكن تحليل كل بيان مستوٍ أقصى إلى مجموع زمر لبيانات مستوية قصوى متصلة بأربعة رؤوس .

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

• الرسم البياني المثالي الخطي ، وهو رسم بياني تكون فيه كل دورة فردية عبارة عن مثلث

• سيمور، بي دي ؛ ويفر، آر دبليو (1984)، "تعميم للرسوم البيانية الوترية"، مجلة نظرية الرسوم البيانية ، 8 (2): 241-251 ، doi : 10.1002/jgt.3190080206 ، MR 0742878 .