توصيف الرسم البياني المحظور

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 9 صور
الموسوعة الحرة
يتم وصف الرسوم البيانية ثنائية الأجزاء ، التي يمكن تقسيم رؤوسها إلى مجموعتين بحيث لا يكون أي رأس في كل مجموعة مجاورًا لأي رأس آخر داخل نفس المجموعة، بدقة من خلال التوصيف المحظور المتمثل في عدم وجود رسوم بيانية ذات دورات فردية كرسوم بيانية فرعية.

في نظرية الرسم البياني ، وهي فرع من الرياضيات، يمكن وصف العديد من العائلات المهمة من الرسوم البيانية بواسطة مجموعة محدودة من الرسوم البيانية الفردية التي لا تنتمي إلى العائلة، كما يتم استبعاد جميع الرسوم البيانية من العائلة التي تحتوي على أي من هذه الرسوم البيانية المحظورة كرسم بياني فرعي (مستحث) أو رسم بياني ثانوي .

من الأمثلة النموذجية لهذه الظاهرة نظرية كوراتوفسكي ، التي تنص على أن الرسم البياني يكون مستويًا (يمكن رسمه دون تقاطعات في المستوى) إذا وفقط إذا لم يحتوِ على أي من الرسمين البيانيين المحظورين، وهما الرسم البياني الكامل K⁵ والرسم البياني الثنائي الكامل K⁳ ,³ . في نظرية كوراتوفسكي، يُعرَّف مفهوم الاحتواء بأنه تماثل الرسم البياني ، حيث يظهر أي تقسيم لأحد الرسمين البيانيين كرسم بياني جزئي للآخر. وبالتالي، فإن كل رسم بياني إما أن يكون له رسم مستوٍ (وفي هذه الحالة ينتمي إلى عائلة الرسوم البيانية المستوية) أو أن يكون له تقسيم لأحد هذين الرسمين البيانيين على الأقل كرسم بياني جزئي (وفي هذه الحالة لا ينتمي إلى الرسوم البيانية المستوية).

تعريف

بشكل أعم، يُعدّ توصيف الرسم البياني المحظور طريقةً لتحديد مجموعة من هياكل الرسوم البيانية ، أو الرسوم البيانية الفائقة ، وذلك بتحديد الهياكل الفرعية المحظورة الوجود داخل أي رسم بياني ضمن هذه المجموعة. وتختلف المجموعات المختلفة في طبيعة ما هو محظور . عمومًا، يُعتبر الهيكل G عضوًا في مجموعة من هذه الهياكل.F{\displaystyle {\mathcal {F}}}إذا وفقط إذا لم تكن البنية الفرعية المحظورة موجودة في G. قد تكون البنية الفرعية المحظورة واحدة مما يلي:

يمكن أيضًا تسمية مجموعة الهياكل الممنوعة من الانتماء إلى عائلة رسوم بيانية معينة بمجموعة العوائق لتلك العائلة.

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

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

قائمة بالخصائص المحظورة للرسوم البيانية والرسوم البيانية الفائقة

عائلةالعوائقالعلاقةمرجع
الغاباتالحلقات، وأزواج الحواف المتوازية، والدورات بجميع أطوالهاالرسم البياني الفرعيتعريف
حلقة (للرسوم البيانية المتعددة) أو مثلث K 3 (للرسوم البيانية البسيطة)الرسم البياني الصغيرتعريف
الغابات الخطية[حلقة / مثلث K 3 (انظر أعلاه)] ونجمة K 1,3الرسم البياني الصغيرتعريف
رسوم بيانية خالية من المخالبستار ك 1.3الرسم البياني الفرعي المستحثتعريف
رسوم بيانية للمقارنةالرسم البياني الفرعي المستحث
الرسوم البيانية الخالية من المثلثاتالمثلث K 3الرسم البياني الفرعي المستحثتعريف
الرسوم البيانية المستويةK 5 و K 3,3الرسم البياني الفرعي المتماثلنظرية كوراتوفسكي
K 5 و K 3,3الرسم البياني الصغيرنظرية فاغنر
الرسوم البيانية الخارجية المستويةK 4 و K 2,3الرسم البياني الصغيرديستل (2000) ، [ 1 ] ص 107
رسوم بيانية لجنس ثابتمجموعة عوائق محدودةالرسم البياني الصغيرديستل (2000) ، [ 1 ] ص 275
رسوم بيانية Apexمجموعة عوائق محدودةالرسم البياني الصغير[ 2 ]
رسوم بيانية قابلة للتضمين بدون روابطعائلة بيترسنالرسم البياني الصغير[ 3 ]
الرسوم البيانية ثنائية الأجزاءدورات غير منتظمةالرسم البياني الفرعي[ 4 ]
الرسوم البيانية الوتريةدورات طولها 4 أو أكثرالرسم البياني الفرعي المستحث[ 5 ]
رسوم بيانية مثاليةدورات ذات طول فردي 5 أو أكثر أو مكملاتهاالرسم البياني الفرعي المستحث[ 6 ]
رسم بياني خطي للرسوم البيانية9 فقرات فرعية محظورةالرسم البياني الفرعي المستحث[ 7 ]
اتحادات الرسوم البيانية لرسوم بيانية من نوع الصبارالرسم البياني الماسي ذو الرؤوس الأربعة الناتج عن إزالة حافة من الرسم البياني الكامل K 4الرسم البياني الصغير[ 8 ]
الرسوم البيانية السلميةK 2,3 ورسمه البياني المزدوجالرسم البياني الفرعي المتماثل[ 9 ]
الرسوم البيانية المنقسمةج4،ج5،ج¯4(=ك2+ك2){\displaystyle C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)}الرسم البياني الفرعي المستحث[ 10 ]
2-متصل على التوالي والتوازي ( عرض الشجرة ≤  2، عرض الفرع  ≤  2)ك 4الرسم البياني الصغيرديستل (2000) ، [ 1 ] ص 327
عرض الشجرة ≤  3K 5 ، ثماني الأوجه ، منشور خماسي ، رسم بياني فاغنرالرسم البياني الصغير[ 11 ]
عرض الفرع ≤  3K 5 ، ثماني السطوح ، مكعب ، رسم بياني فاغنرالرسم البياني الصغير[ 12 ]
الرسوم البيانية القابلة للاختزال التكميلي (الرسوم البيانية التكميلية)المسار ذو 4 رؤوس P 4الرسم البياني الفرعي المستحث[ 13 ]
رسوم بيانية مثالية بشكل تافهالمسار ذو 4 رؤوس P 4 والدورة ذات 4 رؤوس C 4الرسم البياني الفرعي المستحث[ 14 ]
رسوم بيانية للعتبةالمسار ذو الأربع رؤوس P4 ، والدورة ذات الأربع رؤوس C4 ، ومكمل C4الرسم البياني الفرعي المستحث[ 14 ]
رسم بياني خطي للرسوم البيانية الخطية الفائقة المنتظمة الثلاثيةقائمة محدودة من الرسوم البيانية الفرعية المستحثة المحظورة ذات درجة دنيا لا تقل عن 19الرسم البياني الفرعي المستحث[ 15 ]
رسم بياني خطي للرسوم البيانية الخطية الفائقة المنتظمة من الرتبة k ، حيث k  >  3قائمة محدودة من الرسوم البيانية الفرعية المستحثة المحظورة ذات درجة حافة دنيا لا تقل عن 2k² - 3k + 1    الرسم البياني الفرعي المستحث[ 16 ] [ 17 ]
الرسوم البيانية القابلة للاختزال إلى رأس واحد ΔYقائمة محدودة تضم ما لا يقل عن 68 مليار مجموع مختلف من مجموعات (1، 2، 3)الرسم البياني الصغير[ 18 ]
رسوم بيانية لنصف القطر الطيفي على الأكثرλ{\displaystyle \lambda }توجد مجموعة عوائق منتهية إذا وفقط إذاλ<2+5{\displaystyle \lambda <{\sqrt {2+{\sqrt {5}}}}}وλ≠βم1/2+βم-1/2{\displaystyle \lambda \neq \beta _{m}^{1/2}+\beta _{m}^{-1/2}}لأيم≥2{\displaystyle m\geq 2}، أينβم{\displaystyle \beta _{m}}هو الجذر الأكبر لـxم+1=1+x+⋯+xم-1{\displaystyle x^{m+1}=1+x+\dots +x^{m-1}}.الرسم البياني الفرعي / الرسم البياني الفرعي المستحث[ 19 ]
الرسوم البيانية العنقوديةرسم بياني لمسار ثلاثي الرؤوسالرسم البياني الفرعي المستحث
النظريات العامة
عائلة تُعرَّف بخاصية وراثية مستحثةمجموعة عوائق، قد تكون غير منتهيةالرسم البياني الفرعي المستحث
عائلة تُعرَّف بملكية وراثية قاصرمجموعة عوائق محدودةالرسم البياني الصغيرنظرية روبرتسون-سيمور

انظر أيضاً

مراجع

  1. 1 2 3 ديستل، راينهارد (2000)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد  173، سبرينغر-فيرلاغ، ISBN 0-387-98976-5.
  2. ↑ غوبتا، أ.؛ إمباغليازو، ر. (1991)، "حساب التشابكات المستوية" ، وقائع الندوة الثانية والثلاثين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS '91) ، جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 802-811 ، doi : 10.1109/SFCS.1991.185452 ، ISBN  0-8186-2445-0، S2CID 209133 .
  3. ↑ روبرتسون، نيل ؛ سيمور، بي دي ؛ توماس، روبن (1993)، "تضمينات غير مرتبطة للرسوم البيانية في الفضاء ثلاثي الأبعاد"، نشرة الجمعية الرياضية الأمريكية ، 28 (1): 84-89 ، arXiv : math/9301216 ، doi : 10.1090/S0273-0979-1993-00335-5 ، MR 1164063 ، S2CID 1110662  .
  4. ^ بيلا بولوباس (1998) “نظرية الرسم البياني الحديثة”، سبرينغر، ISBN 0-387-98488-7ص 9
  5. ^ كاشيوابارا، توشينوبو (1981)، “خوارزميات لبعض الرسوم البيانية للتقاطع”، في سايتو، نوبوجي؛ نيشيزيكي، تاكاو (محرران)، نظرية الرسم البياني والخوارزميات، الندوة السابعة عشرة لمعهد أبحاث الاتصالات الكهربائية، جامعة توهوكو، سينداي، اليابان، 24-25 أكتوبر 1980، وقائع ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 108، سبرينغر-فيرلاغ، الصفحات من 171 إلى 181، دوى : 10.1007/3-540-10704-5_15 ، ISBN   978-3-540-10704-0.
  6. ↑ تشودنوفسكي، ماريا ؛ روبرتسون، نيل ؛ سيمور، بول ؛ توماس، روبن (2006)، "نظرية الرسم البياني المثالي القوي" (ملف PDF) ، حوليات الرياضيات ، 164 (1): 51-229 ، arXiv : math/0212070v1 ، doi : 10.4007/annals.2006.164.51 ، S2CID 119151552 .
  7. ^ Beineke، LW (1968)، “الرسوم البيانية المشتقة من digraphs”، في Sachs، H .؛ فوس، H.-J.؛ والتر، H.-J. (محرران)، Beiträge zur Graphentheorie ، لايبزيغ: تيوبنر، الصفحات من 17 إلى 33 .
  8. ↑ الملاح، إيهاب؛ كولبورن، تشارلز ج. (1988)، "تعقيد بعض مسائل حذف الحواف"، معاملات IEEE للدوائر والأنظمة ، 35 (3): 354-362 ، Bibcode : 1988ITCS...35..354E ، doi : 10.1109/31.1748.
  9. ↑ تاكاميزاوا، ك.؛ نيشيزيكي، تاكاو ؛ سايتو، نوبوجي (1981)، "مسائل توافقية على الرسوم البيانية المتسلسلة المتوازية"، الرياضيات التطبيقية المنفصلة ، ​​3 (1): 75-76 ، doi : 10.1016/0166-218X(81)90031-7.
  10. ↑ فولديس، ستيفان؛ هامر، بيتر لاديسلاو (1977أ)، "الرسوم البيانية المنقسمة"، وقائع المؤتمر الثامن لجنوب شرق الولايات المتحدة حول التوافقية ونظرية الرسوم البيانية والحوسبة (جامعة ولاية لويزيانا، باتون روج، لويزيانا، 1977) ، كونغرسوس نوميرانتيوم، المجلد التاسع عشر، وينيبيغ: يوتيليتاس ماث، الصفحات 311-315 ، MR 0505860   
  11. ↑ بودليندر، هانز ل. (1998)، "شجرة جزئية من النوع k للرسوم البيانية ذات عرض شجرة محدود"، علوم الحاسوب النظرية ، 209 ( 1-2 ): 1-45 ، doi : 10.1016/S0304-3975(97)00228-4 ، hdl : 1874/18312.
  12. ↑ بودليندر، هانز ل.؛ ثيليكوس، ديميتريوس م. (1999)، "الرسوم البيانية ذات عرض الفروع على الأكثر ثلاثة"، مجلة الخوارزميات ، 32 (2): 167-194 ، doi : 10.1006/jagm.1999.1011 ، hdl : 1874/2734.
  13. ↑ سينش، د. (1974)، "حول خاصية لفئة الرسوم البيانية القابلة للتلوين بـ n لونًا"، مجلة نظرية التوافيق ، السلسلة ب، 16 (2): 191-193 ، doi : 10.1016/0095-8956(74)90063-X ، MR 0337679 
  14. 1 2 غولومبيك، مارتن تشارلز (1978)، "الرسوم البيانية المثالية التافهة"، الرياضيات المتقطعة ، 24 (1): 105-107 ، doi : 10.1016/0012-365X(78)90178-4.
  15. ↑ ميتلسكي، يوري؛ تيشكيفيتش، ريجينا (1997)، "حول الرسوم البيانية الخطية للرسوم البيانية الفائقة الخطية المنتظمة من الدرجة 3"، مجلة نظرية الرسوم البيانية ، 25 (4): 243-251 ، doi : 10.1002/(SICI)1097-0118(199708)25:4 < 243::AID-JGT1 > 3.0.CO ؛ 2-K ، MR 1459889 
  16. ↑ جاكوبسون، إم إس؛ كيزدي، أندريه إي؛ ليهيل، جينو (1997)، "التعرف على رسوم بيانية للتقاطع للرسوم البيانية الخطية المنتظمة الفائقة"، الرسوم البيانية والتوافقية ، 13 (4): 359-367 ، doi : 10.1007/BF03353014 ، MR 1485929 ، S2CID 9173731  
  17. ↑ نايك، رانجان ن.؛ راو، إس بي؛ شريكاندي، إس إس ؛ سينغي، إن إم (1982)، "رسوم بيانية للتقاطع للرسوم البيانية الفائقة المنتظمة من الرتبة k "، المجلة الأوروبية للتوافقية ، 3 : 159-172 ، doi : 10.1016/s0195-6698(82)80029-2 ، MR 0670849 
  18. ↑ يو، يانمينغ (2006)، "المزيد من القاصرين المحظورين لاختزال واي-دلتا-واي"، المجلة الإلكترونية للتوافقية ، 13 R7، doi : 10.37236/1033موقع إلكتروني
  19. ↑ جيانغ، زيلين؛ بوليانسكي، ألكسندر (2020-03-01). "الرسوم البيانية الفرعية المحظورة للرسوم البيانية ذات نصف القطر الطيفي المحدود، مع تطبيقات على الخطوط متساوية الزوايا" . مجلة إسرائيل للرياضيات . 236 (1): 393-421 . arXiv : 1708.02317 . doi : 10.1007/s11856-020-1983-2 . ISSN 1565-8511 .