عرض المسار

الموسوعة الحرة

في نظرية المخططات ، يُعرف تجزئة المسار للمخطط G ، بشكل غير رسمي، بأنه تمثيل لـ G كمخطط مسار "مُكثّف" [ 1 ]. ويُقاس عرض المسار لـ G بعدد يُحدد مقدار تكثيف المسار لتكوين G. وبشكل أكثر دقة، فإن تجزئة المسار هي سلسلة من المجموعات الفرعية لرؤوس G بحيث تظهر نهايات كل حافة في إحدى هذه المجموعات الفرعية، ويظهر كل رأس في سلسلة فرعية متصلة من هذه المجموعات [ 2 ]. ويكون عرض المسار أقل بواحد من حجم أكبر مجموعة في هذه التجزئة. يُعرف عرض المسار أيضًا باسم سُمك الفاصل (أقل بواحد من أقصى حجم للزمرة في مخطط فاصل فائق لـ G ) ، أو عدد فصل الرؤوس ، أو عدد البحث عن العقد [ 3 ] . 

يُشابه عرض المسار وتفكيكاته عرض الشجرة وتفكيكاتها تشابهاً وثيقاً . ويلعبان دوراً محورياً في نظرية الرسوم البيانية الجزئية : إذ يمكن وصف عائلات الرسوم البيانية المغلقة تحت الرسوم البيانية الجزئية والتي لا تشمل جميع الغابات بأنها ذات عرض مسار محدود، [ 2 ] كما أن "الدوامات" التي تظهر في نظرية البنية العامة لعائلات الرسوم البيانية المغلقة جزئياً لها عرض مسار محدود. [ 4 ] ولعرض المسار، والرسوم البيانية ذات عرض المسار المحدود، تطبيقات أيضاً في تصميم الدوائر المتكاملة واسعة النطاق ، ورسم الرسوم البيانية ، واللغويات الحاسوبية .

يُعدّ إيجاد عرض المسار لأي رسم بياني، أو حتى تقريبه بدقة، مسألةً صعبةً من نوع NP . [ 5 ] [ 6 ] مع ذلك، يُمكن حلّ هذه المسألة باستخدام مُعامل ثابت : إذ يُمكن حلّ اختبار ما إذا كان عرض المسار k لرسم بياني في وقت يعتمد خطيًا على حجم الرسم البياني، ولكنه يعتمد بشكل أُسّي فائق على k . [ 7 ] إضافةً إلى ذلك، بالنسبة لعدة فئات خاصة من الرسوم البيانية، مثل الأشجار ، يُمكن حساب عرض المسار في وقت متعدد الحدود دون الاعتماد على k . [ 8 ] [ 9 ] يُمكن حلّ العديد من مسائل خوارزميات الرسوم البيانية بكفاءة على الرسوم البيانية ذات عرض المسار المحدود، باستخدام البرمجة الديناميكية على تجزئة المسار للرسم البياني. [ 10 ] كما يُمكن استخدام تجزئة المسار لقياس التعقيد المكاني لخوارزميات البرمجة الديناميكية على الرسوم البيانية ذات عرض الشجرة المحدود . [ 11 ]  

تعريف

مثال على الرسم البياني G بعرض مسار 2، وتفكيك مساره بعرض 2. الجزء السفلي من الصورة هو نفس الرسم البياني وتفكيك المسار مع إضافة اللون للتوضيح. (هذا المثال هو نسخة معدلة من الرسم البياني المعروض في بودليندر (1994أ) ، مع إضافة التوضيح).

في أول سلسلة أوراق بحثية شهيرة لهما حول صغار الرسوم البيانية ، قام نيل روبرتسون وبول سيمور ( 1983 ) بتعريف تجزئة المسار للرسم البياني G على أنها سلسلة من المجموعات الفرعية Xi من رؤوس G ، مع خاصيتين: 

  1. لكل حافة من حواف G ، يوجد i بحيث تنتمي كلتا نقطتي نهاية الحافة إلى المجموعة الجزئية X i ، و
  2. لكل ثلاثة مؤشرات i ≤ j ≤ k ،Xأنا∩Xك⊆Xج.{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}

الخاصية الثانية من هاتين الخاصيتين تُكافئ اشتراط أن تُشكّل المجموعات الجزئية التي تحتوي على أي رأس مُحدد سلسلة فرعية متصلة من السلسلة الكاملة. وبلغة الأوراق اللاحقة في سلسلة روبرتسون وسيمور عن المخططات الفرعية، فإن تفكيك المسار هو تفكيك شجري ( X , T ) تكون فيه الشجرة الأساسية T للتفكيك عبارة عن مخطط مسار .

يُعرَّف عرض تجزئة المسار بنفس طريقة تعريف تجزئة الشجرة، أي max i | X i | − 1 ، وعرض مسار الرسم البياني G هو الحد الأدنى لعرض أي تجزئة مسار له . إن طرح واحد من حجم X i في هذا التعريف لا يُحدث فرقًا يُذكر في معظم تطبيقات عرض المسار، ولكنه يُستخدم لجعل عرض مسار الرسم البياني مساويًا للواحد. 

توصيفات بديلة

كما يصف بودليندر (1998) ، يمكن وصف عرض المسار بعدة طرق متكافئة.

تسلسلات اللصق

يمكن وصف تجزئة المسار بأنها سلسلة من الرسوم البيانية Gi يتم ربطها معًا بتحديد أزواج من الرؤوس من الرسوم البيانية المتتالية في السلسلة، بحيث تكون نتيجة إجراء جميع عمليات الربط هذه هي G. يمكن اعتبار الرسوم البيانية Gi بمثابة الرسوم البيانية الفرعية المستحثة للمجموعات Xi في التعريف الأول لتجزئة المسار، حيث يتم ربط رأسين في الرسوم البيانية الفرعية المستحثة المتتالية معًا عندما يكونان مستحثين بواسطة نفس الرأس في G ، وفي الاتجاه الآخر، يمكن استعادة المجموعات Xi كمجموعات رؤوس الرسوم البيانية Gi . يكون عرض تجزئة المسار حينها أقل بواحد من الحد الأقصى لعدد الرؤوس في أحد الرسوم البيانية Gi . [ 2 ]

سمك الفاصل

رسم بياني فاصل زمني بعرض مسار اثنين، وهو أقل بواحد من عدد عناصر الزمر الأربع القصوى ABC و ACD و CDE و CDF .

عرض المسار لأي رسم بياني G يساوي أقل بواحد من أصغر عدد زمر في رسم بياني فاصل يحتوي على G كرسم بياني فرعي. [ 12 ] أي أنه لكل تجزئة مسار لـ G ، يمكن إيجاد رسم بياني فاصل فائق لـ G ، ولكل رسم بياني فاصل فائق لـ G، يمكن إيجاد تجزئة مسار لـ G ، بحيث يكون عرض التجزئة أقل بواحد من عدد الزمر في الرسم البياني الفاصل.

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

في الاتجاه الآخر، إذا كان G رسمًا بيانيًا فرعيًا من رسم بياني فاصلي ذي عدد زمر p + 1 ، فإن G يمتلك تجزئة مسار بعرض p، حيث تُحدد عُقدها بواسطة الزمر القصوى للرسم البياني الفاصلي. على سبيل المثال، يمتلك الرسم البياني الفاصلي الموضح بتمثيله الفاصل في الشكل تجزئة مسار بخمس عُقد، تُقابل زمره القصوى الخمس ABC و ACD و CDE و CDF و FG ؛ ويبلغ الحد الأقصى لحجم الزمرة ثلاثة، وعرض تجزئة المسار هذه اثنين.

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

عدد فصل الرؤوس

عدد فصل الرؤوس في الرسم البياني G بالنسبة لترتيب خطي لرؤوسه هو أصغر عدد s بحيث يكون لكل رأس v ، على الأكثر s رؤوس تسبق v في الترتيب ولكنها مجاورة لـ v أو رأس لاحق. عدد فصل الرؤوس في G هو أصغر عدد فصل رؤوس في G بالنسبة لأي ترتيب خطي له . وقد عرّف إليس وسودبورو وتيرنر (1983) عدد فصل الرؤوس ، وهو يساوي عرض المسار في G. [ 13 ] وينتج هذا من التكافؤ السابق مع أعداد الزمر في الرسم البياني الفاصل: إذا كان G رسمًا بيانيًا فرعيًا من رسم بياني فاصل I ، ممثلًا (كما في الشكل) بطريقة تجعل جميع نقاط نهاية الفترات متميزة، فإن ترتيب نقاط النهاية اليسرى لفترات I يكون له عدد فصل رؤوس أقل بواحد من عدد زمر I. وفي الاتجاه الآخر، من خلال الترتيب الخطي لـ G، يمكن للمرء أن يستنتج تمثيلًا فاصليًا تكون فيه نقطة النهاية اليسرى للفاصل الزمني للرأس v هي موضعه في الترتيب ونقطة النهاية اليمنى هي موضع جار v الذي يأتي أخيرًا في الترتيب.

رقم البحث عن العقدة

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

الحدود

شجرة اليرقة ، وهي رسم بياني أقصى بعرض مسار يساوي واحدًا.

كل رسم بياني ذي n رأسًا وعرض مسار k يحتوي على k ( n - k + ( k -1)/2) حافة على الأكثر، والرسوم البيانية ذات عرض المسار الأقصى k (الرسوم البيانية التي لا يمكن إضافة المزيد من الحواف إليها دون زيادة عرض المسار) تحتوي على هذا العدد من الحواف بالضبط. يجب أن يكون الرسم البياني ذو عرض المسار الأقصى k إما مسارًا k أو يرقة k ، وهما نوعان خاصان من أشجار k . شجرة k هي رسم بياني وتري يحتوي على n - k زمر قصوى بالضبط ، تحتوي كل منها على k + 1 رأسًا؛ في شجرة k التي ليست زمرة ( k + 1) بحد ذاتها ، تفصل كل زمرة قصوى الرسم البياني إلى مكونين أو أكثر، أو تحتوي على رأس ورقة واحد، وهو رأس ينتمي إلى زمرة قصوى واحدة فقط. المسار k هو شجرة k ذات ورقتين k على الأكثر ، واليرقة k هي شجرة k يمكن تقسيمها إلى مسار k ومجموعة من الأوراق k ، كل منها مجاور لزمرة k فاصلة للمسار k . وبالتحديد، فإن الرسوم البيانية القصوى ذات عرض المسار الواحد هي أشجار اليرقة تحديدًا . [ 14 ]

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

أي غابة ذات n رأسًا لها عرض مسار O (log n ) . [ 17 ] ففي الغابة، يمكن دائمًا إيجاد عدد ثابت من الرؤوس التي يؤدي حذفها إلى غابة يمكن تقسيمها إلى غابتين فرعيتين أصغر، تحتوي كل منهما على 2n / 3 رأسًا على الأكثر . الترتيب الخطي الناتج عن تقسيم كل من هاتين الغابتين الفرعيتين بشكل متكرر، مع وضع الرؤوس الفاصلة بينهما، له عدد بحث لوغاريتمي عن الرؤوس. تُظهر التقنية نفسها، عند تطبيقها على تحليل شجري للرسم البياني، أنه إذا كان عرض الشجرة للرسم البياني G ذي n رأسًا هو t ، فإن عرض مسار G هو O ( t log n ) . [ 18 ] بما أن الرسوم البيانية الخارجية المستوية ، والرسوم البيانية المتسلسلة المتوازية ، ورسوم هالين البيانية جميعها لها عرض شجرة محدود، فإن عرض مسارها جميعًا يكون لوغاريتميًا على الأكثر.

إلى جانب علاقته بعرض الشجرة، يرتبط عرض المسار أيضًا بعرض الزمرة وعرض القطع ، عبر الرسوم البيانية الخطية ؛ إذ يحتوي الرسم البياني الخطي L ( G ) للرسم البياني G على رأس لكل حافة من حواف G ، ويكون رأسان في L ( G ) متجاورين عندما تشترك الحافتان المتناظرتان في G في نقطة نهاية واحدة. أي مجموعة من الرسوم البيانية لها عرض مسار محدود إذا وفقط إذا كانت رسومها البيانية الخطية لها ذات عرض زمرة خطي محدود، حيث يستبدل عرض الزمرة الخطي عملية الاتحاد المنفصل من عرض الزمرة بعملية ضم رأس جديد واحد. [ 19 ] إذا كان للرسم البياني المتصل ذي ثلاثة رؤوس أو أكثر درجة قصوى تبلغ ثلاثة، فإن عرض القطع الخاص به يساوي عدد فصل الرؤوس في الرسم البياني الخطي الخاص به. [ 20 ]

في أي رسم بياني مستوٍ ، يكون عرض المسار متناسبًا على الأكثر مع الجذر التربيعي لعدد الرؤوس. [ 21 ] إحدى طرق إيجاد تجزئة للمسار بهذا العرض (على غرار تجزئة المسار ذات العرض اللوغاريتمي للغابات الموصوفة أعلاه) هي استخدام نظرية الفاصل المستوي لإيجاد مجموعة من O ( √n ) رأسًا ، يؤدي حذفها إلى فصل الرسم البياني إلى رسمين بيانيين فرعيين، كل منهما يحتوي على 2n/3 رأسًا على الأكثر ، ثم دمج تجزئة المسار المُنشأة بشكل متكرر لكل من هذين الرسمين البيانيين الفرعيين. تنطبق التقنية نفسها على أي فئة من الرسوم البيانية التي تنطبق عليها نظرية فاصل مماثلة. [ 22 ] بما أن فواصل الرسوم البيانية في أي عائلة رسوم بيانية مغلقة جزئيًا ثابتة، مثل الرسوم البيانية المستوية، يكون حجمها O ( √n ) ، [ 23 ] فإنه يترتب على ذلك أن عرض المسار للرسوم البيانية في أي عائلة رسوم بيانية مغلقة جزئيًا ثابتة هو أيضًا O ( √n ) . بالنسبة لبعض فئات الرسوم البيانية المستوية، يجب أن يكون عرض مسار الرسم البياني وعرض مسار الرسم البياني الثنائي له ضمن عامل ثابت: حدود من هذا الشكل معروفة للرسوم البيانية الخارجية ثنائية الاتصال [ 24 ] وللرسوم البيانية متعددة السطوح. [ 25 ] بالنسبة للرسوم البيانية المستوية ثنائية الاتصال، يكون عرض مسار الرسم البياني الثنائي أقل من عرض مسار الرسم البياني الخطي. [ 26 ] يبقى السؤال مطروحًا حول ما إذا كان عرض مسار الرسم البياني المستوي وعرض مسار الرسم البياني الثنائي له دائمًا ضمن عامل ثابت في الحالات المتبقية.

في بعض فئات الرسوم البيانية، ثبت أن عرض المسار وعرض الشجرة متساويان دائمًا: وهذا صحيح بالنسبة للرسوم البيانية التكميلية ، [ 27 ] ورسوم التبديل ، [ 28 ] ومكملات رسوم المقارنة ، [ 29 ] ورسوم المقارنة لترتيبات الفترات . [ 30 ]

مشكلة لم تُحل في الرياضيات
ما هو أكبر عرض مسار ممكن لرسم بياني مكعب ذي n رأس ؟
المزيد من المسائل غير المحلولة في الرياضيات

في أي رسم بياني مكعب ، أو بشكل أعم أي رسم بياني ذي درجة رأس قصوى تبلغ ثلاثة، يكون عرض المسار على الأكثر n / 6 + o( n ) ، حيث n هو عدد رؤوس الرسم البياني. توجد رسوم بيانية مكعبة بعرض مسار 0.082n ، ولكن من غير المعروف كيفية تقليل هذه الفجوة بين هذا الحد الأدنى والحد الأعلى n / 6 . [ 31 ]

حساب تجزئة المسار

يُعدّ تحديد ما إذا كان عرض المسار في رسم بياني مُعطى لا يتجاوز k ، عندما يكون k متغيرًا مُعطى كجزء من المُدخلات، مسألةً من فئة NP-complete. [ 5 ] أفضل حدود زمنية معروفة في أسوأ الحالات لحساب عرض المسار في رسوم بيانية عشوائية ذات n رأس هي من الشكل O (2n , n , c ) لثابت c ما . [ 32 ] مع ذلك، توجد العديد من الخوارزميات المعروفة لحساب تجزئة المسار بكفاءة أكبر عندما يكون عرض المسار صغيرًا، أو عندما تكون فئة الرسوم البيانية المُدخلة محدودة، أو تقريبًا. 

قابلية المعالجة ذات المعلمات الثابتة

يمكن حساب عرض المسار باستخدام معلمات ثابتة : لأي قيمة ثابتة k ، يمكن اختبار ما إذا كان عرض المسار لا يتجاوز k ، وإذا كان الأمر كذلك، يمكن إيجاد تجزئة للمسار بعرض k ، وذلك في زمن خطي. [ 7 ] بشكل عام، تعمل هذه الخوارزميات على مرحلتين. في المرحلة الأولى، يُفترض أن عرض مسار الرسم البياني هو k لإيجاد تجزئة للمسار أو تجزئة للشجرة غير مثالية، ولكن يمكن تحديد عرضها كدالة لـ k . في المرحلة الثانية، تُطبق خوارزمية البرمجة الديناميكية على هذه التجزئة لإيجاد التجزئة المثلى. مع ذلك، فإن الحدود الزمنية للخوارزميات المعروفة من هذا النوع أسية بالنسبة لـ k² ، وهو أمر غير عملي إلا لأصغر قيم k . [ 33 ] في حالة k = 2 ، قدم دي فلوتر (1997) خوارزمية خطية صريحة تعتمد على تجزئة هيكلية للرسوم البيانية ذات عرض المسار 2 .

فئات خاصة من الرسوم البيانية

يستعرض بودليندر (1994) تعقيد حساب عرض المسار على فئات خاصة مختلفة من الرسوم البيانية. يبقى تحديد ما إذا كان عرض مسار الرسم البياني G لا يتجاوز k مسألة NP-كاملة عندما يقتصر G على الرسوم البيانية ذات الدرجة المحدودة، [ 34 ] والرسوم البيانية المستوية ، [ 34 ] والرسوم البيانية المستوية ذات الدرجة المحدودة، [ 34 ] والرسوم البيانية الوترية ، [ 35 ] ودومينو الوتر، [ 36 ] ومكملات رسوم المقارنة ، [ 29 ] والرسوم البيانية الوراثية ثنائية الأجزاء . [ 37 ] ويترتب على ذلك مباشرةً أنها مسألة NP-كاملة أيضًا لعائلات الرسوم البيانية التي تحتوي على الرسوم البيانية الوراثية ثنائية الأجزاء، بما في ذلك الرسوم البيانية ثنائية الأجزاء، والرسوم البيانية الوترية ثنائية الأجزاء، والرسوم البيانية الوراثية، والرسوم البيانية الدائرية . [ 37 ]

مع ذلك، يمكن حساب عرض المسار في وقت خطي للأشجار والغابات. [ 9 ] كما يمكن حسابه في وقت متعدد الحدود للرسوم البيانية ذات عرض الشجرة المحدود، بما في ذلك الرسوم البيانية المتسلسلة المتوازية ، والرسوم البيانية الخارجية المستوية ، ورسوم هالين البيانية ، [ 7 ] وكذلك للرسوم البيانية المنقسمة ، [ 38 ] ولمكملات الرسوم البيانية الوترية، [ 39 ] وللرسوم البيانية التبديلية ، [ 28 ] وللرسوم البيانية التكميلية ، [ 27 ] وللرسوم البيانية ذات القوس الدائري ، [ 40 ] وللرسوم البيانية المقارنة لترتيبات الفترات، [ 30 ] وبالطبع للرسوم البيانية الفتراتية نفسها، لأنه في هذه الحالة يكون عرض المسار أقل بواحد فقط من الحد الأقصى لعدد الفترات التي تغطي أي نقطة في تمثيل فترات للرسم البياني.

خوارزميات التقريب

يُعدّ تقريب عرض المسار في الرسم البياني ضمن ثابت إضافي مسألةً صعبةً من نوع NP. [ 6 ] أفضل نسبة تقريب معروفة لخوارزمية تقريب عرض المسار ذات زمن متعدد الحدود هي O ((log n ) 3/2 ) . [ 41 ] للاطلاع على خوارزميات تقريب سابقة لعرض المسار، انظر Bodlaender et al. (1992) و Guha (2000) . وللحصول على تقريبات على فئات محدودة من الرسوم البيانية، انظر Kloks & Bodlaender (1992) .

الرسوم البيانية الصغيرة

الرسم البياني المصغر للرسم البياني G هو رسم بياني آخر مُشتق من G عن طريق تقليص الحواف، وإزالة الحواف، وإزالة الرؤوس. للرسوم البيانية المصغرة نظرية متعمقة تتضمن العديد من النتائج المهمة المتعلقة بعرض المسار.

باستثناء الغابة

إذا كانت عائلة F من الرسوم البيانية مغلقة عند أخذ المحددات الفرعية (أي أن كل محدد فرعي لعنصر من F ينتمي أيضًا إلى F )، فبموجب نظرية روبرتسون-سيمور، يمكن وصف F بأنها الرسوم البيانية التي لا تحتوي على أي محدد فرعي في X ، حيث X هي مجموعة منتهية من المحددات الفرعية المحظورة . [ 42 ] على سبيل المثال، تنص نظرية فاغنر على أن الرسوم البيانية المستوية هي الرسوم البيانية التي لا تحتوي على الرسم البياني الكامل K⁵ ولا الرسم البياني الثنائي الكامل K⁳, ³ كمحددات فرعية. في كثير من الحالات، ترتبط خصائص F وخصائص X ارتباطًا وثيقًا، وكانت أول نتيجة من هذا النوع من روبرتسون وسيمور (1983) ، [ 2 ] والتي تربط بين عرض المسار المحدود ووجود غابة في عائلة المحددات الفرعية المحظورة. على وجه التحديد، تُعرَّف عائلة F من الرسوم البيانية بأنها ذات عرض مسار محدود إذا وُجد ثابت p بحيث يكون عرض مسار كل رسم بياني في F على الأكثر p . ثم، فإن عائلة F المغلقة من قبل الصغار لها عرض مسار محدود إذا وفقط إذا كانت مجموعة X من الصغار المحظورة لـ F تتضمن غابة واحدة على الأقل.

من جهة، يسهل إثبات هذه النتيجة: إذا لم تتضمن المجموعة X غابة واحدة على الأقل، فإن الرسوم البيانية الخالية من X -minor لا تمتلك عرض مسار محدودًا. ففي هذه الحالة، تتضمن الرسوم البيانية الخالية من X -minor جميع الغابات، وتحديدًا الأشجار الثنائية الكاملة . لكن الشجرة الثنائية الكاملة ذات 2k + 1 مستوى لها عرض مسار k ، لذا في هذه الحالة، يكون عرض مسار الرسوم البيانية الخالية من X -minor غير محدود. من جهة أخرى، إذا احتوت X على غابة ذات n رأس، فإن عرض مسار الرسوم البيانية الخالية من X -minor لا يتجاوز n − 2. [ 43 ]

عوائق أمام عرض المسار المحدود

القاصرون المحظورون للرسوم البيانية ذات عرض المسار  1.

خاصية أن يكون عرض المسار على الأكثر p مغلقةٌ بحد ذاتها عند أخذ القواسم الفرعية: إذا كان للمخطط G تجزئة مسار بعرض لا يتجاوز p ، فإن تجزئة المسار نفسها تظل صالحةً إذا أُزيل أي ضلع من G ، ويمكن إزالة أي رأس من G ومن تجزئة مساره دون زيادة العرض. كما يمكن تقليص ضلع دون زيادة عرض التجزئة، وذلك بدمج المسارات الفرعية التي تمثل طرفي الضلع المُقلَّص. لذلك، يمكن تمييز المخططات ذات عرض المسار الذي لا يتجاوز p بمجموعة X<sub> p</sub> من القواسم الفرعية المستبعدة. [ 42 ] [ 44 ]

على الرغم من أن المجموعة Xp تتضمن بالضرورة غابة واحدة على الأقل، إلا أنه ليس صحيحًا أن جميع الرسوم البيانية في Xp هي غابات: على سبيل المثال، تتكون X1 من رسمين بيانيين، شجرة ذات سبعة رؤوس والمثلث K3 . ومع ذلك، يمكن تحديد مجموعة الأشجار في Xp بدقة : هذه الأشجار هي تحديدًا الأشجار التي يمكن تكوينها من ثلاث أشجار في Xp -1 عن طريق توصيل رأس جذر جديد بحافة إلى رأس مختار عشوائيًا في كل من الأشجار الثلاث الأصغر. على سبيل المثال، تتكون الشجرة ذات السبعة رؤوس في X1 بهذه الطريقة من الشجرة ذات الرأسين (حافة واحدة) في X0 . بناءً على هذا البناء، يمكن إثبات أن عدد القواسم الفرعية المحظورة في Xp هو على الأقل ( p !) 2 . [ 44 ] تم حساب المجموعة الكاملة X2 للقواسم الفرعية المحظورة للرسوم البيانية ذات عرض المسار 2؛ وهي تحتوي على 110 رسوم بيانية مختلفة. [ 45 ]

نظرية البنية

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

التطبيقات

VLSI

في تصميم الدوائر المتكاملة واسعة النطاق (VLSI) ، تمت دراسة مشكلة فصل الرؤوس في الأصل كوسيلة لتقسيم الدوائر إلى أنظمة فرعية أصغر، مع عدد قليل من المكونات على الحدود بين الأنظمة الفرعية. [ 34 ]

استخدم أوتسوكي وآخرون (1979) سُمك الفاصل الزمني لنمذجة عدد المسارات اللازمة في تصميم أحادي البعد لدائرة VLSI، تتكون من مجموعة من الوحدات التي تحتاج إلى الربط فيما بينها عبر نظام من الشبكات. في نموذجهم، يتم إنشاء رسم بياني تمثل فيه الرؤوس الشبكات، ويرتبط رأسان بحافة إذا كانت شبكتاهما متصلتين بالوحدة نفسها؛ أي، إذا فُسِّرت الوحدات والشبكات على أنها تُشكِّل عُقدًا وحوافًا فائقة لرسم بياني فائق ، فإن الرسم البياني المُشكَّل منها هو الرسم البياني الخطي لهذا الرسم البياني. يصف تمثيل الفاصل الزمني للرسم البياني الفائق لهذا الرسم البياني الخطي، بالإضافة إلى تلوين الرسم البياني الفائق، ترتيب الشبكات على طول نظام من المسارات الأفقية (مسار واحد لكل لون) بطريقة تسمح بوضع الوحدات على طول المسارات بترتيب خطي وربطها بالشبكات المناسبة. إن حقيقة أن الرسوم البيانية الفاصلية هي رسوم بيانية مثالية [ 47 ] تعني أن عدد الألوان المطلوبة، في الترتيب الأمثل لهذا النوع، هو نفس عدد الزمر لإكمال الفاصل الزمني للرسم البياني الشبكي.

يُعدّ تخطيط مصفوفة البوابات [ 48 ] نمطًا خاصًا من تخطيطات الدوائر المتكاملة واسعة النطاق بتقنية CMOS لدوائر المنطق البولياني . في هذا النوع من التخطيطات، تنتشر الإشارات على طول "خطوط" (قطع مستقيمة رأسية)، بينما تتكون كل بوابة من سلسلة من خصائص الجهاز التي تقع على طول قطعة مستقيمة أفقية . وبالتالي، يجب أن تتقاطع القطعة المستقيمة الأفقية لكل بوابة مع القطع المستقيمة الرأسية لكل خط من الخطوط التي تُشكّل مدخلات أو مخرجات البوابة. وكما هو الحال في تخطيطات أوتسوكي وآخرون (1979) ، يمكن إيجاد تخطيط من هذا النوع يُقلّل عدد المسارات الرأسية التي تُرتّب عليها الخطوط، وذلك بحساب عرض مسار رسم بياني تكون فيه الخطوط هي رؤوسه، وأزواج الخطوط التي تشترك في بوابة واحدة هي حوافه. [ 49 ] ويمكن استخدام نفس المنهجية الحسابية لنمذجة مشاكل الطي في مصفوفات المنطق القابلة للبرمجة . [ 50 ]

رسم بياني

يُستخدم عرض المسار في العديد من تطبيقات رسم المخططات البيانية :

  • تتميز الرسوم البيانية الدنيا التي لها عدد تقاطعات معين بعرض مسار محدود بدالة لعدد تقاطعاتها. [ 51 ]
  • يتناسب عدد الخطوط المتوازية التي يمكن رسم رؤوس الشجرة عليها دون تقاطع الحواف (في ظل قيود طبيعية مختلفة على طرق وضع الرؤوس المتجاورة بالنسبة لتسلسل الخطوط) مع عرض مسار الشجرة. [ 52 ]
  • رسم بياني ذو طبقات h و k تقاطع للرسم البياني G هو عبارة عن وضع رؤوس G على h خطوط أفقية متميزة، مع توجيه الحواف كمسارات مضلعة رتيبة بين هذه الخطوط، بحيث يكون عدد التقاطعات k على الأكثر . تتميز الرسوم البيانية ذات هذه الرسومات بعرض مسار محدود بدالة لـ h و k . لذلك، عندما يكون كل من h و k ثابتين، يمكن تحديد ما إذا كان للرسم البياني رسم بياني ذو طبقات h و k تقاطع في وقت خطي . [ 53 ]
  • يمكن تضمين رسم بياني ذي n رأسًا وعرض مسار p في شبكة ثلاثية الأبعاد بحجم p × p × n بحيث لا يتقاطع أي ضلعين (ممثلين بقطع مستقيمة بين نقاط الشبكة). وبالتالي، فإن الرسوم البيانية ذات عرض المسار المحدود لها تضمينات من هذا النوع بحجم خطي. [ 54 ]

تصميم المترجم

في عملية تجميع لغات البرمجة عالية المستوى ، يبرز مفهوم عرض المسار عند إعادة ترتيب تسلسلات التعليمات البرمجية الخطية (أي التعليمات البرمجية التي لا تحتوي على فروع تحكم أو حلقات) بحيث يمكن وضع جميع القيم المحسوبة في سجلات الجهاز بدلاً من تخزينها في الذاكرة الرئيسية. في هذا التطبيق، تُمثَّل التعليمات البرمجية المراد تجميعها كرسم بياني موجه غير دوري، حيث تمثل العقد قيم الإدخال للتعليمات البرمجية والقيم المحسوبة بواسطة العمليات داخلها. يمثل الضلع من العقدة x إلى العقدة y في هذا الرسم البياني الموجه غير الدوري أن القيمة x هي إحدى مدخلات العملية y . يمثل الترتيب الطوبولوجي لرؤوس هذا الرسم البياني الموجه غير الدوري إعادة ترتيب صحيحة للتعليمات البرمجية، ويُحدد عدد السجلات اللازمة لتقييم التعليمات البرمجية في ترتيب معين بواسطة عدد فواصل الرؤوس في هذا الترتيب. [ 55 ]

لأي عدد ثابت w من سجلات الآلة، يمكن تحديد ما إذا كان من الممكن إعادة ترتيب جزء من التعليمات البرمجية الخطية بحيث يمكن تقييمه باستخدام w سجل على الأكثر، وذلك في زمن خطي. فإذا كان عدد فواصل الرؤوس في الترتيب الطوبولوجي w على الأكثر ، فإن الحد الأدنى لفاصل الرؤوس بين جميع الترتيبات لا يمكن أن يكون أكبر، وبالتالي فإن الرسم البياني غير الموجه الناتج عن تجاهل اتجاهات الرسم البياني الموجه غير الدوري (DAG) الموصوف أعلاه يجب أن يكون عرض مساره w على الأكثر . يمكن اختبار صحة ذلك باستخدام الخوارزميات المعروفة ذات المعاملات الثابتة لحساب عرض المسار، وإذا كان الأمر كذلك، يمكن إيجاد تحليل مسار للرسم البياني غير الموجه في زمن خطي بافتراض أن w ثابت. بمجرد إيجاد تحليل المسار، يمكن إيجاد ترتيب طوبولوجي بعرض w (إن وجد) باستخدام البرمجة الديناميكية، وذلك أيضًا في زمن خطي. [ 55 ]

اللغويات

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

الخوارزميات الأسية

يمكن حل العديد من مشاكل خوارزميات الرسوم البيانية بكفاءة على الرسوم البيانية ذات عرض المسار المنخفض، باستخدام البرمجة الديناميكية على تجزئة المسار للرسم البياني. [ 10 ] على سبيل المثال، إذا تم إعطاء ترتيب خطي لرؤوس رسم بياني G ذي n رأس ، مع عدد فصل الرؤوس w ، فمن الممكن إيجاد أكبر مجموعة مستقلة لـ G في زمن O(2 w n ). [ 31 ] على الرسوم البيانية ذات عرض المسار المحدود، يؤدي هذا النهج إلى خوارزميات قابلة للمعالجة ذات معلمات ثابتة، يتم تحديدها بواسطة عرض المسار. [ 49 ] لا توجد مثل هذه النتائج بشكل متكرر في الأدبيات لأنها مشمولة بخوارزميات مماثلة يتم تحديدها بواسطة عرض الشجرة؛ ومع ذلك، يظهر عرض المسار حتى في خوارزميات البرمجة الديناميكية القائمة على عرض الشجرة عند قياس التعقيد المكاني لهذه الخوارزميات. [ 11 ]

يمكن تطبيق أسلوب البرمجة الديناميكية نفسه على الرسوم البيانية ذات عرض المسار غير المحدود، مما يؤدي إلى خوارزميات تحل مسائل الرسوم البيانية غير المُعَلمة في زمن أُسّي . على سبيل المثال، يُظهر دمج هذا الأسلوب مع حقيقة أن عرض مسار الرسوم البيانية المكعبة هو n /6  +  o( n )، أنه في الرسم البياني المكعب، يمكن إنشاء المجموعة المستقلة القصوى في زمن O(2n / 6  +  o( n ) )، وهو أسرع من الطرق المعروفة سابقًا. [ 31 ] ويؤدي نهج مماثل إلى خوارزميات مُحسَّنة ذات زمن أُسّي لمسائل القطع الأقصى ومجموعة الهيمنة الدنيا في الرسوم البيانية المكعبة، [ 31 ] ولعدة مسائل تحسين أخرى من نوع NP-hard. [ 57 ]

انظر أيضاً

  • Boxicity ، طريقة مختلفة لقياس تعقيد أي رسم بياني من حيث الرسوم البيانية الفاصلية
  • عرض القطع ، وهو الحد الأدنى الممكن لعرض الترتيب الخطي لرؤوس الرسم البياني
  • عمق الشجرة ، وهو عدد محدود لعائلة رسوم بيانية مغلقة جزئيًا إذا وفقط إذا كانت العائلة تستبعد مسارًا
  • الانحلال ، وهو مقياس لتباعد الرسم البياني الذي يساوي على الأكثر عرض مساره
  • عرض نطاق الرسم البياني ، وهي مشكلة تحسين مختلفة من نوع NP-complete تتضمن تخطيطات خطية للرسوم البيانية
  • عدد ستراهلر ، وهو مقياس لتعقيد الأشجار الجذرية، ويُعرَّف بشكل مشابه لعرض المسار للأشجار غير الجذرية.

ملحوظات

  1. ↑ ديستل وكوهن (2005) .
  2. 1 2 3 4 روبرتسون وسيمور (1983) .
  3. ↑ كينرسلي (1989) ؛ بودليندر (1998) .
  4. 1 2 روبرتسون وسيمور (2003) .
  5. 1 2 كاشيوابارا وفوجيساوا (1979) ؛ أوتسوكي وآخرون. (1979) ; لينجور (1981) ; أرنبورج، كورنيل وبروسكوروسكي (1987) .
  6. 1 2 بودلاندر وآخرون. (1992) .
  7. 1 2 3 بودلاندر (1996) ; بودلاندر وكلوكس (1996)
  8. ↑ بودليندر (1994) .
  9. 1 2 مورينج (1990) ؛ شيفلر (1990) ; إليس، سودبورو وتيرنر (1994) ؛ بنغ وآخرون. (1998) ; سكودينيس (2000) ; سكودينيس (2003) ; كوديرت وهوك ومازوريك (2012) .
  10. 1 2 أرنبورغ (1985) .
  11. 1 2 Aspvall, Proskurowski & Telle (2000) .
  12. ↑ بودليندر (1998) ، النظرية 29، ص 13.
  13. ^ كينرسلي (1989) ؛ كينرسلي (1992) ; بودلاندر (1998) ، النظرية 51.
  14. ↑ بروسكوروفسكي وتيل (1999) .
  15. ↑ Korach & Solel (1993) ، Lemma 3 ص.99؛ Bodlaender (1998) ، Theorem 47، ص. 24.
  16. ↑ Korach & Solel (1993) ، Lemma 1، ص. 99؛ Bodlaender (1998) ، Theorem 49، ص. 24.
  17. ↑ Korach & Solel (1993) ، النظرية 5، ص 99؛ Bodlaender (1998) ، النظرية 66، ص 30. Scheffler (1992) يعطي حدًا أعلى أكثر دقة لـ log 3 (2 n + 1) على عرض المسار لغابة ذات n رأس.
  18. ↑ Korach & Solel (1993) ، النظرية 6، ص. 100؛ Bodlaender (1998) ، النتيجة 24، ص.10.
  19. ↑ جورسكي ووانكي (2007) .
  20. ↑ غولوفاتش (1993) .
  21. ↑ بودليندر (1998) ، النتيجة 23، ص 10.
  22. ↑ بودليندر (1998) ، النظرية 20، ص. 9.
  23. ↑ ألون، سيمور وتوماس (1990) .
  24. ↑ Bodlaender & Fomin (2002) ; Coudert, Huc & Sereni (2007) .
  25. ^ فومين وثيليكوس (2007) ؛ أميني وهوك وبيرينس (2009) .
  26. ↑ فومين (2003) .
  27. 1 2 بودلاندر و مورينج (1990) .
  28. 1 2 بودلاندر، كلوكس وكراتش (1993) .
  29. 1 2 حبيب ومورينغ (1994) .
  30. 1 2 غارب (1995) .
  31. 1 2 3 4 فومين وهوي (2006) .
  32. ↑ فومين وآخرون (2008) .
  33. ↑ داوني وزملاء (1999) ، ص 12.
  34. 1 2 3 4 مونين وسودبورو (1988) .
  35. ↑ جوستيدت (1993) .
  36. ↑ كلوكس، كراتش ومولر (1995) . الدومينو الوتري هو رسم بياني وتري ينتمي فيه كل رأس إلى مجموعتين عظميين على الأكثر.
  37. 1 2 كلوكس وآخرون (1993) .
  38. ^ كلوكس وبودلايندر (1992) ؛ جوستيدت (1993) .
  39. ↑ يعزو غارب (1995) هذه النتيجة إلى أطروحة الدكتوراه التي قدمها تون كلوكس عام 1993؛ خوارزمية غارب متعددة الحدود للرسوم البيانية للمقارنة ذات الترتيبات الفاصلية تعمم هذه النتيجة، حيث يجب أن يكون أي رسم بياني وتر رسمًا بيانيًا للمقارنة من هذا النوع.
  40. ↑ سوشان وتودينكا (2007) .
  41. ^ فيجي وهاجياغاي ولي (2005) .
  42. 1 2 روبرتسون وسيمور (2004) .
  43. ↑ بينستوك وآخرون (1991) ؛ ديستل (1995) ؛ كاتيل، دينين وفيلوز (1996) .
  44. 1 2 كينرسلي (1992) ; تاكاهاشي، أوينو وكاجيتاني (1994) ؛ بودليندر (1998) ، ص. 8.
  45. ↑ كينرسلي ولانغستون (1994) .
  46. ^ ديمين وهاجياغاي وكاواراباياشي (2005) .
  47. ↑ بيرج (1967) .
  48. ↑ لوبيز ولو (1980) .
  49. 1 2 فيلوز ولانغستون (1989) .
  50. ^ مورينج (1990) ؛ فيريرا وسونغ (1992) .
  51. ↑ هلينيني (2003) .
  52. ↑ سودرمان (2004) .
  53. ↑ دوجيموفيتش وآخرون (2008) .
  54. ^ دوجموفيتش ومورين وود (2003) .
  55. 1 2 Bodlaender, Gustedt & Telle (1998) .
  56. ↑ ميلر (1956) .
  57. ^ كنيس وآخرون. (2005) ؛ بيوركلوند وهوسفيلدت (2008) .

مراجع