نفس الطيف: هل يعيد إلينا وصلات الرسم نفسها؟

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

لا تكفي دائمًا. الرسم AB AC AD AE AF BE CD والرسم AC AD AF BC BD BE CD يشتركان في طيف مصفوفة التجاور كله، لأن كليهما يعطي p(t)=t⁶−7t⁴−4t³+7t²+4t−1. لكن قائمتي الدرجات المرتبتين مختلفتان، ولذلك لا يحولهما تبديل أسماء الرؤوس إلى الرسم نفسه.

• الرسمان المتساويان في الطيف يشتركان في قائمة القيم الذاتية مع تكراراتها. [1] نعتمد هنا طيف مصفوفة التجاور؛ ذكر المصفوفة ضروري لأن طيف لابلاس اصطلاح آخر. [2]
• نبني مصفوفتين M₁ وM₂ بترتيب A B C D E F. الخانة1 تعني وجود الحافة، والخانة0 غيابها، والقطر صفر في رسمنا البسيط بلا حلقات. [3] لكل رسم ستة رؤوس وسبع حواف.
• درجات الأول مرتبة (1,2,2,2,2,5)، ودرجات الثاني (1,1,3,3,3,3). وجود درجة5 في الأول وغيابها من الثاني يثبت اختلاف البنية تحت أي إعادة تسمية للرؤوس.
• حساب det(tI−M) يعطي كثيرة الحدود نفسها في الحالتين، وتتحلل إلى (t+1)²(t⁴−2t³−4t²+6t−1). إذن تتطابق القيم الذاتية كلها مع التعدد، دون الحاجة إلى تقريب جذور العامل الرباعي.
• راجعنا متجهين مستقلين للقيمة الذاتية−1 في كل رسم بضرب المصفوفة في المتجه. الإشارات السالبة تخص أعداد المتجه؛ لا تعني حواف سالبة أو تغيير أسماء الرؤوس.
• أوقفنا البحث بعد215 رسمًا متصلًا عند العثور على الزوج، ثم راجعنا المحدد عبر720 تبديلًا لكل مصفوفة. لا نزعم فحص جميع الرسوم أو أصغر مثال. ومصفوفتا لابلاس لهذا الزوج لا تشتركان في كثيرة الحدود نفسها.

ثبّت المصفوفة قبل مقارنة الطيف

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

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

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

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

لا نعتمد على تشابه الرسوم المطبوعة. تغيير موضع دائرة أو طول خط لا يغير قائمة الحواف المعلنة. كذلك اختلاف صورة الرسم لا يكفي وحده لإثبات اختلاف بنيته؛ ربما رسمنا الوصلات نفسها في مواضع أخرى أو استبدلنا أسماء الرؤوس.

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

رسمان متصلان ومصفوفتان واضحتان

قائمة الحواف في الرسم الأول هي AB وAC وAD وAE وAF وBE وCD. يتصل A بالرؤوس الخمسة الأخرى. توجد مثلثات ABE وACD، ويتصل F بـA فقط. كل رأس يصل إلى A، ولذلك يصل كل رأس إلى أي رأس آخر عبر حواف الرسم.

قائمة الثاني هي AC وAD وAF وBC وBD وBE وCD. توجد مثلثات ACD وBCD تشترك في CD. يتصل F بـA فقط وE بـB فقط. الجزء الذي يضم A وB وC وD متصل، ثم تلتحق به الورقتان E وF؛ لذا الرسم كله متصل أيضًا.

مصفوفة التجاور تضع1 عند تجاور الرأسين و0 عند غياب الحافة، ويكون القطر صفرًا في الرسم البسيط بلا حلقات، وتتماثل الخانات حول القطر لأن الحواف غير موجهة. [3] نثبت ترتيب A B C D E F للصفوف والأعمدة في المصفوفتين معًا.

صف A في M₁ هو (0,1,1,1,1,1)، وصف A في M₂ هو (0,0,1,1,0,1). لا يعني الصفر على قطر A غياب الرأس؛ يعني غياب الحلقة التي تصل A بنفسه. وخانة AB تساوي1 في الأولى وصفرًا في الثانية.

نضع الصفوف الستة كاملة في الجدول والصورة الداخلية. كل صف يصف رأسًا واحدًا بالترتيب المعلن. عند قراءة صف C مثلًا، تبقى الخانة الرابعة للرأس D؛ لا نعيد ترتيب الأعمدة بحسب عدد الواحدات أو بحسب مواضع الرؤوس في الصورة.

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

اختلاف الدرجات يمنع إعادة التسمية

نجمع كل صف لنحسب درجة رأسه. في الأول نجد بالترتيب (5,2,2,2,2,1)، وفي الثاني (3,3,3,3,1,1). هذه أعداد الجيران، ولا يدخل طول الخط أو زاوية الرسم في حسابها. مجموع كل قائمة14 يطابق عدد الخانات1 والحواف السبع.

بعد ترتيب القائمتين تصاعديًا نحصل على (1,2,2,2,2,5) و(1,1,3,3,3,3). الأول فيه رأس واحد درجته5، والثاني ليس فيه أي رأس بهذه الدرجة. هذه شهادة مباشرة يمكن فحصها من قوائم الحواف قبل أي حساب للمحدد.

نفترض أن هناك تبديلًا للأسماء يحافظ على جميع الحواف. كل جار للرأس A في الأول سيذهب إلى جار لصورة A في الثاني، والعكس كذلك. لذلك يجب أن تبقى درجة هذا الرأس5. لكن لا توجد في الثاني درجة5؛ الافتراض مستحيل.

إذن لا نقول فقط إن الحافة AB مختلفة عند الأسماء الثابتة. تلك ملاحظة أضعف، لأن تبديل الأسماء قد يعوضها في بعض الأزواج. شاهد الدرجات يمنع كل إعادة تسمية تحفظ الحواف، فيثبت أن الرسمين غير متماثلين في البنية.

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

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

كثيرة الحدود تطابق الطيف كله

نحسب p(t)=det(tI−M)، حيث I مصفوفة الوحدة، وt متغير عددي، وM مصفوفة التجاور المختارة. جذور هذه الكثيرة هي القيم الذاتية للمصفوفة. [2] نطبق الحساب على M₁ ثم M₂، فلا نستبدل أحد المدخلين بالآخر أثناء التوسيع.

في الحالتين نحصل على p(t)=t⁶−7t⁴−4t³+7t²+4t−1. معامل t⁵ يساوي صفرًا، وليس هناك حد محذوف بمعامل غير صفري. نعتمد الناتج الدقيق بمعاملاته الصحيحة، ولا نقارن قائمة جذور مدورة إلى منزلة عشرية واحدة.

الناتج يتحلل إلى (t+1)²(t⁴−2t³−4t²+6t−1). راجعنا حاصل ضرب العاملين فطابق كثيرة الحدود كاملة. العامل الأول يعطي القيمة−1 مرتين، والعامل الرباعي يحدد القيم الأربع الباقية. ليست أسماء الرؤوس جزءًا من هذه العوامل.

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

راجعنا أيضًا آثار القوى من الأولى إلى السادسة، فوجدنا في المصفوفتين القائمة (0,14,12,70,120,446). هذا فحص حسابي إضافي في مثالنا، وليس استبدالًا للمحدد بمجرد عدد الحواف. تطابق14 وحده كان سيعطينا معلومات أقل بكثير.

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

متجهات القيمة−1 لا تصف حواف سالبة

نستطيع مراجعة جزء من النتيجة مباشرة. المتجه ذو ست خانات مرتبة A B C D E F، وضرب M فيه يجمع خانات الجيران لكل رأس. إذا كان Mv=−v وكان v غير صفري، فإن−1 قيمة ذاتية للمصفوفة.

في الرسم الأول نأخذ v=(0,1,0,0,−1,0). خانة A في M₁v تجمع خانات جيرانه فتساوي1−1=0. خانة B تقرأ خانة E فتساوي−1، وخانة E تقرأ B فتساوي1؛ بقية الخانات صفر. الناتج هو−v كما نريد.

المتجه الثاني في الأول هو (0,0,1,−1,0,0). تتبادل خانتا C وD الإشارتين عند الضرب، وتلغيان بعضهما في خانة A. المتجهان مستقلان لأن أحدهما غير صفري في B وE، والآخر في C وD؛ ليس أحدهما مضاعفًا للآخر.

في الثاني نأخذ (0,0,1,−1,0,0) و(1,−1,0,0,1,−1). راجعنا الضرب لكل منهما مع M₂ فوجدنا سالب المتجه نفسه. الأول يملك خانتي C وD، والثاني لا يملكهما ويملك خانات أخرى غير صفرية؛ لذا هما مستقلان أيضًا.

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

تدعم هذه المراجعة العامل (t+1)² لكنها لا تستبدل فحص كثيرة الحدود كاملة. مشاركة قيمة واحدة، حتى مرتين، لا تكفي لإعلان تساوي الطيف كله. ما يثبت ذلك هنا هو تطابق كثيرة الحدود ذات الدرجة السادسة، ثم يأتي الضرب المباشر كشاهد إضافي.

حدود البحث والفرق عن لابلاس

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

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

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

لو بدلنا مصفوفة التجاور بمصفوفة لابلاس L=D−M، حيث D قطر درجات الرؤوس، لتغير الحساب. في المثال الأول كثيرة الحدود لها معامل70 عند t⁴، وفي الثاني لها72. اختلاف معامل واحد يكفي لنفي تطابق كثيرتي الحدود في هذه المقارنة الجديدة.

راجعنا كذلك tr(L₁²)=56 وtr(L₂²)=52. إذن الزوج الذي عرضناه متساوٍ في طيف التجاور لا في طيف لابلاس. لا ننقل إليه نتيجة عن القيمة الذاتية الثانية للابلاس أو عدد الأشجار الممتدة أو محدد مصفوفة مسارات بين مصادر ومصبات.

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