Original title: Závislost času fixace v Moranově procesu na počátečním vrcholu
Translated title: Dependence of the fixation time in the Moran process on the initial vertex
Authors: Jahoda, Adam ; Tkadlec, Josef (advisor) ; Melissinos, Nikolaos (referee)
Document type: Bachelor's theses
Year: 2026
Language: eng
Abstract: [eng] [cze]
The Moran process on graphs is a model of mutation spread in structured popula- tions. We study a version in which the resident population cannot fight back against the mutation, so everyone eventually becomes mutated. We are interested in how the time required for the entire population to be mutated depends on population structure and the location of the first mutated individual. We find an asymptotically tight upper bound on this time on undirected graphs and identify graphs that are very fast from some vertices and slow from others. We also study k-partite graphs and very dense graphs, in both cases proving that the process is fast from every vertex. Moranův proces na grafech je model šíření mutací ve strukturované populaci. V této práci zkoumáme verzi tohoto procesu, v níž se nemůže populace proti mutaci bránit. Každý vrchol tedy nakonec skončí zmutován. Zkoumáme závislost času potřebného k zmutování celé populace na její struktuře a pozici prvního zmutovaného jedince v ní. V této práci nalezneme asymptoticky těsný horní odhad na tento čas v neorientovaných grafech. Poté identifikujeme grafy, kde je proces velmi rychlý, pokud startuje z některých vrcholů, ale velmi pomalý z jiných. Také studujeme k-partitní a velmi husté grafy. U nich v obou případech dokážeme, že proces je velmi rychlý bez ohledu na pozici počátečního vrcholu.
Keywords: evolutionary dynamics|Moran process|graf|fixation time; evoluční dynamika|Moranův proces|graf|čas fixace

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/210836

Permalink: http://www.nusl.cz/ntk/nusl-779607


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses