في نظرية الرسومات ، مقاس محيط ( المقاس أختصارا) (girth) رسم بياني هو طول أقصر دورة في الرسم البياني. [1] إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . [2] على سبيل المثال، دورة طولها4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات .
أقفاص
يُعرف الرسم البياني المكعب ( والذي به جميع رؤوسه من الدرجة الثالثة) الذي مقاسه يساوي g باسم قفص (cage) بحجم g ( أو قفص من النوع (3، g )).مثال على ذلك الرسم البياني Petersen يمثل قفص وحيد بحجم 5 (وهو أصغر رسم بياني مكعب بمقاس 5) . وهنا مثال آخر هو الرسم Heawood والذي يعتبر قفص فريد بحجم 6 بينما في الرسم McGee هو قفص حجمه يساوي 7 . والشكل Tutte به قفص بحجم 8. [3] من الممكن وجودك أقفاص متعددة لنفس المقاس . على سبيل المثال، هنا ثلاثة أقفاص غير متجانسة بحجم 10 وكل منها يحتوي على 70 رأسًا: Balaban 10-cage ، والرسم البياني Harries والرسم البياني Harries-Wong .
هنا الرسم Petersen بمقاس 5.
الشكل يوضح الرسم Heawood والذي مقاسه يساوي 6.
الرسم McGee والذي المقاس فيه يساوي7.
الرسم Tutte–Coxeter والذي مقاس المحيط فيه يساوي 8.
المقاس وتلوين الرسم البياني
لأي أعداد صحيحة موجبة g و χ ، يوجد رسم بياني ذو مقاس g على الأقل ورقم لوني على الأقل χ ؛ على سبيل المثال، في الرسم البياني Grötzsch بدون مثلث ووالذي به العدد اللوني 4 وبتكرار شكل Mycielskian المستخدم فيه، ينتج عنه رسومات بدون لمثلث لها عدد لوني كبير . كان بول إيردوس أول من أثبت هذه النتيجة العامة، باستخدام الطريقة الاحتمالية . [4] بتعبير أدق، أوضح أن رسمًا عشوائيًا على رؤوس n ، يتشكل باختيار مستقل للأضلاع بحيث كل ضلع يظهر بهذا الرسم باحتمال قدره n(1 − g)/g . بالتالي فإن هذا الرسم يحتوي على الأكثر n/2 من الدورات بطول g عالأكثر باحتمال يقترب من 1 عندما n تقترب إلى ما لا نهاية . لكن في هذه الحالة فإن هذا الرسم ليس لديه مجموعة مستقلة بحجم n/2k . فبالتالي فإن حذف رأس واحد من كل دورة قصيرة قد يؤدي إلى تناقض لكون أقصردوره به المعرف بالمقاس يكون أكبر من g . في حين مطلوب أن تكون كل فئة من ألوان التلوين صغيرة وتتطلب بالتالي ألوان k على الأقل في أي تلوين.
يمكن إنشاء رسومات بيانية صريحة، رغم أنها كبيرة الحجم وذات مقاس كبير وأرقام لونية، كرسومات توضيحية معينة من Cayley للمجموعات الخطية على الحقول المحدودة . [5] تحتوي هذه الرسوم البيانية المميزة لـ Ramanujan أيضًا على معامل توسع كبير.
المفاهيم ذات الصلة
يمثل طول المحيط الفردي والمحيط الزوجي للرسم البياني أطوال أقصر دورة فردية وأقصر دورة زوجية على التوالي.
محيط الرسم البياني (circumference) هو طول أطول دورة، وليس أقصرها.
يُنظر إلى المقاس على أنه أقصر طول لدورة غير تافهة، وهذا التعريف يوافق التعميمات المعرفة في 1-systole أو أعلى الانقباضات في systolic geometry.
يرتبط مفهوم المقاس بالرسم البياني بخاصية إرتباط الأضلاع ، بمعنى أن مقاس الرسم البياني المستوي هو اتصال أضلاع الرسم البياني المزدوج له والعكس صحيح. يتم توحيد هذه المفاهيم في نظرية matroid وذلك عن طريق تعريف مقاس محيطه وحجم أصغر مجموعة تابعة فيه. بالنسبة إلى matroid الرسومية، فإن مقاس matroid يعادل مقاس الرسم البياني الأساسي، بينما بالنسبة إلى matroid-graph ، فإنه يساوي اتصال أضلاعه. [6]
المراجع
- R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- Girth – Wolfram MathWorld
- Cages . Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
- Graph theory and probability, 1959 .
- Guiliana Davidoff, Peter Sarnak, Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, Cambridge University Press, 2003.
- On the (co)girth of a connected matroid, 2007 .