متعدد الحدود المطابق

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

تم تعريف عدة أنواع مختلفة من كثيرات الحدود المطابقة. ليكن G رسمًا بيانيًا يحتوي على n رأسًا، وليكن m _k عدد عمليات مطابقة k حافة.

إحدى كثيرات الحدود المطابقة لـ G هي $${\displaystyle m_{G}(x):=\sum _{k\geq 0}m_{k}x^{k}.}$$

يُعرّف تعريف آخر متعدد الحدود المطابق على النحو التالي: $${\displaystyle M_{G}(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}.}$$

التعريف الثالث هو متعدد الحدود $${\displaystyle \mu _{G}(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k}.}$$

لكل نوع استخداماته، وجميعها متكافئة بتحويلات بسيطة. على سبيل المثال، $${\displaystyle M_{G}(x)=x^{n}m_{G}(-x^{-2})}$$ و $${\displaystyle \mu _{G}(x,y)=y^{n}m_{G}(x/y^{2}).}$$

النوع الأول من متعددات الحدود المطابقة هو تعميم مباشر لمتعدد حدود الرخ .

يرتبط النوع الثاني من كثيرات الحدود المطابقة ارتباطًا وثيقًا بكثيرات الحدود المتعامدة . على سبيل المثال، إذا كانت G  = K _{m , n} هي الرسم البياني الثنائي الكامل ، فإن النوع الثاني من كثيرات الحدود المطابقة يرتبط بكثيرة حدود لاغير المعممة L _n ^α ( x ) بالعلاقة التالية: 

$${\displaystyle M_{K_{m,n}}(x)=n!L_{n}^{(mn)}(x^{2}).}$$

إذا كانت G هي الرسم البياني الكامل K _n ، فإن M _G ( x ) هي متعددة حدود هيرميت: $${\displaystyle M_{K_{n}}(x)=H_{n}(x),}$$ حيث أن H _n ( x ) هي "متعددة حدود هيرميت الاحتمالية" (1) في تعريف متعددات حدود هيرميت . وقد لاحظ جودسيل (1981) هذه الحقائق .

إذا كانت G غابة ، فإن متعدد الحدود المطابق لها يساوي متعدد الحدود المميز لمصفوفة التجاور الخاصة بها .

إذا كان G مسارًا أو دورة ، فإن MG ( x ) هو متعدد حدود تشيبيشيف . في هذه الحالة، _يكون μG(1, x) _متعدد حدود فيبوناتشي أو متعدد حدود لوكاس على التوالي.

ترتبط متعددة الحدود المطابقة للرسم البياني G ذي n رأسًا بمتممته من خلال زوج من الصيغ (المتكافئة). إحداهما متطابقة توافقية بسيطة منسوبة إلى زاسلافسكي (1981) . والأخرى متطابقة تكاملية منسوبة إلى جودسيل (1981) .

توجد علاقة مماثلة للرسم البياني الفرعي G من K _{m , n} ومكمله في K _{m , n} . هذه العلاقة، التي تعود إلى ريوردان (1958)، كانت معروفة في سياق وضعيات الرخ غير المهاجمة ومتعددات حدود الرخ.

يُستخدم مؤشر هوسويا للرسم البياني G، أي عدد التطابقات، في المعلوماتية الكيميائية كمؤشر بنيوي للرسم البياني الجزيئي. ويمكن حسابه كـ m _G (1) ( غوتمان 1991 ) .

تم تقديم النوع الثالث من متعدد الحدود المطابق بواسطة فاريل (1980) كنسخة من "متعدد الحدود غير الدوري" المستخدم في الكيمياء .

في الرسوم البيانية العشوائية، أو حتى الرسوم البيانية المستوية ، يُعد حساب متعدد الحدود المطابق مسألةً كاملةً من فئة #P ( جيروم، 1987 ) . ومع ذلك، يمكن حسابه بكفاءة أكبر عند معرفة بنية إضافية للرسم البياني. على وجه الخصوص، يُعد حساب متعدد الحدود المطابق على الرسوم البيانية ذات n رأسًا وعرض الشجرة k قابلًا للمعالجة بمعامل ثابت : إذ توجد خوارزمية يكون زمن تشغيلها، لأي ثابت k ، متعدد حدود في n بأس لا يعتمد على k ( كورسيل، ماكوفسكي، وروتيكس ، 2001 ) . يمكن حساب متعدد الحدود المطابق لرسم بياني ذي n رأسًا وعرض زمرة k في زمن n ^{O( k )} ( ماكوفسكي وآخرون، 2006 ) .

• كورسيل، ب .؛ ماكوفسكي، ج. أ.؛ روتيكس، يو. (2001)، "حول تعقيد المعاملات الثابتة لمسائل تعداد الرسوم البيانية القابلة للتعريف في منطق الرتبة الثانية الأحادي" (ملف PDF) ، الرياضيات التطبيقية المنفصلة ، ​​108 ( 1-2 ): 23-52 ، doi : 10.1016/S0166-218X(00)00221-3.
• فاريل، إي جيه (1980)، "متعددة الحدود المطابقة وعلاقتها بمتعددة الحدود غير الدورية للرسم البياني"، آرس كومبيناتوريا ، 9 : 221-228.
• جودسيل، سي دي (1981)، "متعددات حدود هيرميت وعلاقة الازدواجية لمتعددات حدود المطابقة"، كومبيناتوريكا ، 1 (3): 257-262 ، doi : 10.1007/BF02579331.
• غوتمان، إيفان (1991)، "كثيرات الحدود في نظرية المخططات"، في بونشيف، د.؛ روفراي، د.هـ. (محرران)، نظرية المخططات الكيميائية: مقدمة وأساسيات ، الكيمياء الرياضية، المجلد  1، تايلور وفرانسيس، الصفحات 133-176 ، ISBN  978-0-85626-454-2.
• جيروم، مارك (1987)، "أنظمة المونومر-دايمر ثنائية الأبعاد غير قابلة للمعالجة حسابيًا"، مجلة الفيزياء الإحصائية ، 48 (1): 121-134 ، Bibcode : 1987JSP....48..121J ، doi : 10.1007/BF01010403.
• ماكوفسكي، جيه إيه؛ روتيكس، أودي؛ أفربوش، إيليا؛ جودلين، بيني (2006)، "حساب كثيرات حدود الرسم البياني على رسوم بيانية ذات عرض زمرة محدود"، وقائع ورشة العمل الدولية الثانية والثلاثين حول مفاهيم نظرية الرسم البياني في علوم الحاسوب (WG '06) (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد  4271، سبرينغر-فيرلاغ، الصفحات 191-204 ، doi : 10.1007/11917496_18 ، ISBN  978-3-540-48381-6تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 24 يونيو 2021 ، وتمت معاينته بتاريخ 15 سبتمبر 2019..
• ريوردان، جون (1958)، مقدمة في التحليل التوافقي ، نيويورك: وايلي.
• زاسلافسكي، توماس (1981)، "متجهات المطابقة التكميلية وخاصية تمديد المطابقة المنتظمة"، المجلة الأوروبية للتوافقية ، 2 : 91-103 ، doi : 10.1016/s0195-6698(81)80025-x.