نظام ديناميكي بياني

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

يتناول العمل على أنظمة الفضاءات الديناميكية الرسوم البيانية المحدودة (GDSs) الرسوم البيانية المحدودة وفضاءات الحالة المحدودة. ولذلك، يتضمن البحث عادةً تقنيات من مجالات مثل نظرية الرسوم البيانية ، والتوافقية ، والجبر ، والأنظمة الديناميكية ، بدلاً من الهندسة التفاضلية . من حيث المبدأ، يمكن تعريف ودراسة أنظمة الفضاءات الديناميكية الرسوم البيانية على رسم بياني غير محدود (مثل الأوتوماتا الخلوية أو الأوتوماتا الخلوية الاحتمالية).${\displaystyle \mathbb {Z} ^{k}}$أو أنظمة الجسيمات المتفاعلة عند تضمين بعض العشوائية)، بالإضافة إلى أنظمة التوزيع العام ذات فضاء الحالة اللانهائي (مثل${\displaystyle \mathbb {R} }$كما هو الحال في شبكات الخرائط المترابطة)؛ انظر، على سبيل المثال، وو. ^{[ 1 ]} فيما يلي، يُفترض ضمنيًا أن كل شيء محدود ما لم يُذكر خلاف ذلك.

يتكون نظام الرسم البياني الديناميكي من المكونات التالية:

• الرسم البياني المحدود Y بمجموعة رؤوس v[ Y ] = {1,2, ..., n}. اعتمادًا على السياق، يمكن أن يكون الرسم البياني موجهًا أو غير موجه.
• حالة x _v لكل رأس v من Y مأخوذة من مجموعة محدودة K. حالة النظام هي المجموعة n -tuple x = ( x ₁ , x ₂ , ... , x _n ), و x [ v ] هي المجموعة المكونة من الحالات المرتبطة بالرؤوس في الجوار 1 لـ v في Y (بترتيب ثابت).
• دالة رأسية f _v لكل رأس v . تقوم الدالة الرأسية بربط حالة الرأس v في الوقت t بحالة الرأس في الوقت t  +  1 بناءً على الحالات المرتبطة بالجوار 1 لـ v في Y.
• مخطط تحديث يحدد الآلية التي يتم من خلالها تنفيذ تعيين حالات الرؤوس الفردية بحيث يؤدي إلى إحداث نظام ديناميكي منفصل مع الخريطة F : K ⁿ → K ⁿ .

فضاء الطور المرتبط بنظام ديناميكي ذي دالة F : K ⁿ → K ⁿ هو رسم بياني موجه محدود ذو مجموعة رؤوس K ⁿ وحواف موجهة ( x , F ( x )). وتخضع بنية فضاء الطور لخصائص الرسم البياني Y ، ودوال الرؤوس ( f _i ) _i ، وآلية التحديث. ويسعى البحث في هذا المجال إلى استنتاج خصائص فضاء الطور بناءً على بنية مكونات النظام. ويتسم التحليل بطابع يتراوح من المحلي إلى العالمي.

إذا كانت آلية التحديث، على سبيل المثال، تتألف من تطبيق دوال الرؤوس بشكل متزامن، فإننا نحصل على فئة الأوتوماتا الخلوية المعممة (CA). في هذه الحالة، تُعطى الخريطة العامة F : K ⁿ → K ^{n بالصيغة التالية:}

${\displaystyle F(x)_{v}=f_{v}(x[v])\;.}$

يُشار إلى هذه الفئة باسم الأوتوماتا الخلوية المعممة لأن الأوتوماتا الخلوية الكلاسيكية أو القياسية يتم تعريفها ودراستها عادةً على الرسوم البيانية أو الشبكات المنتظمة، وعادةً ما يُفترض أن تكون وظائف الرؤوس متطابقة.

مثال: ليكن Y مخطط الدائرة ذو الرؤوس {1، 2، 3، 4} والحواف {1، 2}، {2، 3}، {3، 4}، و{1، 4}، ويُرمز له بـ Circ _4. ليكن K = {0، 1} فضاء الحالة لكل رأس، ولنستخدم الدالة nor ₃  : K ³ → K المعرفة بالعلاقة nor ₃ ( x, y, z )  =  (1  + x )(1 + y )(1 + z ) مع باقي القسمة على 2 لجميع دوال الرؤوس. على سبيل المثال، يتم تحويل حالة النظام (0، 1، 0، 0) إلى (0، 0، 0، 1) باستخدام تحديث متزامن. جميع الانتقالات موضحة في فضاء الطور أدناه.        

_{إذا تم تطبيق دوال الرؤوس بشكل} غير متزامن في التسلسل المحدد بواسطة كلمة w = ( w1 , w2 , ..., _wm ) _أو تبديل${\displaystyle \pi }$= (${\displaystyle \pi _{1}}$،${\displaystyle \pi _{2},\dots ,\pi _{n}}$من خلال v [ Y ] نحصل على فئة الأنظمة الديناميكية المتسلسلة (SDS). ^{[ 2 ]} في هذه الحالة، من الملائم تقديم الخرائط المحلية Y - Fi _{المُنشأة} من دوال الرؤوس بواسطة

${\displaystyle F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;.}$

الخريطة SDS F = [ F _Y , w ]  : K ⁿ → K ⁿ هي تركيب الدوال

${\displaystyle [F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;.}$

إذا كان تسلسل التحديث عبارة عن تبديل، فغالباً ما نتحدث عن تبديل SDS للتأكيد على هذه النقطة.

مثال: ليكن Y مخطط الدائرة ذو الرؤوس {1، 2، 3، 4} والحواف {1، 2}، {2، 3}، {3، 4}، و{1، 4}، ويُرمز له بـ Circ _4. ليكن K = {0، 1} فضاء الحالة لكل رأس، ولنستخدم الدالة nor ₃  : K ³ → K المعرفة بالعلاقة nor ₃ ( x,  y,  z ) = (1  + x )(1 + y )(1 + z ) مع باقي القسمة على 2 لجميع دوال الرؤوس. باستخدام تسلسل التحديث (1، 2، 3، 4)، يتم تحويل حالة النظام (0، 1، 0، 0) إلى (0، 0، 1، 0). جميع انتقالات حالة النظام لهذا النظام الديناميكي المتسلسل موضحة في فضاء الطور أدناه.           

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

يمكن جعل كل عنصر من عناصر نظام ديناميكي بياني عشوائيًا بعدة طرق. على سبيل المثال، في نظام ديناميكي تسلسلي، يمكن جعل تسلسل التحديث عشوائيًا. في كل خطوة تكرار، يمكن اختيار تسلسل التحديث w عشوائيًا من توزيع معين لتسلسلات التحديث ذات الاحتمالات المقابلة. يُنشئ فضاء احتمالات المطابقة لتسلسلات التحديث فضاء احتمالات لخرائط SDS. ومن المواضيع الطبيعية للدراسة في هذا الصدد سلسلة ماركوف على فضاء الحالة الناتجة عن هذه المجموعة من خرائط SDS. تُعرف هذه الحالة باسم GDS العشوائي لتسلسل التحديث ، وهي مستوحاة من، على سبيل المثال، العمليات التي تحدث فيها "الأحداث" عشوائيًا وفقًا لمعدلات معينة (مثل التفاعلات الكيميائية)، والتزامن في الحوسبة المتوازية/محاكاة الأحداث المنفصلة، ​​وفي النماذج الحسابية الموصوفة لاحقًا .

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

يمكن أيضًا النظر في حالة كون دوال الرؤوس عشوائية، أي أنظمة التوزيع العشوائي للدوال . على سبيل المثال، تُعد الشبكات البوليانية العشوائية مثالًا على أنظمة التوزيع العشوائي للدوال التي تستخدم مخطط تحديث متزامن، حيث تكون فضاء الحالة K = {0,  1}. تُعد الأوتوماتا الخلوية الاحتمالية المحدودة (PCA) مثالًا آخر على أنظمة التوزيع العشوائي للدوال. من حيث المبدأ، تشمل فئة أنظمة الجسيمات المتفاعلة (IPS) أنظمة الأوتوماتا الخلوية المحدودة وغير المحدودة ، ولكن عمليًا، يركز العمل على أنظمة الجسيمات المتفاعلة بشكل كبير على الحالة غير المحدودة، لأن ذلك يسمح بإدخال بنيات أكثر تعقيدًا في فضاء الحالة.

تشكل أنظمة الرسوم البيانية الديناميكية إطارًا طبيعيًا لالتقاط الأنظمة الموزعة مثل الشبكات البيولوجية والأوبئة عبر الشبكات الاجتماعية، والتي يشار إلى العديد منها بشكل متكرر باسم الأنظمة المعقدة.

• نظرية شبكة التفاعلات الكيميائية
• تحليل الشبكات الديناميكية (موضوع في العلوم الاجتماعية )
• آلة الحالة المحدودة
• شبكة هوبفيلد
• شبكة بتري

• ماكولي، ماثيو؛ مورتفيت، هينينغ س. (2009). "تكافؤ دورات الأنظمة الديناميكية للرسوم البيانية". اللاخطية . 22 (2): 421-436 . arXiv : 0802.4412 . Bibcode : 2009Nonli..22..421M . doi : 10.1088/0951-7715/22/2/010 . S2CID 17978550 . 
• جولوبيتسكي، مارتن ؛ ستيوارت، إيان (2003). منظور التناظر . بازل: بيركهاوزر. ISBN 0-8176-2171-7.

• أنظمة الرسوم البيانية الديناميكية - إطار رياضي للأنظمة القائمة على التفاعل، وتحليلها ومحاكاتها، بقلم هينينغ مورتفيت