الرسم البياني الفرعي المستحث

في المجال الرياضي لنظرية الرسم البياني ، الرسم البياني الفرعي المستحث للرسم البياني هو رسم بياني آخر، يتكون من مجموعة فرعية من رؤوس الرسم البياني وجميع الحواف ، من الرسم البياني الأصلي، ويربط بين أزواج الرؤوس في تلك المجموعة الفرعية.

رسميًا، ليكن أي رسم بياني، وليكن أي مجموعة فرعية من رؤوس G . إذن يكون الرسم البياني الفرعي المستحث هو الرسم البياني الذي تكون مجموعة رؤوسه هي ومجموعة أضلاعه تتكون من جميع الأضلاع في التي لها كلتا النقطتين النهائيتين في . ^[1] أي لأي رأسين ، و متجاورتين في إذا وفقط إذا كانتا متجاورتين في . وينطبق نفس التعريف على الرسوم البيانية غير الموجهة ، والرسوم البيانية الموجهة ، وحتى الرسوم البيانية المتعددة . ${\displaystyle G=(V,E)}$${\displaystyle S\subseteq V}$${\displaystyle G[S]}$${\displaystyle S}$${\displaystyle E}$${\displaystyle S}$${\displaystyle u,v\in S}$${\displaystyle u}$${\displaystyle v}$${\displaystyle G[S]}$${\displaystyle G}$

يمكن أيضًا تسمية الرسم البياني الفرعي المستحث بالرسم البياني الفرعي المستحث في بواسطة ، أو (إذا جعل السياق اختيار لا لبس فيه) الرسم البياني الفرعي المستحث لـ . ${\displaystyle G[S]}$${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

تتضمن الأنواع المهمة من الرسوم البيانية الفرعية المستحثة ما يلي.

• المسارات المستحثة هي رسوم بيانية فرعية مستحثة وهي مسارات . أقصر مسار بين أي رأسين في رسم بياني غير مرجح هو دائمًا مسار مستحث، لأن أي حواف إضافية بين أزواج الرؤوس والتي يمكن أن تتسبب في عدم استحثاثه ستتسبب أيضًا في عدم كونه الأقصر. وعلى العكس من ذلك، في الرسوم البيانية الوراثية للمسافة ، فإن كل مسار مستحث هو أقصر مسار. ^[2]
• الدورات المستحثة هي رسوم بيانية فرعية مستحثة عبارة عن دورات . يتم تحديد محيط الرسم البياني بطول أقصر دورة له، والتي تكون دائمًا دورة مستحثة. وفقًا لنظرية الرسم البياني المثالي القوي ، تلعب الدورات المستحثة ومكملاتها دورًا حاسمًا في توصيف الرسوم البيانية المثالية . ^[3]
• المجموعات المستقلة والزمر هي رسوم بيانية فرعية مستحثة وهي عبارة عن رسوم بيانية كاملة أو رسوم بيانية بدون حواف على التوالي .
• المطابقات المستحثة هي رسوم بيانية فرعية مستحثة وهي مطابقات .
• الحيز المجاور للرأس هو الرسم البياني الفرعي المستحث لجميع الرؤوس المجاورة له.

مشكلة تماثل الرسم البياني الفرعي المستحث هي شكل من أشكال مشكلة تماثل الرسم البياني الفرعي حيث يكون الهدف هو اختبار ما إذا كان من الممكن العثور على رسم بياني واحد كرسم بياني فرعي مستحث لآخر. نظرًا لأنها تتضمن مشكلة الزمرة كحالة خاصة، فهي NP-كاملة . ^[4]