الاتصال الجبري: هل تعني حواف أكثر قيمة أكبر؟

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

لا؛ دورة الرؤوس الستة تعطي القيمة1 بحوافها الست، بينما مثلثان يصل بينهما CD فقط يعطيان (5−√17)/2، وهي أقل من1/2، رغم وجود سبع حواف. نقارن رسمين مختلفين في وصلاتهما؛ لا نقول إن إضافة حافة إلى الرسم نفسه خفضت القيمة.

• الاتصال الجبري هو ثاني أصغر قيمة ذاتية لمصفوفة لابلاس، مع عد القيم المكررة كل مرة. يكون موجبًا إذا وفقط إذا كان الرسم متصلًا. [1] نستعمل هنا رسمًا بسيطًا غير موجه وبلا أوزان.
• نبني L بدرجة الرأس على القطر، و−1 بين المتجاورين، وصفر بين غير المتجاورين. [2] نثبت ترتيب A B C D E F ونستعمل المصفوفة الكاملة غير المطبعة.
• الدورة AB BC CD DE EF AF لها الطيف (0,1,1,3,3,4)، لذا ثاني قيمة1. المثلثان AB AC BC وDE DF EF مع CD لهما القيمة (5−√17)/2≈0.438، وهي أصغر رغم الحافة الزائدة.
• في حساب المثلثين المتصلين نحصل على العامل t(t−3)^3(t²−5t+2). جذرا العامل التربيعي (5−√17)/2 و(5+√17)/2؛ الأول يأتي بعد الصفر وقبل3.
• حذف CD يترك مثلثين منفصلين بست حواف وطيف (0,0,3,3,3,3). ثاني قيمة صفر؛ لا نتجاوز الصفرين إلى أول عدد موجب. ست حواف لا تميز هذا الرسم من الدورة المتصلة.
• راجعنا محدد tI−L بالضبط عبر720 تبديلًا لكل رسم، وطابقنا العوامل والدرجات. هذه مقارنة محددة لا قياس أمان لشبكة واقعية، ولا حساب أشجار ممتدة أو دورة شاملة أو توجيه للحواف.

نقرأ ثاني قيمة مع التكرارات

نثبت ستة رؤوس مختلفة A وB وC وD وE وF. حوافنا غير موجهة؛ AB وBA اسمان للحافة نفسها. لا حلقات ذاتية ولا حواف مكررة ولا أوزان في الأمثلة، ولا ننشئ رأسًا عند تقاطع خطين في الصورة.

الاتصال الجبري هو ثاني أصغر قيمة ذاتية لمصفوفة لابلاس، مع حساب التعدد. [1] نرمز إليه λ₂؛ نرتب القيم الست من الأصغر إلى الأكبر، ونأخذ الخانة الثانية، لا ثاني عدد مختلف عن الأول.

في الطيف (0,1,1,3,3,4) تأتي1 في الخانة الثانية، ثم1 مرة أخرى في الثالثة. أما (0,0,3,3,3,3) فتأتي فيه0 ثانيةً أيضًا. حذف الأعداد المكررة قبل الاختيار يغير السؤال ويعطي جوابًا خطأ.

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

لا نعامل λ₂ بوصفه عدد مسارات أو احتمال نجاح رحلة. العدد في مثال المثلثين غير صحيح، وهذا طبيعي لأنه قيمة ذاتية، لا حصرًا لأشياء منفصلة. لا نضيف وحدة زمن أو طول إليه دون نموذج آخر.

السؤال هنا عن ترتيب قيم رسمين بحسب هذا التعريف الرياضي. لا يكفي وجود حواف أكثر لإعلان أن λ₂ أكبر. سنثبت فرق القيم بمصفوفتيهما وقوائمهما الكاملة، بدل إعطاء وصف عام عن «قوة الشبكة».

ابن مصفوفة لابلاس للرسم المعلن

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

في الدورة ذات الحواف AB وBC وCD وDE وEF وAF، درجة كل رأس2. صف A هو (2,−1,0,0,0,−1)، لأنه متصل بـB وF فقط. صف C هو (0,−1,2,−1,0,0) لأنه متصل بـB وD.

في المثلثين مع CD، درجات الرؤوس بالترتيب (2,2,3,3,2,2). صف C يصبح (−1,−1,3,−1,0,0): له A وB وD جيرانًا. وصف D هو (0,0,−1,3,−1,−1)، لأنه متصل بـC وE وF.

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

كل صف يجمع إلى صفر: درجة الرأس تقابل خانات −1 التي تمثل جيرانه. لذلك L(1,1,1,1,1,1)=0 في أمثلتنا. وجود قيمة ذاتية صفر لا ينفي الاتصال؛ علينا معرفة القيمة التالية في القائمة.

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

الدورة تعطي القيمة1 بحوافها الست

رسم الدورة يضم AB وBC وCD وDE وEF وAF فقط. يمكن الوصول فيه بين أي رأسين باتباع الحواف دون اتجاهات؛ الأسماء مرتبة حول حلقة، ولا توجد حافة AC أوDF في هذا الرسم.

لنرمز إلى متغير القيمة الذاتية بالحرف t. حسبنا محدد tI−L، حيث I مصفوفة الوحدة ذات الست خانات القطرية1. الناتج يتحلل إلى t(t−1)^2(t−3)^2(t−4). الجذور هي القيم التي تجعل هذا المحدد صفرًا.

العامل t يعطي0، والعامل (t−1)^2 يعطي1 مرتين، و(t−3)^2 يعطي3 مرتين، والعامل الأخير يعطي4. إذن قائمة القيم الست هي (0,1,1,3,3,4)، وثاني قيمة فيها1.

مجموع القيم12 يطابق مجموع القطر12 في حسابنا. وتكرر1 لا يعني وجود حافة مكررة أو رأسين لهما الاسم نفسه؛ إنه تكرر جذر في كثيرة الحدود المحسوبة للمصفوفة.

اللوحة اليسرى من الصورة الرئيسية تعرض هذه الحواف الست وقيمة λ₂=1. ليس ارتفاع دائرة أو طول خط في الرسم مدخلًا للحساب؛ المصفوفة تعتمد على من يتصل بمن وعلى الدرجات، لا مواضع النقاط.

الدورة متصلة وقيمتها موجبة كما نتوقع من تعريف الاتصال الجبري. لكن لا نحتاج أن نعتبر هذه القيمة أكبر ما يمكن على ستة رؤوس؛ المطلوب الآن مقارنة رسم واحد آخر يملك حافة أكثر.

سبع حواف، لكن القيمة أصغر من نصف

نبني مثلث ABC بالحواف AB وAC وBC، ومثلث DEF بالحواف DE وDF وEF، ثم نصل C بـD. توجد سبع حواف، والرسم متصل لأن CD تنقلنا بين المثلثين. لا توجد AF في هذا الرسم.

حسبنا المصفوفة ذات الدرجات (2,2,3,3,2,2)، فوجدنا det(tI−L)=t(t−3)^3(t²−5t+2). الناتج ليس حاصل ضرب درجات الرؤوس؛ خانات التجاور تدخل في المحدد أيضًا، وهي ما يحتفظ بترتيب الاتصال.

يعطي العامل التربيعي الجذرين (5−√17)/2 و(5+√17)/2. بما أن16<17<25، فلدينا4<√17<5. لذلك 0<(5−√17)/2<1/2؛ الجذر الأصغر موجب ويقع بين0 و3.

والجذر الأكبر يتجاوز(5+4)/2=4.5، فيأتي بعد القيم الثلاث3. القائمة المرتبة هي (0,(5−√17)/2,3,3,3,(5+√17)/2). الخانة الثانية هي الجذر الأصغر، لا العدد3 المكرر ثلاث مرات.

تقريب الجذر الأصغر هو0.438447 تقريبًا. نستعمل0.438 للشرح، لكن المقارنة لا تعتمد على التقريب: الحد الدقيق الأقل من1/2 يثبت أنه أصغر من قيمة الدورة1. بقيت القيمة موجبة والرسم متصلًا.

لدينا إذن ست حواف مع قيمة1، وسبع مع قيمة دون1/2. مواضع الحواف مختلفة؛ الدورة ليست جزءًا من الرسم الثاني. فهي تستعمل AF وCD وBC، بينما الرسم الثاني يعوض AF بحواف داخل المثلثين ويحتفظ بوصلة واحدة بينهما.

لا نستنتج أن إضافة حافة إلى رسم ثابت خفضت λ₂. لم نبدأ بالدورة ونضف حافة فقط؛ بنينا رسمًا آخر. هذا الفرق يمنع تحويل المقارنة الصحيحة بين مدخلين إلى ادعاء عن أثر تعديل واحد داخل المدخل نفسه.

بعد حذف الجسر يأتي صفران متتاليان

نحذف CD من رسم المثلثين فقط، ونبقي AB وAC وBC وDE وDF وEF. صار عدد الحواف6، مثل الدورة الأولى، لكن لا اتصال بين جهتي ABC وDEF. كل رأس داخل مثلثه درجته2.

تتكون المصفوفة الآن من جزأين منفصلين للمثلثين. كثيرة الحدود التي حسبناها هي t^2(t−3)^4، فتكون قائمة الجذور (0,0,3,3,3,3). جاءت القيمة0 مرتين، ثم3 أربع مرات.

عند أخذ ثاني خانة نحصل على0، كما يناسب انفصال الرسم. لو بحثنا بدل ذلك عن أول قيمة غير صفرية لاخترنا3 وأجبنا عن سؤال آخر. لذلك احتفظنا بالتكرارات عند تعريف الترتيب وفي الجدول.

الصورة الداخلية تقارن الرسم المنفصل بالدورة المتصلة، وكلاهما بست حواف على الرؤوس الستة نفسها. حتى تساوي العدد والدرجات كلها2 لا يجعل الاتصال أو الطيف متساويين؛ حواف الدورة تربط الأسماء على حلقة واحدة.

الجدول يضم الرسوم الثلاثة بقوائم قيمها. صف المثلثين مع CD لا يمثل حالة إضافة CD إلى الدورة؛ وصف المثلثين دونها يمثل حذفها من ذلك الرسم وحده. تثبيت اسم المدخل يوضح العلاقة بين كل عمليتين.

نكتب a=(5−√17)/2 وb=(5+√17)/2 للاختصار في الجدول. الحرفان الصغيران عددان، وليسا رأسي الرسم A وB. يأتي a بعد0 وقبل3، ويأتي b بعد3.

المصفوفة والحساب يحددان نطاق المقارنة

راجعنا محدد tI−L في كل رسم بتوسيع دقيق على720 تبديلًا للصفوف والأعمدة الستة. معاملات كثيرة الحدود أعداد صحيحة، ثم ضربنا العوامل المكتوبة لنراجع أنها تعطي المعاملات نفسها، لا مجرد قيم عددية قريبة من الجذور.

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

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

ليس λ₂ عدد الأشجار الممتدة ولا درجة رأس واحد ولا أقل عدد من الحواف يكفي لقطع الرسم. الأسماء قد تتجاور في أكثر من مسألة، لكن طريقة الحساب والمطلوب مختلفان؛ هنا نحافظ على مصفوفة الستة كاملة.

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

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