نظرية كيرشوف

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 18 صور
الموسوعة الحرة

في مجال نظرية المخططات الرياضية ، تُعرف نظرية كيرشوف، أو نظرية شجرة المصفوفة لكيرشوف، بأنها نظرية تُعنى بعدد الأشجار الممتدة في مخطط بياني . وتنص على أنه يمكن حساب هذا العدد كأي عامل مرافق لمصفوفة لابلاس الخاصة بالمخطط . ويُبين هذا، على وجه الخصوص، إمكانية حساب عدد الأشجار الممتدة من بيانات المخطط في وقت متعدد الحدود . تُعد نظرية كيرشوف تعميمًا لصيغة كايلي التي تُحدد عدد الأشجار الممتدة في مخطط بياني كامل . سُميت النظرية نسبةً إلى عالم الرياضيات الألماني غوستاف كيرشوف ، الذي نشرها عام 1847. ونُشرت ترجمة إنجليزية لبحث كيرشوف عام 1958. [ 1 ]

التعريفات والبيان

ليكن G رسمًا بيانيًا بسيطًا غير موجه . الشجرة الممتدة لـ G هي رسم بياني جزئي من G ، وهي شجرة لها نفس مجموعة رؤوس G. مصفوفة لابلاس L لـ G هي الفرق بين مصفوفة درجات الرسم البياني ( المصفوفة القطرية لدرجات الرؤوس ) ومصفوفة التجاور الخاصة به ( مصفوفة (0,1) تحتوي على 1 في المواضع التي تُقابل الرؤوس المتجاورة، و0 فيما عدا ذلك). يُحسب العامل المرافق لـ L بحذف صف (مثلاً الصف i ) وعمود (مثلاً العمود j ) من L ، ثم حساب محدد المصفوفة الأصغر، وضربها في (-1) i+j .

تنص نظرية كيرشوف على أن عدد الأشجار الممتدة للرسم البياني يساوي أي عامل مرافق لمصفوفة لابلاس الخاصة بالرسم البياني. (وبالتحديد، جميع هذه العوامل المرافقة متساوية).

مثال

يحتوي هذا الرسم البياني على ثماني أشجار ممتدة، موضحة باللون البرتقالي على اليمين. تحسب نظرية المصفوفة-الشجرة عدد الأشجار الممتدة من مصفوفة لابلاس الخاصة بالرسم البياني.

أولاً، قم بإنشاء مصفوفة لابلاس L للرسم البياني الماسي G كمثال (انظر الصورة على اليمين):

ل=[2-1-10-13-1-1-1-13-10-1-12].{\displaystyle L=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right].}

بعد ذلك، أنشئ مصفوفة Q * عن طريق حذف أي صف وأي عمود من Q. على سبيل المثال، يؤدي حذف الصف 1 والعمود 1 إلى

ل*=[3-1-1-13-1-1-12].{\displaystyle L^{\ast }=\left[{\begin{array}{rrr}3&-1&-1\\-1&3&-1\\-1&-1&2\end{array}}\right].}

وأخيرًا، خذ محدد L * ، والذي ينتج عنه 8. عدد الأشجار الممتدة لـ G ، الموضحة على اليمين ، هو أيضًا 8.

مخطط البرهان

(يستند البرهان أدناه إلى صيغة كوشي-بينيه . يمكن إيجاد حجة استقراء أولية لنظرية كيرشوف في الصفحة 654 من كتاب مور (2011). [ 2 ] )

لاحظ أولاً أن مصفوفة لابلاس تتميز بخاصية أن مجموع عناصرها في أي صف وأي عمود يساوي صفرًا. وبالتالي، يمكننا تحويل أي مصفوفة فرعية إلى أي مصفوفة فرعية أخرى عن طريق جمع الصفوف والأعمدة، وتبديلها، وضرب صف أو عمود في -1. ومن ثم، فإن العوامل المرافقة متطابقة حتى الإشارة، ويمكن التحقق من أنها في الواقع لها نفس الإشارة.

سنُبين لاحقًا أن مُحدد المصفوفة الصغرى M 11 هو عدد الأشجار الممتدة. ليكن n عدد رؤوس الرسم البياني، و m عدد حوافه. مصفوفة الوقوع E هي مصفوفة من الرتبة n × m ، ويمكن تعريفها كما يلي: لنفترض أن ( i , j ) هي الحافة رقم k في الرسم البياني، وأن i < j . عندئذٍ ، E <sub>ik</sub> = 1، و E <sub>jk</sub> = -1، وجميع العناصر الأخرى في العمود k تساوي صفرًا (انظر مصفوفة الوقوع الموجهة لفهم مصفوفة الوقوع المُعدلة E ). بالنسبة للمثال السابق (مع n = 4 و m = 5):

هـ=[11000-101100-1-101000-1-1].{\displaystyle E=\left[{\begin{array}{rrrrr}1&1&0&0&0\\-1&0&1&1&0\\0&-1&-1&0&1\\0&0&0&-1&-1\end{array}}\right].}

تذكر أن لابلاس L يمكن تحليله إلى حاصل ضرب مصفوفة الوقوع ومنقولتها ، أي L = EE T. علاوة على ذلك، لنفترض أن F هي المصفوفة E بعد حذف صفها الأول، بحيث يكون FF T = M 11 .

الآن تسمح لنا صيغة كوشي-بينيه بكتابة

المحقق(م11)=∑Sالمحقق(FS)المحقق(FSتي)=∑Sالمحقق(FS)2{\displaystyle \det \left(M_{11}\right)=\sum _{S}\det \left(F_{S}\right)\det \left(F_{S}^{\mathrm {T} }\right)=\sum _{S}\det \left(F_{S}\right)^{2}}

حيث تتراوح S عبر مجموعات جزئية من [ m ] بحجم n − 1، و F<sub> S </sub> تُمثل المصفوفة ( n − 1)×( n − 1) التي أعمدتها هي أعمدة F ذات الفهرس في S. عندئذٍ، تُحدد كل S عدد n − 1 من حواف الرسم البياني الأصلي، ويمكن إثبات أنه إذا كانت هذه الحواف تُشكل شجرة ممتدة، فإن مُحدد F <sub> S</sub> يكون +1 أو -1، وإذا لم تُشكل شجرة ممتدة، فإن المُحدد يكون 0. وبذلك يكتمل البرهان.

حالات خاصة وتعميمات

معادلة كايلي

تُستنتج صيغة كايلي من نظرية كيرشوف كحالة خاصة، حيث أن كل متجه يحتوي على 1 في موضع، و-1 في موضع آخر، و0 في باقي المواضع هو متجه ذاتي لمصفوفة لابلاس للرسم البياني الكامل، وقيمته الذاتية المقابلة هي n . تشكل هذه المتجهات معًا فضاءً ذا بُعد n  − 1، لذا لا توجد قيم ذاتية أخرى غير صفرية.

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

[ن-1-1⋯-1-1ن-1⋯-1⋮⋮⋱⋮-1-1⋯ن-1].{\displaystyle {\begin{bmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{bmatrix}}.}

أي عامل مرافق للمصفوفة أعلاه هو n n −2 ، وهي صيغة كايلي.

صياغة باستخدام القيم الذاتية لمصفوفة لابلاس

يمكن صياغة النظرية بدلالة القيم الذاتية لمصفوفة لابلاس. هذه القيم الذاتية غير سالبة دائمًا، وواحدة منها تساوي صفرًا. بالنسبة لرسم بياني معطى G ذي n رأسًا، ولتكن λ₀ ≤ λ₁ ≤ λ₂ ≤ ... ≤ λₙ₋₁ هي القيم الذاتية لمصفوفة لابلاس الخاصة به . عندئذٍ ، يكون عدد الأشجار الممتدة t ( G ) للرسم البياني G هو   

ت(جي)=1نλ1λ2⋯λن-1.{\displaystyle t(G)={\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}\,.}

نظرية كيرشوف للرسوم البيانية المتعددة

تنطبق نظرية كيرشوف على الرسوم البيانية المتعددة أيضًا؛ ويتم تعديل المصفوفة L على النحو التالي:

  • المدخل q i,j يساوي − m ، حيث m هو عدد الحواف بين i و j ؛
  • عند حساب درجة الرأس، يتم استبعاد جميع الحلقات .

صيغة كايلي للرسم البياني المتعدد الكامل هي m n −1 ( n n −1 −( n −1) n n −2 ) بنفس الطرق المذكورة أعلاه، لأن الرسم البياني البسيط هو رسم بياني متعدد مع m = 1.

تعداد صريح للأشجار الممتدة

يمكن تعزيز نظرية كيرشوف بتغيير تعريف مصفوفة لابلاس. فبدلاً من مجرد عدّ الحواف المنبثقة من كل رأس أو التي تربط زوجًا من الرؤوس، يتم تسمية كل حافة بقيمة غير محددة ، ويكون العنصر ( i , j ) في مصفوفة لابلاس المعدلة هو مجموع القيم غير المحددة المقابلة للحواف بين الرأسين i و j عندما لا يساوي i قيمة j ، والمجموع السالب لجميع القيم غير المحددة المقابلة للحواف المنبثقة من الرأس i عندما يساوي i قيمة j .

إن محدد مصفوفة لابلاس المعدلة، بحذف أي صف أو عمود (كما هو الحال في إيجاد عدد الأشجار الممتدة من مصفوفة لابلاس الأصلية)، هو متعدد حدود متجانس (متعدد حدود كيرشوف) في المجاهيل التي تُمثل حواف الرسم البياني. بعد تجميع الحدود وإجراء جميع عمليات الحذف الممكنة، يُمثل كل حد أحادي في التعبير الناتج شجرة ممتدة تتكون من الحواف التي تُمثل المجاهيل الظاهرة في ذلك الحد الأحادي. وبهذه الطريقة، يُمكن الحصول على تعداد صريح لجميع الأشجار الممتدة للرسم البياني ببساطة عن طريق حساب المحدد.

للاطلاع على برهان هذه النسخة من النظرية، انظر بولوباس (1998). [ 3 ]

ماترويدز

تشكل الأشجار الممتدة للرسم البياني قواعد الماترويد الرسومي ، لذا توفر نظرية كيرشوف صيغةً لعدد القواعد في الماترويد الرسومي. ويمكن استخدام الطريقة نفسها لتحديد عدد القواعد في الماترويدات المنتظمة ، وهي تعميم للماترويدات الرسومية ( ماورر، 1976 ) .

نظرية كيرشوف للرسوم البيانية المتعددة الموجهة

يمكن تعديل نظرية كيرشوف لإيجاد عدد الأشجار الممتدة الموجهة في الرسوم البيانية المتعددة الموجهة. يتم إنشاء المصفوفة Q على النحو التالي:

  • المدخل q i,j لـ i و j المختلفين يساوي − m ، حيث m هو عدد الحواف من i إلى j ؛
  • المدخل q i,i يساوي درجة الدخول لـ i مطروحًا منها عدد الحلقات عند i .

عدد الأشجار الممتدة الموجهة التي جذرها رأس i هو محدد المصفوفة التي يتم الحصول عليها عن طريق إزالة الصف والعمود i من Q

عد الغابات الممتدة ذات المكونات k

يمكن تعميم نظرية كيرشوف لحساب الغابات الممتدة ذات k مكون في رسم بياني غير مُثقَّل. [ 4 ] الغابة الممتدة ذات k مكون هي رسم بياني فرعي يحتوي على k مكون متصل ، ويضم جميع الرؤوس، وهو خالٍ من الدورات، أي يوجد مسار واحد على الأكثر بين كل زوج من الرؤوس. بفرض وجود غابة F ذات مكونات متصلةF1،...،Fك{\textstyle F_{1},\dots ,F_{k}}حدد وزنهw(F)=|V(F1)|⋅⋯⋅|V(Fك)|{\textstyle w(F)=|V(F_{1})|\cdot \dots \cdot |V(F_{k})|}ليكون حاصل ضرب عدد الرؤوس في كل مكون. ثم

∑Fw(F)=qك،{\displaystyle \sum _{F}w(F)=q_{k},}

حيث يكون المجموع على جميع الغابات الممتدة ذات المكونات k وqك{\textstyle q_{k}}هو معاملxك{\textstyle x^{k}}من متعدد الحدود

(x+λ1)...(x+λن-1)x.{\displaystyle (x+\lambda _{1})\dots (x+\lambda _{n-1})x.}

العامل الأخير في متعددة الحدود يعود إلى القيمة الذاتية الصفريةλن=0{\textstyle \lambda _{n}=0}وبشكل أكثر تحديداً، العددqك{\textstyle q_{k}}يمكن حسابها على النحو التالي

qك=∑{أنا1،...،أنان-ك}⊂{1...ن-1}λأنا1...λأنان-ك.{\displaystyle q_{k}=\sum _{\{i_{1},\dots ,i_{n-k}\}\subset \{1\dots n-1\}}\lambda _{i_{1}}\dots \lambda _{i_{n-k}}.}

حيث يكون المجموع على جميع المجموعات الفرعية المكونة من ( ن  - ك ) عنصرًا من {1،...،ن}{\textstyle \{1,\dots ,n\}}. على سبيل المثال

qن-1=λ1+⋯+λن-1=tr⁡سؤال=2|هـ|qن-2=λ1λ2+λ1λ3+⋯+λن-2λن-1q2=λ1...λن-2+λ1...λن-3λن-1+⋯+λ2...λن-1q1=λ1...λن-1{\displaystyle {\begin{aligned}q_{n-1}&=\lambda _{1}+\dots +\lambda _{n-1}=\operatorname {tr} Q=2|E|\\q_{n-2}&=\lambda _{1}\lambda _{2}+\lambda _{1}\lambda _{3}+\dots +\lambda _{n-2}\lambda _{n-1}\\q_{2}&=\lambda _{1}\dots \lambda _{n-2}+\lambda _{1}\dots \lambda _{n-3}\lambda _{n-1}+\dots +\lambda _{2}\dots \lambda _{n-1}\\q_{1}&=\lambda _{1}\dots \lambda _{n-1}\end{aligned}}}

بما أن الغابة الممتدة ذات n − 1 مكونًا تُقابل حافة واحدة، فإن الحالة k = n  −  1 تنص على أن مجموع القيم الذاتية للمصفوفة Q يساوي ضعف عدد الحواف. أما الحالة k = 1 فتتوافق مع نظرية كيرشوف الأصلية، حيث أن وزن كل شجرة ممتدة هو n . 

يمكن إجراء البرهان بشكل مماثل لبرهان نظرية كيرشوف.(ن-ك)×(ن-ك){\displaystyle (n-k)\times (n-k)}المصفوفة الفرعية لمصفوفة الحدوث تتوافق بشكل تقابلي مع غابة ممتدة مكونة من k عنصر مع اختيار رأس لكل عنصر.

المعاملاتqك{\textstyle q_{k}}تصل إلى إشارة معاملات متعددة الحدود المميزة لـ Q.

انظر أيضاً

مراجع

  1. ↑ أوتول، ج. ب. (1958). "حول حل المعادلات المستنتجة من دراسة التوزيع الخطي للتيارات الجلفانية". معاملات معهد مهندسي الكهرباء والإلكترونيات في نظرية الدوائر . 5 (1): 4-7 . doi : 10.1109/TCT.1958.1086426 .
  2. ↑ مور، كريستوفر (2011). طبيعة الحوسبة . أكسفورد، إنجلترا - نيويورك: مطبعة جامعة أكسفورد. ISBN 978-0-19-923321-2. OCLC 180753706 . 
  3. ↑ بولوباس، بيلا (1998). نظرية الرسم البياني الحديثة . نصوص الدراسات العليا في الرياضيات. المجلد 184. نيويورك: سبرينغر. doi : 10.1007/978-1-4612-0619-4 . ISBN  978-0-387-98488-9.
  4. ↑ بيغز، ن. (1993). نظرية الرسم البياني الجبرية . مطبعة جامعة كامبريدج.
  • هاريس، جون م.؛ هيرست، جيفري ل.؛ موسينغهوف، مايكل ج. (2008)، التوافقية ونظرية الرسوم البيانية ، نصوص جامعية في الرياضيات (  الطبعة الثانية)، سبرينغر.
  • ماورر، ستيفن ب. (1976)، "تعميمات المصفوفات لبعض النظريات حول الأشجار والدورات والدورات المشتركة في الرسوم البيانية"، مجلة SIAM للرياضيات التطبيقية ، 30 (1): 143-148 ، doi : 10.1137/0130017 ، MR 0392635 .
  • توتي، دبليو تي (2001)، نظرية الرسم البياني ، مطبعة جامعة كامبريدج، ص  138، رقم ISBN 978-0-521-79489-3.
  • تشايكن، س.؛ كليتمان، د. (1978)، "نظريات شجرة المصفوفة"، مجلة نظرية التوافيق، السلسلة أ ، 24 (3): 377-381 ، doi : 10.1016/0097-3165(78)90067-5 ، ISSN 0097-3165