طوق (نظرية البيان)
{{عن|3=طوق (توضيح)}}
{{لا صندوق معلومات}}
{{يتيمة|تاريخ=أغسطس 2019}}
في [[نظرية البيان]]، '''الطَّوْق'''<ref>{{استشهاد بويكي بيانات|Q108593221|الصفحة=282}}</ref> أو '''الخصر'''<ref>{{استشهاد بويكي بيانات|Q130241879|الصفحة=58}}</ref> {{إنج|Girth}} في رسم بياني هو طول أقصر [[دورة (نظرية الرسومات)|دورة]] فيه.<ref>R. Diestel, ''Graph Theory'', p.8. 3rd Edition, Springer-Verlag, 2005</ref> إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه [[لانهاية|اللانهاية]] .<ref>{{استشهاد|عنوان=Girth – Wolfram MathWorld}}</ref> على سبيل المثال، دورة طولها 4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر [[:en:Triangle-free graph|رسم بدون مثلثات]] .

== أقفاص ==
يُعرف [[:en:Cubic graph|الرسم البياني المكعب]] ( والذي به جميع رؤوسه من الدرجة الثالثة) الذي مقاسه يساوي {{تعبير رياضي|''g''}} باسم [[:en:Cage (graph theory)|قفص]] (cage) بحجم {{تعبير رياضي|''g''}} ( أو قفص من النوع (3، {{تعبير رياضي|''g''}} )).مثال على ذلك [[:en:Petersen graph|الرسم البياني Petersen]] يمثل قفص وحيد بحجم 5 (وهو أصغر رسم بياني مكعب بمقاس 5) . وهنا مثال آخر هو [[:en:Heawood graph|الرسم Heawood]] والذي يعتبر قفص فريد بحجم 6 بينما في [[:en:McGee graph|الرسم McGee]] هو قفص حجمه يساوي 7 . والشكل [[:en:Tutte–Coxeter graph|Tutte]] به قفص بحجم 8.<ref>{{استشهاد|عنوان=Cages}}. Electronic supplement to the book ''Distance-Regular Graphs'' (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).</ref> من الممكن وجودك أقفاص متعددة لنفس المقاس . على سبيل المثال، هنا ثلاثة أقفاص غير متجانسة بحجم 10 وكل منها يحتوي على 70 رأسًا: [[:en:Balaban 10-cage|Balaban 10-cage]] ، والرسم البياني [[:en:Harries–Wong graph|Harries]] والرسم البياني [[:en:Harries–Wong graph|Harries-Wong]] . <gallery>
ملف:Petersen1 tiny.svg|هنا الرسم [[:en:Petersen graph|Petersen]] بمقاس 5.
ملف:Heawood Graph.svg|الشكل يوضح الرسم [[:en:Heawood graph|Heawood]] والذي مقاسه يساوي 6.
ملف:McGee graph.svg|الرسم [[:en:McGee graph|McGee]] والذي المقاس فيه يساوي7.
ملف:Tutte eight cage.svg| الرسم [[:en:Tutte–Coxeter graph|Tutte–Coxeter]] والذي مقاس المحيط فيه يساوي 8.
</gallery>

== المقاس وتلوين الرسم البياني ==
لأي أعداد صحيحة موجبة {{تعبير رياضي|''g''}} و {{تعبير رياضي|χ}} ، يوجد رسم بياني ذو مقاس {{تعبير رياضي|''g''}} على الأقل [[مسألة تلوين المخطط|ورقم لوني]] على الأقل {{تعبير رياضي|χ}} ؛ على سبيل المثال، في الرسم البياني [[:en:Grötzsch graph|Grötzsch]] بدون مثلث ووالذي به العدد اللوني 4 وبتكرار شكل Mycielskian المستخدم فيه، ينتج عنه رسومات بدون لمثلث لها عدد لوني كبير . كان [[بول إيردوش|بول إيردوس]] أول من أثبت هذه النتيجة العامة، باستخدام [[:en:Probabilistic method|الطريقة الاحتمالية]] .<ref>{{استشهاد|عنوان=Graph theory and probability|سنة=1959}}.</ref> بتعبير أدق، أوضح أن رسمًا [[رسم بياني عشوائي|عشوائيًا]] على رؤوس {{تعبير رياضي|''n''}} ، يتشكل باختيار مستقل للأضلاع بحيث كل ضلع يظهر بهذا الرسم باحتمال قدره {{تعبير رياضي|''n''<sup>(1&nbsp;&minus;&nbsp;''g'')/''g''</sup>}} . بالتالي فإن هذا الرسم يحتوي على الأكثر {{تعبير رياضي|''n''/2}} من الدورات بطول {{تعبير رياضي|''g''}} عالأكثر باحتمال يقترب من 1 عندما {{تعبير رياضي|''n''}} تقترب إلى ما لا نهاية . لكن في هذه الحالة فإن هذا الرسم ليس لديه مجموعة مستقلة بحجم {{تعبير رياضي|''n''/2''k''}} . فبالتالي فإن حذف رأس واحد من كل دورة قصيرة قد يؤدي إلى تناقض لكون أقصردوره به المعرف بالمقاس يكون أكبر من {{تعبير رياضي|''g''}} . في حين مطلوب أن تكون كل فئة من ألوان التلوين صغيرة وتتطلب بالتالي ألوان {{تعبير رياضي|''k''}} على الأقل في أي تلوين.

يمكن إنشاء [[مخطط كايلي|رسومات بيانية]] صريحة، رغم أنها كبيرة الحجم وذات مقاس كبير وأرقام لونية، [[مخطط كايلي|كرسومات توضيحية]] معينة من [[مخطط كايلي|Cayley]] للمجموعات الخطية على [[حقل محدود (رياضيات)|الحقول المحدودة]] .<ref>Guiliana Davidoff, Peter Sarnak, Alain Valette, ''Elementary number theory, group theory, and Ramanujan graphs'', Cambridge University Press, 2003.</ref> تحتوي هذه ''الرسوم البيانية المميزة لـ Ramanujan'' أيضًا على معامل توسع كبير.

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

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

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

يرتبط مفهوم المقاس بالرسم البياني بخاصية [[:en:K-edge-connected graph|إرتباط الأضلاع]] ، بمعنى أن مقاس [[مخطط مستو|الرسم البياني المستوي]] هو اتصال أضلاع الرسم البياني المزدوج له والعكس صحيح. يتم توحيد هذه المفاهيم في نظرية [[:en:Matroid|matroid]] وذلك عن طريق تعريف [[:en:Matroid girth|مقاس محيطه]] وحجم أصغر مجموعة تابعة فيه. بالنسبة إلى matroid الرسومية، فإن مقاس matroid يعادل مقاس الرسم البياني الأساسي، بينما بالنسبة إلى matroid-graph ، فإنه يساوي اتصال أضلاعه.<ref>{{استشهاد|عنوان=On the (co)girth of a connected matroid|سنة=2007}}.</ref>

== المراجع ==
{{مراجع}}
{{شريط بوابات|رياضيات|علم الحاسوب}}

[[تصنيف:نظرية البيان]]
في نظرية البيان، الطَّوْق أو الخصر  في رسم بياني هو طول أقصر دورة فيه.R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005 إذا كان الرسم البياني لا يحتوي على أي دورات (أي أنه رسم بياني بدون دوره، فسيتم تعريف المقاس بأنه اللانهاية . على سبيل المثال، دورة طولها 4 (تاخذ شكل المربع) بها مقاس المحيط 4 وقياس محيط المثلث يساوي 4 أيضا، وشبكة الثلاثي لديها حزام 3. فبالتالي أي رسم بياني به طول محيطه يساوي أربعة أو أكثر يعتبر رسم بدون مثلثات .

 أقفاص 
يُعرف الرسم البياني المكعب ( والذي به جميع رؤوسه من الدرجة الثالثة) الذي مقاسه يساوي  باسم قفص (cage) بحجم  ( أو قفص من النوع (3،  )).مثال على ذلك الرسم البياني Petersen يمثل قفص وحيد بحجم 5 (وهو أصغر رسم بياني مكعب بمقاس 5) . وهنا مثال آخر هو الرسم Heawood والذي يعتبر قفص فريد بحجم 6 بينما في الرسم McGee هو قفص حجمه يساوي 7 . والشكل Tutte به قفص بحجم 8.. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag). من الممكن وجودك أقفاص متعددة لنفس المقاس . على سبيل المثال، هنا ثلاثة أقفاص غير متجانسة بحجم 10 وكل منها يحتوي على 70 رأسًا: Balaban 10-cage ، والرسم البياني Harries والرسم البياني Harries-Wong . 

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

يمكن إنشاء رسومات بيانية صريحة، رغم أنها كبيرة الحجم وذات مقاس كبير وأرقام لونية، كرسومات توضيحية معينة من Cayley للمجموعات الخطية على الحقول المحدودة .Guiliana Davidoff, Peter Sarnak, Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, Cambridge University Press, 2003. تحتوي هذه الرسوم البيانية المميزة لـ Ramanujan أيضًا على معامل توسع كبير.

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

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

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

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

 المراجع 

تصنيف:نظرية البيان