🔢 mathematics

On the number of generalized cospectral mates of graphs

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

المؤلفون الأصليون: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

نُشر 2026-03-24

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك محقق يحاول تحديد هوية مشتبه به بناءً على "بصمته". في عالم الرياضيات، تُعتبر الرسوم البيانية (التي هي مجرد شبكات من النقاط المتصلة بخطوط) تمتلك بصمات تسمى الأطياف (Spectra).

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

المشكلة: هل هناك الكثير من التوائم؟

لفترة طويلة، تساءل الرياضيون: "هل يمكننا التمييز بين هذه الرسوم البيانية؟"

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

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

السؤال الكبير: إذا كان للرسم البياني "محتلون"، فكم عدد هؤلاء المحتلين الذين يمكن أن يكونوا؟ هل هم واحد فقط؟ عشرة؟ مليون؟

الحل: "مصفوفة السير" و"الصيغة الطبيعية لسميث"

استخدم المؤلفون في هذه الورقة البحثية، محمد رضا وفريقه، طريقة ذكية لعدّ هؤلاء المحتلين دون الحاجة إلى إيجاد كل واحد منهم على حدة.

إليك نهجهم، مقسماً باستخدام التشبيهات:

1. مصفوفة السير (Walk Matrix): "ذاكرة" الرسم البياني

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

إذا كان الرسم البياني "قابلاً للتحكم" (Controllable)، فإن هذه الذاكرة تكون فريدة وقوية. وهذا يعني أن هيكل الرسم البياني صلب ويصعب تزييفه.

2. الصيغة الطبيعية لسميث (Smith Normal Form): "الكود الأولي"

عندما ينظر الرياضيون إلى مصفوفة السير، يمكنهم تفكيكها إلى كود خاص يسمى الصيغة الطبيعية لسميث (SNF).
فكر في الـ SNF على أنها التحليل إلى العوامل الأولية للحمض النووي للرسم البياني. تماماً كما يمكن تفكيك أي رقم إلى أعداد أولية (مثل $12 = 2 \times 2 \times 3$ )، فإن مصفوفة السير تتفكك إلى قائمة من "العوامل الثابتة".
يركز المؤلفون على الرقم الأخير في هذه القائمة. هذا الرقم يحمل السر وراء عدد المحتلين الموجودين.

3. "مستوى" المحتل

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

رؤية جوهرية: يثبت البحث أنه إذا تطلب اثنان من المحتلين مفاتيح من نفس الحجم (المستوى)، فهما في الواقع نفس الرسم البياني (مع إعادة تسمية النقاط فقط).
لذلك، لعدّ المحتلين، عليك فقط عدّ كم حجم مختلف من المفاتيح هو أمر ممكن.

الاكتشاف الكبير (الحد الأعلى)

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

الصيغة باللغة البسيطة:
إذا تفكك الرقم الأخير في الكود إلى عوامل أولية بهذا الشكل:
$2^3 \times 3^2 \times 5^1$
(والتي تعني $2 \times 2 \times 2 \times 3 \times 3 \times 5$ )

يتم حساب عدد المحتملين من المحتلين عن طريق أخذ الأسس (3، 2، 1)، وإضافة 1 إلى كل منها، ضربها في بعضها، ثم طرح 1 (لأن أحد "المفاتيح" هو الرسم البياني نفسه).

$(3+1) \times (2+1) \times (1+1) - 1 = 4 \times 3 \times 2 - 1 = 23$ .
إذن، يمكن لهذا الرسم البياني أن يمتلك 23 محتلاً كحد أقصى.

لماذا هذا مهم؟

إنه حد، وليس تخميناً: قبل هذا، لم يكن لدينا سقف صلب لعدد المحتلين الذين يمكن أن يمتلكهم الرسم البياني. الآن، أصبح لدينا "حد للسرعة" رياضياً.
إنه يعمل مع العديد من الرسوم البيانية: اختبر المؤلفون هذا على آلاف الرسوم البيانية العشوائية. وجدوا أن حوالي 39% من جميع الرسوم البيانية العشوائية تندرج تحت هذه "عائلة Fn" الخاصة حيث تنطبق هذه القاعدة. هذه كتلة ضخمة من عالم الرسوم البيانية!
إثبات من الواقع: قاموا ببناء رسم بياني محدد مكون من 10 نقاط. توقعت رياضياتهم أنه يمكن أن يكون له 3 محتلين كحد أقصى. ثم استخدموا الحاسوب للعثور عليهم، ووجدوا 3 بالضبط. كانت الرياضيات مثالية.

الملخص

فكر في الرسم البياني كأنه لغز فريد.

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

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

إليك ملخص تقني مفصل لورقة "On the number of generalized cospectral mates of graphs" للباحثين Raza وآخرون.

١. بيان المشكلة

تتناول الورقة امتداداً كمياً لمسألة كلاسيكية في نظرية الطيف الرسومي: تحديد عدد الرسوم البيانية غير المتماثلة (non-isomorphic) التي تشترك في نفس الطيف المعمم (generalized spectrum).

الطيف المعمم: يُعرف بأنه الزوج $(\text{Spec}(G), \text{Spec}(\bar{G}))$ ، والذي يتكون من طيف الرسم البياني $G$ وطيف متممه $\bar{G}$ .
الأقران متساويا الطيف المعمم (Generalized Cospectral Mates): مجموعة من الرسوم البيانية غير المتماثلة فيما بينها والتي تشترك في نفس الطيف المعمم.
السؤال الجوهري: بينما من المعروف أن بعض الرسوم البيانية تكون "محددة بطيفها المعمم" (DGS) (أي ليس لها أقران)، تسعى الورقة إلى وضع حدود عليا صريحة على عدد أقران الطيف المعمم للرسوم البيانية التي ليست محددة بشكل فريد. كانت الأعمال السابقة قد قدمت خوارزميات لإيجاد الأقران، لكنها افتقرت إلى وجود حدود نظرية عامة على عدد هذه الأقران لفئات واسعة من الرسوم البيانية.

٢. المنهجية

يستخدم المؤلفون مزيجاً من الجبر الخطي، ونظرية الأعداد، ونظرية المصفوفات التوافقية. تعتمد المنهجية بشكل كبير على مصفوفة المشي (Walk Matrix) والصيغة الطبيعية سميث (Smith Normal Form - SNF) الخاصة بها.

تعريفات وأدوات رئيسية

مصفوفة المشي ( $W(G)$ ): مصفوفة مربعة بحجم $n \times n$ أعمدتها هي $e, A(G)e, \dots, A(G)^{n-1}e$ ، حيث $e$ هو متجه الواحدات (all-ones vector). يكون الرسم البياني قابلاً للتحكم (controllable) إذا كانت $W(G)$ غير منفردة (non-singular).
المصفوفات المتعامدة النسبية (Rational Orthogonal Matrices): إذا كان رسمان بيانيان $G$ و $H$ متساويان في الطيف المعمم وقابلان للتحكم، فإنه توجد مصفوفة متعامدة نسبية منتظمة فريدة $Q$ (حيث $Qe=e$ ) بحيث $Q^T A(G) Q = A(H)$ .
المستوى ( $\ell(Q)$ ): أصغر عدد صحيح موجب $x$ بحيث تكون $xQ$ مصفوفة عددية صحيحة. هذا معلم حسابي حاسم.
الصيغة الطبيعية سميث (SNF): لمصفوفة عددية صحيحة $M$ ، الصيغة هي مصفوفة قطرية $\text{diag}(d_1, \dots, d_n)$ حيث $d_i | d_{i+1}$ . الـ $d_i$ هي العوامل الثابتة (invariant factors).

الإطار النظري

تتقدم المنهجية عبر الخطوات المنطقية التالية:
١. القيود الحسابية: يحلل المؤلفون الخصائص الحسابية للمصفوفات المتعامدة النسبية $Q$ التي تربط بين الرسوم البيانية متساوية الطيف المعمم. يستخدمون SNF لمصفوفة المشي لاستخلاص شروط القابلية للقسمة على المستوى $\ell(Q)$ .
٢. تحليل الرتب فوق الحقول المنتهية: يستقصون رتبة مصفوفة المشي فوق الحقول المنتهية $\mathbb{F}_p$ . يوضحون أنه بالنسبة لرسوم معينة، فإن قيود الرتبة تجبر أعمدة المصفوفة المضروبة في $\ell(Q)$ أن تكون مضاعفات قياسية لمتجه ثابت بمقياس $p^k$ .
٣. التفرد عبر المستوى: يثبتون أنه إذا كان الرسمان البيانيان $H_1$ و $H_2$ متساويان في الطيف المعمم لـ $G$ وكانتا تقابلان المصفوفتين $Q_1$ و $Q_2$ اللتين لهما نفس المستوى، فإن $H_1$ و $H_2$ يجب أن يكونا متماثلين (isomorphic). هذا يقلل من مسألة عد الأقران إلى عد المستويات المسموح بها.
٤. تحديد المستويات المسموح بها: من خلال تحليل تحليل العوامل الأولية لآخر عامل ثابت لمصفوفة المشي، $d_n(W(G))$ ، يحددون أقصى عدد ممكن من المستويات المتميزة.

أ. تعريف العائلة $\mathcal{F}_n$

يعرف المؤلفون عائلة محددة من الرسوم البيانية القابلة للتحكم، $\mathcal{F}_n$ ، تتميز بقيود معينة على العوامل الثابتة لمصفوفات المشي الخاصة بها:
$d_{\lceil n/2 \rceil}(W(G)) = 1 \quad \text{و} \quad d_{n-1}(W(G)) = 2$
هذه العائلة مهمة لأنها كبيرة بما يكفي لتشمل العديد من الرسوم البيانية العشوائية، ولكنها مهيكلة بما يكفي للسماح بحدود حسابية دقيقة.

ب. النظرية ١.١: تفرد المستوى

البيان: لأي رسم بياني $G \in \mathcal{F}_n$ ، إذا كان هناك قرنان $H_1$ و $H_2$ متساويان في الطيف المعمم لـ $G$ ويقابلان مصفوفتين متعامدتين نسبيتين $Q_1$ و $Q_2$ لهما نفس المستوى ( $\ell(Q_1) = \ell(Q_2)$ )، فإن $H_1 \cong H_2$ .
الأهمية: يثبت هذا وجود علاقة تقابل واحد لواحد (حتى التماثل) بين مستوى مصفوفة التحويل وفئة التماثل للقريب.

ج. النظرية ١.٢: الحد العلي الصريح

البيان: ليكن $G \in \mathcal{F}_n$ وليكن التحليل الأولي لآخر عامل ثابت لمصفوفة المشي الخاصة به هو $d_n(W(G)) = \prod_{j=1}^m p_j^{k_j}$ . فإن عدد أقران الطيف المعمم لـ $G$ هو على الأكثر:
$\left( \prod_{j=1}^m k_j \right) - 1$
الاشتقاق: يتم اشتقاق الحد من خلال عد عدد القواسم الممكنة للعوامل الثابتة التي تحقق قيود الرتبة فوق الحقول المنتهية، باستثناء الحالة البديهية حيث المستوى يساوي ١ (والتي تمثل الرسم البياني نفسه).

٤. النتائج والتحليل العددي

مثال دقيق: قام المؤلفون ببناء رسم بياني محدد بـ $n=10$ $n = 10$ رؤوس ينتمي إلى $\mathcal{F}_{10}$ $F_{10}$ .
- آخر عامل ثابت كان $d_{10}(W(G)) = 19350 = 2^1 \cdot 3^2 \cdot 5^2 \cdot 43^1$ .
- الأسس هي $k_1=1, k_2=2, k_3=2, k_4=1$ .
- الحد العللي النظري هو $(1 \times 2 \times 2 \times 1) - 1 = 3$ .
- التحقق التجريبي: أكدت عملية البحث الشامل (brute-force search) أن $G$ لديه بالضبط 3 أقران متساوية في الطيف المعمم ( $H_1, H_2, H_3$ ). وقد وُجد أن مستويات المصفوفات المقابلة هي 3، 15، و5، مما يؤكد أنها متميزة وتتطابق مع التنبؤ النظري.
الانتشار الإحصائي: قام المؤلفون بتوليد 10,000 رسم بياني عشوائي لدرجات مختلفة $n$ $n$ (من 11 إلى 50) باحتمالية حافة $p=0.5$ $p = 0.5$ .
- وجدوا أن حوالي 39% من هذه الرسوم البيانية العشوائية تنتمي إلى العائلة $\mathcal{F}_n$ .
- يشير هذا إلى أن الحد العلوي المستمد قابل للتطبيق على جزء كبير وغير بديهي من فضاء الرسوم البيﺔ البسيطة.

٥. الأهمية والتوجهات المستقبلية

تقدم كمي: تنتقل الورقة من السؤال الثنائي "هل الرسم البياني DGS؟" إلى السؤال الكمي "كم عدد الأقران التي يمكن أن يمتلكها الرسم البياني؟"، مما يوفر حداً علوياً ملموساً وقابلاً للحساب.
قابلية تطبيق واسعة: على عكس النتائج السابقة التي طبقت فقط على الرسوم البيانية التي ليس لها أقران، يوفر هذا العمل حدوداً لفئة كبيرة من الرسوم البيانية التي تملك أقراناً.
ابتكار منهجي: يوفر استخدام الصيغة الطبيعية سميث والقيود الحسابية على المصفوفات المتعامدة النسبية أداة جديدة قوية لـ نظرية الطياف الرسومي، حيث تربط نظرية الأعداد النسبية مباشرة بمسائل تماثل الرسوم البيانية.
العمل المستقبلي: يقترح المؤلفون تخفيف القيود على العوامل الثابتة لتغطية المزيد من الرسوم البيانية، وتوسيع التقنيات لتشمل مصفوفات أخرى (مثل مصفوفة لابلاس بدون علامة، أو مصفوفة المسافة)، واستكشاف متجهات تحكم مختلفة بخلاف متجه الواحدات $e$ .

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