المحيط (نظرية الرسم البياني)

في نظرية المخططات ، يُعرف محيط المخطط غير الموجه بطول أقصر دورة فيه. ^{[ 1 ]} إذا لم يحتوي المخطط على أي دورات (أي أنه غابة )، يُعرّف محيطه بأنه ما لا نهاية . ^{[ 2 ]} على سبيل المثال، يبلغ محيط الدورة الرباعية (المربع) 4. كما يبلغ محيط الشبكة 4 أيضًا، ويبلغ محيط الشبكة المثلثية 3. المخطط الذي يبلغ محيطه 4 أو أكثر خالٍ من المثلثات .

يُعرف الرسم البياني المكعب ( جميع رؤوسه من الدرجة الثالثة) ذو المحيط g الذي يكون أصغر ما يمكن باسم قفص g ( أو قفص (3، g ) ). يُعدّ رسم بيترسن البياني القفص الوحيد ذو المحيط 5 (فهو أصغر رسم بياني مكعب ذو محيط 5)، ورسم هيوود البياني القفص الوحيد ذو المحيط 6، ورسم ماكجي البياني القفص الوحيد ذو المحيط 7، وقفص توت ذو المحيط 8 هو القفص الوحيد ذو المحيط 8. ^{[ 3 ]} قد توجد أقفاص متعددة لمحيط معين. على سبيل المثال، هناك ثلاثة أقفاص غير متماثلة ذات محيط 10، كل منها يحتوي على 70 رأسًا: قفص بالابان ذو المحيط 10 ، ورسم هاريس البياني ، ورسم هاريس-وونغ البياني .

• 
  يبلغ محيط الرسم البياني لبيترسن 5
• 
  يبلغ محيط الرسم البياني لهيوود 6
• 
  يبلغ محيط الرسم البياني لماكجي 7
• 
  يبلغ محيط مخطط توت-كوكسيتر ( قفص توت-ثمانية ) 8

لأي عددين صحيحين موجبين g و χ ، يوجد رسم بياني محيطه على الأقل g وعدده اللوني على الأقل χ ؛ على سبيل المثال، رسم غروتزش البياني خالٍ من المثلثات وله عدد لوني 4، وتكرار بناء مايسيلسكي المستخدم لتكوين رسم غروتزش البياني ينتج رسومًا بيانية خالية من المثلثات ذات عدد لوني كبير كيفيًا. كان بول إردوش أول من أثبت النتيجة العامة، باستخدام الطريقة الاحتمالية . ^{[ 4 ]} وبشكل أدق، أظهر أن الرسم البياني العشوائي على n رأسًا، المُشكَّل باختيار ما إذا كان سيتم تضمين كل حافة بشكل مستقل باحتمالية n ^{(1– g )/ g} ، يحتوي، باحتمالية تقترب من 1 عندما يؤول n إلى اللانهاية ، على n / 2 دورة على الأكثر بطول g أو أقل ، ولكنه لا يحتوي على مجموعة مستقلة بحجم n / 2k . لذلك، فإن إزالة رأس واحد من كل دورة قصيرة ينتج عنه رسم بياني أصغر بمحيط أكبر من g ، حيث يجب أن تكون كل فئة لونية من التلوين صغيرة، وبالتالي تتطلب على الأقل k لونًا في أي تلوين.

يمكن إنشاء رسوم بيانية صريحة، وإن كانت كبيرة، ذات محيط كبير وعدد لوني عالٍ، كرسوم بيانية معينة لكايلي للمجموعات الخطية على الحقول المنتهية . ^{[ 5 ]} تتميز رسوم رامانوجان الرائعة هذه أيضًا بمعامل تمدد كبير .

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

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

يُعتبر المحيط أقصر طول لدورة غير تافهة، ويسمح بتعميمات طبيعية مثل الانقباض الأول أو الانقباضات الأعلى في الهندسة الانقباضية .

يُعدّ محيط الرسم البياني مفهومًا مُقابلًا لاتصال الحواف ، بمعنى أن محيط الرسم البياني المستوي هو اتصال حواف الرسم البياني المُقابل له ، والعكس صحيح. يتم توحيد هذين المفهومين في نظرية الماترويد من خلال محيط الماترويد ، وهو حجم أصغر مجموعة تابعة في الماترويد. بالنسبة للماترويد البياني ، يُساوي محيط الماترويد محيط الرسم البياني الأساسي، بينما يُساوي اتصال الحواف بالنسبة للماترويد المُشترك. ^{[ 6 ]}

يمكن حساب محيط الرسم البياني غير الموجه عن طريق إجراء بحث بالعرض أولاً من كل عقدة، مع تعقيد${\displaystyle O(nm)}$أين${\displaystyle n}$يمثل عدد رؤوس الرسم البياني و${\displaystyle m}$يمثل عدد الحواف. ^{[ 7 ]} يتمثل أحد التحسينات العملية في تحديد عمق خوارزمية البحث في العرض أولاً (BFS) بعمق يعتمد على طول أصغر دورة تم اكتشافها حتى الآن. ^{[ 8 ]} توجد خوارزميات أفضل في حالة كون محيط الرسم البياني زوجيًا ^{[ 9 ]} وعندما يكون الرسم البياني مستويًا. ^{[ 10 ]} من حيث الحدود الدنيا، فإن حساب محيط الرسم البياني لا يقل صعوبة عن حل مشكلة إيجاد المثلثات فيه.