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

الأصل: "Counting Unlabeled Chordal Graphs by Equivariant Evaporation"
· Matthew Sun
arXiv:2607.02613 · 2026-07-01 · CC BY 4.0 · 3 دقيقة
لأول مرة، تُحدَّث متتاليتان من موسوعة المتتاليات الصحيحة تعكسان عدد الرسوم البيانية الوترية، بفضل خوارزمية تحوّل التناظر إلى عدسة مكبرة.

7 278 601 292 779 396 715. هذا هو عدد الرسوم البيانية الوترية المختلفة (Choral graphs) – أي الرسوم البيانية الخالية من الدورات المستحثّة التي طولها أربعة أو أكثر – التي يمكن بناؤها على عشرين رأسًا، إذا ما تعاملنا مع البنى بلا أسماء. هذا الرقم ليس لغزًا لحاسوب عملاق، بل هو النتيجة الدقيقة لـخوارزمية جديدة تنظر إلى التناظر بوصفه أداة لا عائقًا.

تخيّل مشكالاً: بضع قطع زجاجية ملونة تولّد نمطًا لا نهائيًا يتضاعف في المرايا. في مسألة تعداد الرسوم البيانية غير الموسومة (حيث لا نميّز بين الرؤوس)، تكون التناظرات أشبه بتلك المرايا: إنها تبديلات للرؤوس تترك الرسم البياني على حاله. ولعدّ جميع الرسوم البيانية غير الموسومة، لا بد من مراعاة كل انعكاس ممكن. وهنا تدخل لِـمَّة برنسايد: متوسط عدد الرسوم البيانية الثابتة عند كل تبديل – على جميع التبديلات – يساوي العدد المطلوب. المشكلة أن عدد التبديلات هو مضروب عدد الرؤوس، وفي حالة n=20 يصبح 2,43×$10^{18}$ احتمالاً. لكن الخوارزمية تتجنب هذا السيل بالاعتماد على «التبخير».

التبخير عملية أنيقة: تُحذف من الرسم البياني الوتري، مرة بعد أخرى، الرؤوس البسيطة (Simplicial vertices) – أي التي يشكّل جيرانها زمرة (Clique) – حتى يتبقى رسم بياني فارغ. في عام 2021، مكّن نهج ذو روح فون نيومانية – هو البرمجة الديناميكية – من عدّ الرسوم البيانية الوترية الموسومة بسرعة. لكن كيف ننقله إلى عالم التناظرات؟ الجواب: أن نجعل التبخير يطال مدارات كاملة – أي مجموعات من الرؤوس يتحول بعضها إلى بعض عند التبديل. هكذا ينشأ التبخير المداري.

لو احتل كل رسم بياني وتري على 20 رأسًا بايتًا واحدًا، لتجاوز إجمالي حجمها سبعة بيتابايتات – وهو أكثر من جميع البيانات في أكبر مراكز البيانات حول العالم.

أعقد اللحظات هي عندما يكون المدار غير متجانس، وتكون أجزاؤه متصلة بجسور معقدة. وهنا يأتي دور تفكيك الحزم القاسِمة. إذا احتوى تبديل ما على دورة طولها c، وامتدت مركّبة متصلة من الرسم البياني على عدة مدارات، فإنها تنقسم إلى d من «الحزم» المتطابقة، المتناظرة كل منها بالنسبة لزمرة أصغر – أشبه بأن لا ينعكس في المشكال كل الزجاجة بل جزء منها. هذه الحيلة تُرجِع الحساب إلى استدعاء تكراري للمسألة نفسها في عالم مصغَّر: فبدل الزمرة الأصلية، نتعامل مع زمرة رتبتها d مرّة أصغر. ويُبنى على هذا التكرار مخطط حسابي يعدّد أنواع الدورات بدقة ويُجمِّع الإسهامات.

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

التناظر يحفظ شيئًا أساسيًا: في الفيزياء – قوانين الانحفاظ، وفي التوافقيات – بنية المجاميع التعدادية. تكتسب مبرهنة إيمي نويثر هنا تجسيدًا حسابيًا غير متوقع.

مشكال التناظرات لم يكتفِ بتحديث موسوعة OEIS. لقد أظهر كيف تتصادق خوارزميات «التبخير» مع نظرية الزمر، وقدم مخططًا شاملًا لفئات أخرى من الرسوم البيانية – الفترية، والوترية ثنائية الأجزاء، ورسوم القابلية للمقارنة. وفي الأفق: حوسبة موزَّعة وقفزة إلى n=22. وقد تفيد استعارة الحزم القاسِمة في اختبار النماذج التوليدية للشبكات أو في مسائل المعلوماتية الكيميائية حيث يلزم تعداد البنى الجزيئية غير المتماكِلة.

لنعد إلى الرقم 7 278 601 292 779 396 715. لا يقف خلفه فوضى، بل عمارة محكمة من الانعكاسات. فكل تشكيلة من الأضلاع تذكر مدارها في متاهة التناظرات المرآتية، وها قد أمكننا اجتياز هذه المتاهة بلا ضياع.

بالنسبة لـ n=20، تطلّب الأمر تعداد 627 نوعًا مختلفًا من الدورات — لكل منها حده الخاص في مجموع برنسايد.

فكرة تعداد جميع البنى الممكنة وصلت إلى أقصاها في «مكتبة بابل» لخورخي لويس بورخيس، حيث تُحفَظ جميع الكتب الممكنة تصوّرها. تعداد الرسوم البيانية الوترية هو خطوة نحو جرد أحد «رفوف» تلك المكتبة في عالم الأشكال المتقطعة.

a(n) = \frac{1}{n!} \sum_{\pi \in S_n} \mathrm{fix}(\pi)
عدد الأشياء غير الموسومة يساوي متوسط عدد الأشياء الموسومة الثابتة عند كل تبديل
\mathrm{BUNDLE}(\mu) = \mathrm{cfix}(\mu) + \sum_{d>1,\, d\mid\gcd(\mu)} d^{|\mu|-1} \mathrm{cfix}^{\langle N/d \rangle}(\mu/d)
المركّبة الحزمية إما لا تملك تناظرًا داخليًا، أو تنقسم إلى d نسخة أصغر بمضاعفة d^{|μ|-1}
العلماء
Emmy Noether
المفاهيم
الغرافات (graphs)