مرجع
آخر الزيارات

طوق (نظرية البيان)

498 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في نظرية البيان، الطَّوْق أو الخصر في رسم بياني هو طول أقصر دورة فيه. في هذه المقالة 3 أقسام: «المقاس وتلوين الرسم البياني»، «المفاهيم ذات الصلة» و«أقفاص».
المحتويات
  1. المقاس وتلوين الرسم البياني
  2. المفاهيم ذات الصلة
  3. أقفاص

على سبيل التعريف، في نظرية البيان، الطَّوْق أو الخصر في رسم بياني هو طول أقصر دورة فيه. إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . مثلًا، دورة طولها 4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 كذلك، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات . وفيما يلي تفاصيل أوسع عن ذلك.

المقاس وتلوين الرسم البياني

كذلك، لأي أعداد صحيحة موجبة و ، يوجد رسم بياني ذو مقاس على الأقل ورقم لوني على الأقل ؛ مثلًا، في الرسم البياني Grötzsch بدون مثلث ووالذي به العدد اللوني 4 وبتكرار شكل Mycielskian المستعمل فيه، ينتج عنه رسومات بدون لمثلث لها عدد لوني كبير . كان بول إيردوس أول من أثبت هذه النتيجة العامة، باستخدام الطريقة الاحتمالية . بتعبير أدق، أوضح أن رسمًا عشوائيًا على رؤوس ، يتشكل باختيار مستقل للأضلاع بحيث كل ضلع يظهر بهذا الرسم باحتمال قدره . بالتالي فإن هذا الرسم يحتوي على الأكثر من الدورات بطول عالأكثر باحتمال يقترب من 1 عندما تقترب إلى ما لا نهاية . لكن في هذه الحالة فإن هذا الرسم ليس لديه مجموعة مستقلة بحجم . فبالتالي فإن حذف رأس واحد من كل دورة قصيرة قد يؤدي إلى تناقض لكون أقصردوره به المعرف بالمقاس يكون أكبر من . في حين مطلوب أن تكون كل فئة من ألوان التلوين صغيرة وتتطلب بالتالي ألوان على الأقل في أي تلوين.

وفي هذا الصدد، يمكن إنشاء رسومات بيانية صريحة، رغم أنها كبيرة الحجم وذات مقاس كبير وأرقام لونية، كرسومات توضيحية معينة من Cayley للمجموعات الخطية على الحقول المحدودة . تحتوي هذه الرسوم البيانية المميزة لـ Ramanujan كذلك على معامل توسع كبير.

المفاهيم ذات الصلة

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

إضافةً إلى ذلك، يُنظر إلى المقاس على أنه أقصر طول لدورة غير تافهة، وهذا التعريف يوافق التعميمات المعرفة في 1-systole أو أعلى الانقباضات في systolic geometry.

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

ومن جهة أخرى، محيط الرسم البياني (circumference) هو طول أطول دورة، وليس أقصرها.

أقفاص

وفي هذا السياق، يُعرف الرسم البياني المكعب ( والذي به جميع رؤوسه من الدرجة الثالثة) الذي مقاسه يساوي باسم قفص (cage) بحجم ( أو قفص من النوع (3، )).مثال على ذلك الرسم البياني Petersen يمثل قفص وحيد بحجم 5 (وهو أصغر رسم بياني مكعب بمقاس 5) . وهنا مثال آخر هو الرسم Heawood والذي يعتبر قفص فريد بحجم 6 بينما في الرسم McGee هو قفص حجمه يساوي 7 . والشكل Tutte به قفص بحجم 8. من الممكن وجودك أقفاص متعددة لنفس المقاس . مثلًا، هنا ثلاثة أقفاص غير متجانسة بحجم 10 وكل منها يحتوي على 70 رأسًا: Balaban 10-cage ، والرسم البياني Harries والرسم البياني Harries-Wong .

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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