ทฤษฎีกราฟเชิงวิวัฒนาการเป็นสาขาการวิจัยที่อยู่บนจุดตัดของทฤษฎีกราฟทฤษฎีความน่าจะเป็นและชีววิทยาเชิงคณิตศาสตร์ทฤษฎีกราฟเชิงวิวัฒนาการเป็นแนวทางในการศึกษาว่าโทโพโลยีมีผลต่อวิวัฒนาการของประชากร อย่างไร โทโพโลยีพื้นฐานสามารถส่งผลกระทบอย่างมากต่อผลลัพธ์ของกระบวนการวิวัฒนาการได้อย่างชัดเจนที่สุดในบทความของErez Lieberman , Christoph Hauert และMartin Nowak ^{[ 1 ]}

ในทฤษฎีกราฟเชิงวิวัฒนาการ สิ่งมีชีวิตแต่ละตัวจะครอบครองจุดยอดของกราฟทิศทางที่ มีน้ำหนัก และน้ำหนัก w ของขอบจากจุดยอดiไปยังจุดยอดjแสดงถึงความน่าจะเป็นที่iจะเข้ามาแทนที่jน้ำหนักนี้สอดคล้องกับแนวคิดทางชีววิทยาเรื่องความเหมาะสมโดยที่สายพันธุ์ที่มีความเหมาะสมมากกว่าจะแพร่กระจายได้ง่ายกว่า

คุณสมบัติหนึ่งที่ศึกษาในกราฟที่มีบุคคลสองประเภทคือความน่าจะเป็นของการคงอยู่ (fixation probability ) ซึ่งนิยามว่า ความน่าจะเป็นที่ตัวกลายพันธุ์ประเภท A ที่วางไว้แบบสุ่มเพียงตัวเดียวจะเข้ามาแทนที่ประชากรประเภท B ตามทฤษฎีไอโซเทอร์มอล (isothermal theorem ) กราฟจะมีความน่าจะเป็นของการคงอยู่เท่ากับกระบวนการโมแรน (Moran process) ที่สอดคล้องกัน ก็ต่อเมื่อ กราฟ นั้นเป็นไอโซเทอร์มอล กล่าวคือ ผลรวมของน้ำหนักทั้งหมดที่นำไปสู่จุดยอดหนึ่งๆ จะเท่ากันสำหรับทุกจุดยอด ดังนั้น ตัวอย่างเช่นกราฟสมบูรณ์ที่มีน้ำหนักเท่ากันจะอธิบายกระบวนการโมแรน ความน่าจะเป็นของการคงอยู่คือ

${\displaystyle {\begin{aligned}\rho _{M}={\frac {1-r^{-1}}{1-r^{-N}}}\end{aligned}}}$

โดยที่rคือค่าความเหมาะสมสัมพัทธ์ของชนิดพันธุ์ที่รุกราน

กราฟสามารถจำแนกได้เป็นตัวขยายการคัดเลือกและตัวยับยั้งการคัดเลือก หากความน่าจะเป็นของการคงอยู่ของการกลายพันธุ์ที่เป็นประโยชน์เพียงครั้งเดียวสูงกว่าความน่าจะเป็นของการคงอยู่ของกระบวนการโมแรน ที่สอดคล้อง กัน กราฟนั้นจะเป็นตัวขยายการคัดเลือก มิฉะนั้นจะเป็นตัวยับยั้งการคัดเลือก ตัวอย่างหนึ่งของตัวยับยั้งการคัดเลือกคือกระบวนการเชิงเส้นที่จุดยอดi-1 เท่านั้น ที่สามารถแทนที่จุดยอดi ได้ (แต่ไม่ใช่ในทางกลับกัน) ในกรณีนี้ ความน่าจะเป็นของการคงอยู่คือ(โดยที่Nคือจำนวนจุดยอด) เนื่องจากนี่คือความน่าจะเป็นที่การกลายพันธุ์เกิดขึ้นในจุดยอดแรกซึ่งในที่สุดจะแทนที่จุดยอดอื่นๆ ทั้งหมด เนื่องจากสำหรับทุกrที่มากกว่า 1 กราฟนี้จึงเป็นตัวยับยั้งการคัดเลือกตามนิยาม ${\displaystyle \rho _{G}}$${\displaystyle \rho _{M}}$${\displaystyle \rho _{G}=1/N}$${\displaystyle \rho _{G}<\rho _{M}}$

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

นอกจากนี้เกมวิวัฒนาการยังสามารถศึกษาได้บนกราฟ โดยที่เส้นเชื่อมระหว่างiและjหมายความว่าบุคคลทั้งสองนี้จะเล่นเกมแข่งขันกันเอง

กระบวนการสุ่มที่เกี่ยวข้องอย่างใกล้ชิด ได้แก่แบบจำลองผู้ลงคะแนนซึ่งได้รับการแนะนำโดย Clifford และ Sudbury (1973) และโดย Holley และ Liggett (1975) อย่างอิสระ และได้รับการศึกษาอย่างกว้างขวาง

• Holley, RA; Liggett, TM (1975). "ทฤษฎีบทเออร์โกดิกสำหรับระบบอนันต์ที่มีปฏิสัมพันธ์อย่างอ่อนและแบบจำลองผู้ลงคะแนน"วารสารความน่าจะเป็น 3 ( 4): 643– 663. doi : 10.1214/aop/1176996306 .
• Liggett, Thomas M. (1999). ระบบปฏิสัมพันธ์เชิงสุ่ม: กระบวนการติดต่อ ผู้ลงคะแนน และการกีดกัน . เบอร์ลิน: Springer. ISBN 978-3-540-65995-2.
• Clifford, P.; Sudbury, A. (1973). "แบบจำลองสำหรับความขัดแย้งเชิงพื้นที่" Biometrika . 60 (3): 581– 588. doi : 10.1093/biomet/60.3.581 .
• Martin A. Nowak (2006). พลวัตเชิงวิวัฒนาการ: การสำรวจสมการแห่งชีวิต . เคมบริดจ์: สำนักพิมพ์ Belknap แห่งมหาวิทยาลัยฮาร์วาร์ด . ISBN 978-0-674-02338-3.
• Monk, T. (2018). " Martingales และความน่าจะเป็นของการตรึงของกราฟวิวัฒนาการมิติสูง". Journal of Theoretical Biology . 451 : 10–18 . Bibcode : 2018JThBi.451...10M . doi : 10.1016/j.jtbi.2018.04.039 . PMID  29727631. S2CID  13682722 .

ห้องปฏิบัติการเสมือนจริงสำหรับการศึกษาการวิวัฒนาการบนกราฟ: [1]

• Allen, Benjamin; Nowak, Martin A. (2014). "เกมบนกราฟ" EMS Surveys in Mathematical Sciences . 1 (1): 113– 151. doi : 10.4171/emss/3 .