ثابت شيغر (نظرية الرسم البياني)

في الرياضيات ، يُعدّ ثابت شيغر (أو عدد شيغر أو العدد المحيطي المتساوي ) للرسم البياني مقياسًا عدديًا يُحدد ما إذا كان الرسم البياني يحتوي على "عنق زجاجة" أم لا. ويُعتبر ثابت شيغر، كمقياس لـ"عنق الزجاجة"، ذا أهمية بالغة في العديد من المجالات، مثل بناء شبكات حاسوبية مترابطة جيدًا ، وخلط أوراق اللعب . وقد نشأ مفهوم نظرية الرسم البياني بعد ثابت شيغر المحيطي المتساوي لمتشعب ريماني مضغوط .

سُمّي ثابت شيغر تيمناً بعالم الرياضيات جيف شيغر .

ليكن G رسمًا بيانيًا محدودًا غير موجه، بمجموعة رؤوس V ( G ) ومجموعة حواف E ( G ) . بالنسبة لمجموعة من الرؤوس A ⊆ V ( G ) ، لنرمز بـ ∂A إلى مجموعة جميع الحواف التي تصل من رأس في A إلى رأس خارج A (يُسمى أحيانًا حدود حواف A ) :

${\displaystyle \partial A:=\{\{x,y\}\in E(G)\$ :\ x\in A,y\in V(G)\setminus A\}.}

لاحظ أن الحواف غير مرتبة، أي${\displaystyle \{x,y\}=\{y,x\}}$يتم تعريف ثابت شيجر لـ G ، والذي يرمز له بـ h ( G ) ، بواسطة ^{[ 1 ]}

${\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\$ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}

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

في تطبيقات علوم الحاسوب النظرية، يرغب المرء في تصميم تكوينات الشبكة التي يكون فيها ثابت شيجر عاليًا (على الأقل، محدودًا بعيدًا عن الصفر) حتى عندما يكون | V ( G )| (عدد أجهزة الكمبيوتر في الشبكة) كبيرًا.

على سبيل المثال، لنفترض شبكة حلقية مكونة من N ≥ 3 أجهزة كمبيوتر، يمكن تمثيلها بيانيًا G ∈ _N. قم بترقيم أجهزة الكمبيوتر من 1 إلى N باتجاه عقارب الساعة حول الحلقة. رياضيًا، تُعطى مجموعة الرؤوس ومجموعة الحواف كما يلي:

${\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}$

لنفترض أن A عبارة عن مجموعة من${\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }$من هذه الحواسيب في سلسلة متصلة:

${\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}$

لذا،

${\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}$

و

${\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .}$

يُقدّم هذا المثال حدًا أعلى لثابت شيغر h ( GN ) ، الذي يؤول أيضًا إلى الصفر عندما N → ∞ . ونتيجةً لذلك، نعتبر الشبكة الحلقية "مُختنقة" للغاية عند قيم N الكبيرة _، وهذا أمر غير مرغوب فيه عمليًا. يكفي أن يتعطل جهاز حاسوب واحد فقط على الحلقة ليتراجع أداء الشبكة بشكل كبير. أما إذا تعطل جهازان غير متجاورين، فستنقسم الشبكة إلى مُكوّنين منفصلين.

يُعدّ ثابت شيغر ذا أهمية خاصة في سياق الرسوم البيانية المتوسعة، إذ يُستخدم لقياس توسع حواف الرسم البياني. وتربط ما يُسمى بمتباينات شيغر فجوة القيم الذاتية للرسم البياني بثابت شيغر الخاص به. وبشكل أكثر تحديدًا، بالنسبة لـ${\displaystyle G\neq K_{1},K_{2},K_{3}}$لدينا

${\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}$

في أي${\displaystyle \Delta (G)}$يمثل الحد الأقصى لدرجة العقد في${\displaystyle G}$و${\displaystyle \lambda }$^{[ 2} ] تمثل الفجوة الطيفية لمصفوفة لابلاس للرسم البياني. ^{[ 2 ]} تُعدّ متباينة شيغر نتيجة أساسية ودافعًا لنظرية الرسم البياني الطيفية .

• نظرية الرسم البياني الطيفي
• الاتصال الجبري
• متجه إلى شيجر
• تصرف
• الاتصال
• رسم بياني موسع