ในทางคณิตศาสตร์แนวคิดของระบบพลวัตกราฟสามารถนำมาใช้เพื่ออธิบายกระบวนการต่างๆ ที่เกิดขึ้นบนกราฟหรือเครือข่ายได้ ประเด็นสำคัญในการวิเคราะห์ทางคณิตศาสตร์และการคำนวณของระบบพลวัตกราฟคือการเชื่อมโยงคุณสมบัติเชิงโครงสร้าง (เช่น การเชื่อมต่อของเครือข่าย) กับพลวัตโดยรวมที่เกิดขึ้น

งานวิจัยเกี่ยวกับ GDS พิจารณากราฟจำกัดและปริภูมิสถานะจำกัด ดังนั้น งานวิจัยจึงมักเกี่ยวข้องกับเทคนิคจากทฤษฎีกราฟ คณิตศาสตร์เชิงการจัดเรียงพีชคณิตและระบบพลวัตมากกว่าเรขาคณิตเชิงอนุพันธ์ในทางทฤษฎี เราสามารถกำหนดและศึกษา GDS บนกราฟอนันต์ (เช่นออโตมาตาเซลลูลาร์หรือออโตมาตาเซลลูลาร์เชิงความน่า จะเป็น บน ระบบอนุภาค ที่มีปฏิสัมพันธ์เมื่อรวมความสุ่มบางอย่าง) เช่นเดียวกับ GDS ที่มีปริภูมิสถานะอนันต์ (เช่นในแลตทิซแผนที่คู่) ดูตัวอย่างเช่น Wu ^{[ 1 ]}ในส่วนต่อไปนี้ ทุกอย่างจะถือว่าจำกัดโดยปริยาย เว้นแต่จะระบุไว้เป็นอย่างอื่น ${\displaystyle \mathbb {Z} ^{k}}$${\displaystyle \mathbb {R} }$

ระบบพลวัตแบบกราฟถูกสร้างขึ้นจากส่วนประกอบต่อไปนี้:

• กราฟ จำกัดYที่มีเซตของจุดยอด v[ Y ] = {1,2, ... , n} ขึ้นอยู่กับบริบท กราฟนี้อาจเป็นกราฟทิศทางหรือกราฟไร้ทิศทางก็ได้
• สถานะx _vสำหรับแต่ละจุดยอดvของYที่เลือกมาจากเซตจำกัดK สถานะของระบบคือทูเปิลn ตัว 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 ⁿจะกำหนดโดย

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

กลุ่มนี้เรียกว่า ออโตมาตาเซลลูลาร์แบบทั่วไป เนื่องจากออโตมาตาเซลลูลาร์ แบบคลาสสิกหรือแบบมาตรฐาน มักถูกกำหนดและศึกษาบนกราฟหรือตารางปกติ และโดยทั่วไปจะถือว่าฟังก์ชันของจุดยอดนั้นเหมือนกัน

ตัวอย่าง:ให้Yเป็นกราฟวงกลมบนจุดยอด {1,2,3,4} ที่มีขอบ {1,2}, {2,3}, {3,4} และ {1,4} ซึ่งเขียนแทนด้วย Circ ₄ให้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 = ( w ₁ , w ₂ , ... , w _m ) หรือการเรียงสับเปลี่ยน= ( , ) ของv [ Y ] จะได้คลาสของ ระบบไดนามิกแบบลำดับ (SDS) ^{[ 2 ]} ในกรณีนี้ การแนะนำแผนที่ Y -local F _iที่สร้างขึ้นจากฟังก์ชันจุดยอดโดย เป็นเรื่องสะดวก${\displaystyle \pi }$${\displaystyle \pi _{1}}$${\displaystyle \pi _{2},\dots ,\pi _{n}}$

${\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 ₄ให้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) การเปลี่ยนสถานะของระบบทั้งหมดสำหรับระบบพลวัตแบบลำดับนี้แสดงอยู่ในปริภูมิเฟสด้านล่าง

ตัวอย่างเช่น จากมุมมองของการประยุกต์ใช้งาน เป็นเรื่องน่าสนใจที่จะพิจารณากรณีที่ส่วนประกอบอย่างน้อยหนึ่งส่วนของ GDS มีองค์ประกอบสุ่ม แอปพลิเคชันที่กระตุ้นให้เกิดความสนใจอาจรวมถึงกระบวนการที่ไม่เข้าใจอย่างถ่องแท้ (เช่น พลวัตภายในเซลล์) และในบางแง่มุมที่ดูเหมือนจะทำงานตามการกระจายความน่าจะเป็น นอกจากนี้ยังมีแอปพลิเคชันที่อยู่ภายใต้หลักการเชิงกำหนดซึ่งคำอธิบายมีความซับซ้อนหรือจัดการได้ยากจนทำให้การพิจารณาการประมาณค่าเชิงความน่าจะเป็นมีความเหมาะสม

องค์ประกอบทุกส่วนของระบบพลวัตแบบกราฟสามารถทำให้เป็นแบบสุ่มได้หลายวิธี ตัวอย่างเช่น ในระบบพลวัตแบบลำดับ ลำดับการอัปเดตสามารถทำให้เป็นแบบสุ่มได้ ในแต่ละขั้นตอนการวนซ้ำ สามารถเลือกลำดับการอัปเดตwแบบสุ่มจากชุดลำดับการอัปเดตที่กำหนดไว้พร้อมความน่าจะเป็นที่สอดคล้องกันพื้นที่ความน่าจะ เป็นที่ตรงกัน ของลำดับการอัปเดตจะเหนี่ยวนำให้เกิดพื้นที่ความน่าจะเป็นของแผนที่ SDS วัตถุที่เหมาะสมที่จะศึกษาในเรื่องนี้คือห่วงโซ่มาร์คอฟบนพื้นที่สถานะที่เกิดจากชุดแผนที่ SDS นี้ กรณีนี้เรียกว่าGDS แบบสุ่มลำดับการอัปเดตและได้รับแรงบันดาลใจจากกระบวนการที่ "เหตุการณ์" เกิดขึ้นแบบสุ่มตามอัตราที่กำหนด (เช่น ปฏิกิริยาเคมี) การซิงโครไนซ์ในการคำนวณแบบขนาน/การจำลองเหตุการณ์แบบไม่ต่อเนื่อง และในกระบวนทัศน์การคำนวณที่อธิบายไว้ในภายหลัง

ตัวอย่างเฉพาะนี้ที่มีลำดับการอัปเดตแบบสุ่มแสดงให้เห็นข้อเท็จจริงทั่วไปสองประการสำหรับระบบดังกล่าว: เมื่อเปลี่ยนไปใช้ระบบพลวัตกราฟแบบสุ่ม โดยทั่วไปจะนำไปสู่ ​​(1) การศึกษาลูกโซ่ Markov (ที่มีโครงสร้างเฉพาะซึ่งควบคุมโดยส่วนประกอบของ GDS) และ (2) ลูกโซ่ Markov ที่ได้มักจะมีขนาดใหญ่ โดยมีจำนวนสถานะแบบเลขชี้กำลัง เป้าหมายหลักในการศึกษา GDS แบบสุ่มคือการสามารถสร้างแบบจำลองที่ลดขนาดลงได้

นอกจากนี้ เราอาจพิจารณากรณีที่ฟังก์ชันของจุดยอดเป็นแบบสุ่ม กล่าวคือGDS แบบสุ่มเชิงฟังก์ชันตัวอย่างเช่นเครือข่ายบูลีน แบบสุ่ม เป็นตัวอย่างของ GDS แบบสุ่มเชิงฟังก์ชันที่ใช้รูปแบบการอัปเดตแบบซิงโครนัส และปริภูมิสถานะคือK = {0, 1} ออโตมาตาเซลลูลาร์เชิงความน่าจะ เป็นแบบจำกัด (PCA) เป็นอีกตัวอย่างหนึ่งของ GDS แบบสุ่มเชิงฟังก์ชัน โดยหลักการแล้ว กลุ่มของระบบอนุภาคที่มีปฏิสัมพันธ์ (IPS) ครอบคลุมPCA แบบจำกัดและแบบอนันต์ แต่ในทางปฏิบัติ งานวิจัยเกี่ยวกับ IPS ส่วนใหญ่เกี่ยวข้องกับกรณีอนันต์ เนื่องจากทำให้สามารถนำเสนอโทโพโลยีที่น่าสนใจมากขึ้นในปริภูมิสถานะได้

ระบบพลวัตแบบกราฟเป็นกรอบการทำงานที่เป็นธรรมชาติสำหรับการจับภาพระบบแบบกระจาย เช่น เครือข่ายทางชีววิทยาและการระบาดของโรคผ่านเครือข่ายสังคม ซึ่งหลายระบบเหล่านี้มักถูกเรียกว่าระบบที่ซับซ้อน

• ทฤษฎีเครือข่ายปฏิกิริยาเคมี
• การวิเคราะห์เครือข่ายพลวัต ( หัวข้อ ทางสังคมศาสตร์ )
• เครื่องจักรสถานะจำกัด
• เครือข่ายฮอปฟิลด์
• โครงข่ายเพทรี

• Macauley, Matthew; Mortveit, Henning S. (2009). "ความสมมูลของวัฏจักรของระบบพลวัตกราฟ" Nonlinearity . 22 (2): 421– 436. arXiv : 0802.4412 . Bibcode : 2009Nonli..22..421M . doi : 10.1088/0951-7715/22/2/010 . S2CID  17978550 .
• Golubitsky, Martin ; Stewart, Ian (2003). มุมมองด้านสมมาตร . บาเซิล: Birkhauser. ISBN 0-8176-2171-7.

• ระบบพลวัตแบบกราฟ – กรอบทางคณิตศาสตร์สำหรับระบบที่อิงปฏิสัมพันธ์ การวิเคราะห์ และการจำลอง โดย เฮนนิง มอร์ทเวท