مبرهنة الشجرة والمصفوفة: لماذا لا نعيد حساب الدرجات بعد حذف الصف؟

الخلاصة السريعة

لأن حذف الصف والعمود عملية على المصفوفة الأصلية، لا طلب لبناء مصفوفة جديدة للرسم بعد حذف رأس. في مثالنا C درجته 4 قبل الحذف؛ يبقى العدد 4 في المصفوفة المختزلة، فيعطي محددها 8 أشجار ممتدة. إعادة الدرجة إلى 3 تعطي مصفوفة لابلاس كاملة لرسم آخر، ومحددها صفر لا عدد أشجارها.

• الشجرة الممتدة تربط الرؤوس المحددة كلها بلا دورة. على خمسة رؤوس تحتاج إلى أربع حواف؛ لا يكفي اختيار أربع حواف إذا تركت رأسًا معزولًا. [3]
• رسمنا حوافه AB وBC وCD وAD وAC وCE. كل شجرة فيه تستعمل CE لأنها الوصلة الوحيدة للرأس E، ولدينا 8 مجموعات حواف صالحة مختلفة.
• مصفوفة لابلاس تضع الدرجة على القطر، و−1 بين رأسين متجاورين، وصفرًا بين غير المتجاورين. [2] درجات A وB وC وD وE هنا (3,2,4,2,1).
• نحذف صف E وعموده، ونبقي درجات المصفوفة الأصلية. المحدد 8 يساوي عدد الأشجار الممتدة. [1] حذف صف A وعموده بدلًا منه يعطي 8 أيضًا.
• إذا حذفنا E من الرسم نفسه، تصير درجة C ثلاثة. المصفوفة الكاملة لهذا الرسم الجديد لها مجموع صفوف صفر، ومحددها صفر، مع أن للرسم الجديد 8 أشجار ممتدة.
• الدورة مع جسرها CE لها 4 أشجار؛ إضافة AC تجعلها 8. المثلث مع جسرين له 3، وإضافة رأس معزول إلى رسم آخر تمنع شجرة تمتد الرؤوس الخمسة. لا نختار أقل وزن هنا.

نعد مجموعات حواف تربط الرؤوس كلها

نثبت خمسة رؤوس مختلفة A وB وC وD وE. الرسم بسيط غير موجه وبلا أوزان، وحوافه النهائية AB وBC وCD وAD وAC وCE. AB هي نفسها BA؛ لا نعدها مرتين ولا نضيف حواف من تقاطعات الصورة.

الشجرة الممتدة مجموعة من n−1 حافة تشكل شجرة على الرؤوس المحددة. [3] معناها في مثالنا أربع حواف تصل الرؤوس الخمسة بلا دورة. لا نسمح بنسيان E لمجرد أن الرسم على الأربعة الأخرى يبدو متصلًا.

CE جسر في الرسم: حذفها يعزل E لأن هذا الرأس لا يملك وصلة أخرى. لذلك تدخل CE في كل شجرة ممتدة. يبقى اختيار ثلاث حواف تصل A وB وC وD بلا دورة من الحواف الخمس الموجودة بينها.

نعد مجموعات الحواف المختلفة، لا ترتيب قراءتها أو نقطة بدء السير فيها. المجموعة AB BC CD CE هي شجرة واحدة، سواء سردنا CE أولًا أو آخرًا. ولا نعد تغيير مكان دائرة في الصورة شجرة جديدة. نرمز إلى عدد الأشجار الممتدة بالرمز τ، كما في الصورة الرئيسية.

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

ابن مصفوفة لابلاس قبل أي حذف

تكتب مصفوفة لابلاس L=D−A، حيث D مصفوفة الدرجات القطرية وA مصفوفة التجاور. على القطر درجة الرأس؛ وخارجه −1 للاتصال وصفر لغيابه في الرسم البسيط غير الموجه. [2] سنثبت ترتيب الرؤوس A B C D E للمصفوفة كلها.

عند A نجد AB وAD وAC، فدرجته 3. عند B نجد AB وBC فدرجته 2. عند C نجد BC وCD وAC وCE فدرجته 4. وعند D درجته 2، وعند E درجته 1. إذن القطر هو (3,2,4,2,1).

صف C هو (−1,−1,4,−1,−1): أربع وصلات إلى A وB وD وE، ولذلك يجمع الصف إلى صفر. صف E هو (0,0,−1,0,1)، لأن CE وحدها موجودة. أسماء الصفوف والأعمدة تضمن ألا نضع الدرجة في موضع رأس آخر.

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

مجموع كل صف من المصفوفة الكاملة صفر: الدرجة تقابل عدد خانات −1. لذلك ضربها في المتجه (1,1,1,1,1) يعطي المتجه الصفري؛ الأعمدة تعتمد خطيًا ومحدد L الكامل صفر. هذا الحساب لا ينفي اتصال الرسم أو وجود أشجار ممتدة.

احذف صف E وعموده واحتفظ بالعدد 4

في العامل المرافق القطري نزيل صفًا والعمود ذي الاسم نفسه من المصفوفة. مبرهنة الشجرة والمصفوفة تجعل قيمة هذا العامل عدد الأشجار الممتدة. [1] مع الحذف القطري إشارة العامل موجبة؛ لا ننقل القاعدة إلى حذف صف وعمود مختلفين دون مراعاة الإشارة.

بعد حذف صف E وعموده، يبقى ترتيب A B C D. صف C المختزل هو (−1,−1,4,−1)، لا (−1,−1,3,−1). اختفت خانة اتصال C بـE من المصفوفة، لكن خانة الدرجة 4 لم تطلب عملية الحذف تغييرها.

نسمي المصفوفة المختزلة L_E. صفوفها مبينة في الجدول. صف C يجمع إلى 1، وبقية الصفوف إلى صفر؛ لذلك لا يجوز استعمال حجة مجموع جميع الصفوف صفر لإعلان أن المحدد المختزل يساوي صفرًا.

بتوسيع المحدد على الصف الأول نجد 3×12−10−8−10=8. مقادير المحددات الصغيرة قبل تطبيق معاملات الصف هي 12 و−10 و8 و−10. يمكن التحقق منها بتوسيع محددات ثلاثة في ثلاثة؛ النتيجة هنا عدد صحيح موجب لا قيمة مقربة.

حذف صف A وعموده من L الأصلية يعطي أيضًا 8، وكذلك حذف أي اسم قطري من الأسماء الخمسة. اختيار E مريح لأنه رأس طرفي، ولا يعني أننا نعد أشجارًا تمتد أربعة رؤوس فقط أو نسمح بترك E خارج الشجرة.

راجع الأشجار الثماني مباشرة

بين A وB وC وD توجد الحواف AB وBC وCD وAD وAC. مع CE الإلزامية، نجرب مجموعات الحواف الثلاث من هذه الخمس؛ عددها 10. ثمانٍ تصل الرؤوس الأربعة بلا دورة، ونضيف CE لكل واحدة فتصل الرؤوس الخمسة.

أول أربع خيارات تأتي من الدورة AB وBC وCD وAD: احذف حافة واحدة منها ثم أضف CE. تحصل على AB BC CD CE، أو AD BC CD CE، أو AB AD CD CE، أو AB AD BC CE. كل مجموعة طريق على الأربعة مع الفرع المؤدي إلى E.

وتأتي أربع خيارات أخرى تستعمل AC: AB AC CD CE، وAB AC AD CE، وAC BC CD CE، وAC AD BC CE. القوائم مختلفة، وفي كل منها توجد ثلاث حواف متصلة على الأربعة دون دورة قبل إضافة CE.

أما AB BC AC فتشكل مثلث ABC وتترك D خارجها. والمجموعة AC AD CD تشكل مثلث ACD وتترك B خارجها. إضافة CE لا تعالج العزل في أي منهما؛ لذلك لا تدخلان في العدد 8.

لو جربنا مباشرة جميع مجموعات الأربع من الحواف الست، لوجدنا 15 مجموعة. الثماني السابقة صالحة، والسبع الأخرى تفشل الاتصال؛ خمس منها لا تستعمل CE، واثنتان تستعملانها مع أحد المثلثين. توافق هذا الحصر مع محدد L_E يراجع المثال بطريقتين مستقلتين.

إعادة الدرجة إلى 3 تغير المصفوفة والمسألة

احذف E من الرسم نفسه مع حافته CE. بقيت الحواف AB وBC وCD وAD وAC على A وB وC وD. انخفضت درجة C من 4 إلى 3، بينما بقيت درجات الآخرين كما كانت. هذه عملية حذف رأس من رسم، وتستحق بناء مصفوفة لابلاس جديدة.

صف C في المصفوفة الجديدة هو (−1,−1,3,−1)، فيجمع إلى صفر. كل صف يجمع الآن إلى صفر؛ محدد هذه المصفوفة الكاملة صفر. إذن الفرق عن L_E الأصلية هو خانة واحدة على القطر، لكنها تغير المحدد من 8 إلى صفر.

لا يعني الصفر أن الرسم الجديد بلا أشجار؛ الحواف الخمس على الأربعة لها 8 أشجار ممتدة من ثلاث حواف، كما حصرنا في القسم السابق. للحصول على عددها بالمبرهنة نختزل مصفوفتها الجديدة مرة أخرى بحذف صف وعموده، بدل أخذ محددها الكامل.

المصفوفة الأصلية المختزلة تعد أشجار الرسم الأصلي ذي الخمسة رؤوس. أما المصفوفة المعاد بناؤها فهي كاملة لرسم الأربعة. في هذا المثال تساوى العددان بسبب الرأس الطرفي E، لكن هذا لا يجعل المحددين الكامل والمختزل شيئًا واحدًا.

الصورة الداخلية تعرض شجرة أصلية واحدة بالذهب يسارًا، والرسم بعد حذف E يمينًا. اللون يحدد الحواف المختارة فقط؛ الرمادي حواف متاحة لم نخترها. علامة الصفر بجانب الرسم الجديد تخص محدد مصفوفته الكاملة، وليس عدد أشجاره.

الاتصال وقوائم الحواف يسبقان استعمال الناتج

في الرسم الأول، قبل إضافة AC، كانت الدورة AB وBC وCD وAD مع الجسر CE. حذف أي حافة من الدورة يعطي شجرة مع CE، فيكون العدد 4. إضافة AC أعطت خيارات جديدة فصار العدد 8؛ لم تعد كل مجموعة من أربع حواف صالحة.

في مثال آخر على الأسماء الخمسة، ارسم AB وAC وBC مثلثًا، ثم CD وDE جسرين. يلزم الجسران في كل شجرة، ونختار حافتين من ثلاث حواف المثلث. عدد الأشجار 3 رغم أن مجموع الحواف 5 مثل مثال الدورة والجسر.

وإذا استعملنا AB وBC وCD وAD وAC وتركنا E معزولًا، فلا شجرة تمتد الرؤوس الخمسة. العدد صفر، مع أن الجزء على الأربعة يملك 8 أشجار. الجدول يقارن السؤال على الرؤوس الخمسة دائمًا، ويمنع الخلط بعدد أشجار جزء منها.

لا يعطينا عدد الحواف وحده عدد الأشجار، ولا يخبرنا العدد 8 بأن كل اختيار صالح أو أن هناك شجرة صغرى فريدة. نحافظ على أسماء الرؤوس والحواف، ونحسب خياراتها المختلفة ضمن الرسم المحدد؛ تغيير الاتصال أو عزل رأس يغير السؤال.

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