المسار المستحث

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

وبالمثل، فإن الدورة المستحثة هي دورة تمثل رسمًا بيانيًا فرعيًا مستحثًا من G ؛ وتُسمى الدورات المستحثة أيضًا بالدورات عديمة الأوتار أو (عندما يكون طول الدورة أربعة أو أكثر) بالثقوب . أما الثقب المضاد فهو ثقب في متمم G ، أي أن الثقب المضاد هو متمم للثقب.

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

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

يمكن وصف العديد من عائلات الرسوم البيانية المهمة من حيث المسارات أو الدورات المستحثة للرسوم البيانية في العائلة.

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

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

كما أن تحديد ما إذا كان من الممكن تقسيم رؤوس الرسم البياني إلى مسارين مستحثين، أو دورتين مستحثتين، يُعد مسألة NP-كاملة. ^{[ 7 ]} ونتيجة لذلك، فإن تحديد عدد المسارات المستحثة في الرسم البياني يُعد مسألة NP-صعبة.

يمكن ربط تعقيد تقريب أطول مسار أو دورة مستحثة بتعقيد إيجاد مجموعات مستقلة كبيرة في الرسوم البيانية، وذلك من خلال الاختزال التالي. ^{[ 8 ]} من أي رسم بياني G ذي n رأسًا، نُنشئ رسمًا بيانيًا آخر H بضعف عدد رؤوس G ، وذلك بإضافة n ( n - 1)/2 رأسًا إلى G ، لكل منها جاران، جار واحد لكل زوج من الرؤوس في G. إذا كان G يحتوي على مجموعة مستقلة بحجم k ، فلا بد أن يحتوي H على مسار مستحث ودورة مستحثة بطول 2k ، تتكون من تناوب رؤوس المجموعة المستقلة في G مع رؤوس I. على العكس، إذا كان H يحتوي على مسار أو دورة مستحثة بطول k ، فإن أي مجموعة قصوى من الرؤوس غير المتجاورة في G من هذا المسار أو الدورة تُشكل مجموعة مستقلة في G بحجم k /3 على الأقل. وبالتالي، فإن حجم المجموعة المستقلة القصوى في G يقع ضمن عامل ثابت من حجم أطول مسار مستحث وأطول دورة مستحثة في H. لذلك، وبناءً على نتائج هاستاد (1996) حول عدم إمكانية تقريب المجموعات المستقلة، ما لم يكن NP=ZPP، فلا توجد خوارزمية زمنية متعددة الحدود لتقريب أطول مسار مستحث أو أطول دورة مستحثة ضمن عامل O( n½ ^-ε ) من الحل الأمثل.  

يمكن اكتشاف الثقوب (والثقوب المضادة في الرسوم البيانية التي لا تحتوي على دورات بدون أوتار بطول 5) في رسم بياني يحتوي على n رأسًا و m حافة في وقت (n+m ² ). ^{[ 9 ]}

تُعدّ الدورات الذرية تعميمًا للدورات الخالية من الأوتار، والتي لا تحتوي على أي أوتار من الرتبة n . في دورة ما، يُعرَّف الوتر من الرتبة n بأنه مسار طوله n يربط نقطتين على الدورة، حيث n أقل من طول أقصر مسار على الدورة يربط هاتين النقطتين. إذا لم تحتوي الدورة على أي أوتار من الرتبة n ، تُسمى دورة ذرية، لأنها لا يمكن تجزئتها إلى دورات أصغر. ^{[ 10 ]} في أسوأ الحالات، يمكن تعداد الدورات الذرية في الرسم البياني في زمن O( m² ⁾ ، حيث m هو عدد الحواف في الرسم البياني.