رقم سيكلو

الموسوعة الحرة
يحتوي هذا الرسم البياني على عدد حلقي r = 2 لأنه يمكن تحويله إلى شجرة عن طريق إزالة حافتين، على سبيل المثال الحافتين 1-2 و2-3، ولكن إزالة أي حافة واحدة تترك دورة في الرسم البياني.

في نظرية الرسم البياني ، وهي فرع من فروع الرياضيات ، فإن العدد الحلقي ، أو رتبة الدائرة ، أو رتبة الدورة ، أو الرتبة المشتركة ، أو العدمية للرسم البياني غير الموجه هو الحد الأدنى لعدد الحواف التي يجب إزالتها من الرسم البياني لكسر جميع دوراته ، مما يجعله شجرة أو غابة .

تم تقديم هذا المفهوم وأطلق عليه اسم العدد الحلقي بواسطة غوستاف كيرشوف . [ 1 ] [ 2 ]

صيغة

يُساوي العدد الحلقي للرسم البياني عدد الدورات المستقلة فيه، وهو حجم أساس الدورة . وعلى عكس مسألة مجموعة أقواس التغذية الراجعة المقابلة للرسوم البيانية الموجهة ، يُمكن حساب العدد الحلقي r بسهولة باستخدام الصيغة التالية: ر=هـ-v+ج،{\displaystyle r=e-v+c,} حيث يمثل e عدد الحواف في الرسم البياني المعطى، و v عدد الرؤوس ، و c عدد المكونات المتصلة . [ 3 ]

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

يمكن تفسير العدد الحلقي من منظور نظرية الرسم البياني الجبرية باعتباره بُعد فضاء الدورات في الرسم البياني، ومن منظور نظرية الماترويد باعتباره الرتبة الثنائية للماترويد الرسومي الخاص به ، ومن منظور الطوبولوجيا باعتباره أحد أعداد بيتي لفضاء طوبولوجي مُشتق من الرسم البياني. وهو يحسب عدد الآذان في تجزئة الآذان للرسم البياني، ويُشكل أساس التعقيد المُعامل على الأشجار شبه الكاملة، وقد طُبِّق في مقاييس البرمجيات كجزء من تعريف التعقيد الحلقي لجزء من التعليمات البرمجية.

بالنسبة للرسوم البيانية الفائقة

يمكن اشتقاق العدد الحلقي للرسم البياني الفائق من خلال رسم ليفي الخاص به ، والذي له نفس العدد الحلقي ولكنه مُختزل إلى رسم بياني بسيط. ر=ز-(v+هـ)+ج،{\displaystyle r=g-(v+e)+c,} حيث g هو مجموع الدرجات (وعدد الحواف في الرسم البياني ليفي)، و e هو عدد الحواف الفائقة في الرسم البياني الفائق المعطى، و v هو عدد الرؤوس ، و c هو عدد المكونات المتصلة .

مجموع درجات الرسم البياني الفائق هو مجموع درجات جميع رؤوسه، ويُختزل إلى 2e للرسم البياني البسيط، أو ke للرسم البياني الفائق المنتظم من الرتبة k . هذه الصيغة متناظرة بين الرؤوس والحواف ، مما يدل على أن الرسم البياني الفائق ورسمه البياني الفائق الثنائي لهما نفس العدد الحلقي.

رتبة الماترويد وبناء مجموعة حواف التغذية الراجعة الدنيا

يمكن وصف العدد الحلقي للرسم البياني G باستخدام نظرية الماترويد باعتباره الرتبة المزدوجة للماترويد الرسومي لـ G. [ 4 ] باستخدام خاصية الجشع للماترويدات، هذا يعني أنه يمكن إيجاد مجموعة دنيا من الحواف التي تكسر جميع الحلقات باستخدام خوارزمية جشعة تختار في كل خطوة حافة تنتمي إلى حلقة واحدة على الأقل من الرسم البياني المتبقي.

بدلاً من ذلك، يمكن إيجاد مجموعة دنيا من الحواف التي تكسر جميع الدورات عن طريق إنشاء غابة قصوى لـ G واختيار المجموعة التكميلية من الحواف التي لا تنتمي إلى الغابة القصوى.

عدد الدورات المستقلة

في نظرية الرسم البياني الجبرية ، يُعد العدد الحلقي أيضًا بُعد فضاء الدورة لـجي{\displaystyle G}يمكن تفسير ذلك بشكل بديهي على أنه يعني أن العدد الحلقي يحسب عدد الدورات المستقلة في الرسم البياني، حيث تكون مجموعة من الدورات مستقلة إذا لم يكن من الممكن تكوين إحدى الدورات كفرق متناظر لمجموعة جزئية من الدورات الأخرى. [ 3 ]

يمكن تفسير هذا العدد من الدورات المستقلة باستخدام نظرية التماثل ، وهي فرع من فروع علم الطوبولوجيا. يمكن اعتبار أي رسم بياني G مثالًا على مُركَّب تبسيطي أحادي البُعد ، وهو نوع من الفضاء الطوبولوجي يتكون من تمثيل كل حافة من حواف الرسم البياني بقطعة مستقيمة ولصق هذه القطع معًا عند نقاط نهايتها. يُعرف العدد الحلقي بأنه رتبة مجموعة التماثل الأولى ( الصحيحة ) لهذا المُركَّب، [ 5 ]ر=رتبة⁡[ح1(جي،Z)].{\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].}بسبب هذا الارتباط الطوبولوجي، يُطلق على العدد الحلقي للرسم البياني G أيضًا اسم عدد بيتي الأول لـ G. [ 6 ] وبشكل أعم، فإن عدد بيتي الأول لأي فضاء طوبولوجي ، المعرف بنفس الطريقة، يحسب عدد الدورات المستقلة في الفضاء.

التطبيقات

معامل التشابك

يُطلق على أحد أشكال العدد الحلقي للرسوم البيانية المستوية ، بعد تطبيعه بقسمته على أكبر عدد حلقي ممكن لأي رسم بياني مستوٍ له نفس مجموعة الرؤوس، اسم معامل التشابك . بالنسبة لرسم بياني مستوٍ متصل ذي m حافة و n رأس، يمكن حساب معامل التشابك باستخدام الصيغة [ 7 ].

م-ن+12ن-5.{\displaystyle {\frac {m-n+1}{2n-5}}.}

هنا، البسطم-ن+1{\displaystyle m-n+1}يمثل الجزء من الصيغة العدد الحلقي للرسم البياني المعطى، والمقام2ن-5{\displaystyle 2n-5}يمثل أكبر عدد حلقي ممكن في رسم بياني مستوٍ ذي n رأس. ويتراوح معامل التشابك بين 0 للأشجار و1 للرسوم البيانية المستوية القصوى .

تحلل الأذن

يتحكم العدد الحلقي في عدد الآذان في تجزئة الأذن للرسم البياني، وهي تقسيم لحواف الرسم البياني إلى مسارات ودورات، وهو تقسيم مفيد في العديد من خوارزميات الرسوم البيانية. على وجه الخصوص، يكون الرسم البياني متصلًا برأسين إذا وفقط إذا كان له تجزئة أذن مفتوحة. هذه التجزئة عبارة عن سلسلة من الرسوم البيانية الفرعية، حيث يكون الرسم البياني الفرعي الأول دورة بسيطة، والرسوم البيانية الفرعية المتبقية كلها مسارات بسيطة، ويبدأ كل مسار وينتهي عند رؤوس تنتمي إلى الرسوم البيانية الفرعية السابقة، ويظهر كل رأس داخلي للمسار لأول مرة في ذلك المسار. في أي رسم بياني ثنائي الاتصال برتبة دائرةر{\displaystyle r}كل عملية تحلل للأذن المفتوحة لها بالضبطر{\displaystyle r}آذان. [ 8 ]

شبه الأشجار

رسم بياني ذو عدد حلقير{\displaystyle r}يُطلق عليها أيضًا اسم " شجرة شبه- r" ، لأنه لا يلزم سوى إزالة r من الحواف من الرسم البياني لتحويله إلى شجرة أو غابة. تُسمى الشجرة شبه-1 شجرة قريبة ، والشجرة القريبة المتصلة هي شجرة زائفة ، وهي عبارة عن دورة ذات شجرة (قد تكون تافهة) متجذرة عند كل رأس. [ 9 ]

قام العديد من المؤلفين بدراسة التعقيد المُعَلم لخوارزميات الرسم البياني على الأشجار القريبة من الرتبة r ، والمُعَلم بواسطةر{\displaystyle r}[ 10 ] [ 11 ]​

تعميمات على الرسوم البيانية الموجهة

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

من الممكن أيضًا حساب ثابت أبسط للرسوم البيانية الموجهة بتجاهل اتجاهات الحواف وحساب رتبة الدائرة للرسم البياني غير الموجه الأساسي. يشكل هذا المبدأ أساس تعريف التعقيد الحلقي ، وهو مقياس برمجي لتقدير مدى تعقيد جزء من شفرة الحاسوب.

الكيمياء الحاسوبية

في مجالي الكيمياء والمعلوماتية الكيميائية ، يُشار أحيانًا إلى العدد الحلقي للرسم البياني الجزيئي (عدد الحلقات في أصغر مجموعة من أصغر الحلقات ) باسم عدد فريجاك . [ 12 ] [ 13 ] [ 14 ]

التعقيد المُعَلم

بعض المسائل الحسابية المتعلقة بالرسوم البيانية تُصنف عمومًا ضمن المسائل الصعبة من نوع NP، ولكن يمكن حلها في وقت متعدد الحدود للرسوم البيانية ذات العدد الحلقي الصغير. ومن الأمثلة على ذلك مسألة إعادة تشكيل المسار. [ 15 ]

الأرقام الأخرى المحددة من حيث حذف العناصر من الرسوم البيانية هي:

مراجع

  1. ↑ بيتر روبرت كوتيوجا (2010)، احتفاء بالإرث الرياضي لراؤول بوت ، الجمعية الرياضية الأمريكية، ص  20، ISBN 978-0-8218-8381-5
  2. ↑ بير هاج (1996)، شبكات الجزر: التواصل، والقرابة، وهياكل التصنيف في أوقيانوسيا ، مطبعة جامعة كامبريدج، ص 48، ISBN  978-0-521-55232-5
  3. 1 2 بيرج، كلود (2001)، "العدد الحلقي"، نظرية الرسوم البيانية ، منشورات كوريير دوفر، ص 27-30 ، ISBN  9780486419756.
  4. ↑ بيرج، كلود (1976)، الرسوم البيانية والرسوم البيانية الفائقة ، مكتبة شمال هولندا الرياضية، المجلد 6، إلسيفير، ص 477، ISBN   9780720424539.
  5. ↑ سير، جان بيير (2003)، الأشجار ، سلسلة دراسات سبرينغر في الرياضيات، سبرينغر، ص 23، ISBN  9783540442370.
  6. ↑ غريغوري بيركولايكو؛ بيتر كوشمنت (2013)، مقدمة في الرسوم البيانية الكمومية ، الجمعية الرياضية الأمريكية، ص 4، ISBN  978-0-8218-9211-4
  7. ↑ بوهل، ج.؛ غوترايس، ج.؛ سول، ر. ف.؛ كونتز، ب.؛ فالفيردي، س.؛ دينوبورغ، ج. ل.؛ ثيراولاز، ج. (2004)، "الكفاءة والمتانة في شبكات النمل للمعارض"، المجلة الأوروبية للفيزياء ب ، 42 (1)، سبرينغر-فيرلاغ: 123-129 ، رمز Bibcode : 2004EPJB...42..123B ، doi : 10.1140/epjb/e2004-00364-9.
  8. ↑ ويتني، هـ. (1932)، "الرسوم البيانية غير القابلة للفصل والمستوية"، معاملات الجمعية الرياضية الأمريكية ، 34 (2): 339-362 ، doi : 10.2307/1989545 ، JSTOR 1989545 ، PMC 1076008 ، PMID 16587624   انظر على وجه الخصوص النظريتين 18 (التي تربط تجزئة الأذن برتبة الدائرة) و19 (حول وجود تجزئة الأذن).
  9. ↑ بروالدي، ريتشارد أ. (2006)، فئات المصفوفات التوافقية ، موسوعة الرياضيات وتطبيقاتها، المجلد 108، كامبريدج: مطبعة جامعة كامبريدج ، ص 349 ، ISBN   0-521-86565-4Zbl 1106.05001​ 
  10. ↑ كوبرسميث، دون ؛ فيشكين، أوزي (1985)، "حل مسائل NP-صعبة في 'شبه الأشجار': غطاء الرأس"، الرياضيات التطبيقية المنفصلة ، ​​10 (1): 27-45 ، doi : 10.1016/0166-218X(85)90057-5 ، Zbl 0573.68017 .
  11. ^ فيالا، جيري؛ كلوكس، طن؛ Kratochvíl، Jan (2001)، “تعقيد المعلمات الثابتة للتسميات ″، الرياضيات التطبيقية المنفصلة ، 113 (1): 59–72 ، دوى : 10.1016 / S0166-218X(00)00387-5 ، Zbl 0982.05085 .
  12. ↑ ماي، جون دبليو؛ شتاينبك، كريستوف (2014)، "إدراك الحلقة بكفاءة لمجموعة أدوات تطوير الكيمياء"، مجلة المعلوماتية الكيميائية ، 6 (3): 3، doi : 10.1186/1758-2946-6-3 ، PMC 3922685 ، PMID 24479757  
  13. ↑ داونز، جي إم؛ جيليه، في جيه؛ هوليداي، جي دي؛ لينش، إم إف (1989)، "مراجعة لخوارزميات إدراك الحلقة للرسوم البيانية الكيميائية "، مجلة المعلومات الكيميائية وعلوم الحاسوب ، 29 (3): 172-187 ، doi : 10.1021/ci00063a007
  14. ^ فريجاك، مارسيل (1939)، “رقم 108-تكثيف الجزيء العضوي” [ تكثيف الجزيء العضوي ] ، Bull. شركة نفط الجنوب. شيم. الأب. ، 5 : 1008 – 1011
  15. ↑ ديمين، إريك د .؛ إبستين، ديفيد ؛ هيستربيرج، آدم؛ جاين، كشيتيج؛ لوبيو، آنا ؛ أوهارا، ريوهي؛ أونو، يوشي (2019)، "إعادة تشكيل المسارات غير الموجهة"، في فريجستاد، زاكاري؛ ساك، يورج-روديجير ؛ سالافاتيبور، محمد ر. (محررون)، الخوارزميات وهياكل البيانات - الندوة الدولية السادسة عشرة، WADS 2019، إدمونتون، ألبرتا، كندا، 5-7 أغسطس 2019، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد. 11646، سبرينغر، الصفحات 353-365 ، arXiv : 1905.00518 ، doi : 10.1007/978-3-030-24766-9_26 ، ISBN   978-3-030-24765-2