Prolaznost i povratnost slučajnih šetnji na grafovima

Tema ovog diplomskog rada je prolaznost i povratnost slučajnih šetnji na grafovima. Diplomski rad je podijeljen u tri poglavlja. U prvom poglavlju cilj je upoznati se s Markovljevim lancima i njihovim osnovnim svojstvima. Također, uvodimo pojmove kao što su povratnost, prolaznost i reverzibilnost. U drugom poglavlju uvodimo pojam grafa te se upoznajemo s osnovnim pojmovima vezanim za graf. Uvodimo slučajnu šetnju na grafu i na električnoj mreži. Također, uvodimo pojam energije. U trećem poglavlju dajemo kriterij za prolaznost i povratnost reverzibilnog Markovljevog lanca. Također, dajemo i dovoljan uvjet za povratnost Markovljevog lanca poznat kao Nash-Williamsov kriterij. Zatim, dajemo teorem koji, uz neke dodatne pretpostavke na Markovljev lanac X, daje dovoljne uvjete za prolaznost tog lanca. Za kraj, dajemo nekoliko primjera.The topic of this thesis is transience and recurrence of random walks on graphs. The thesis is divided into three chapters. In the first chapter, the goal is to get acquainted with Markov chains and their basic properties. We also introduce the notions of recurrence, transience and reversibility. In the second chapter, we introduce the concept of a graph and get familiar with the basic concepts related to graphs. We introduce the notion of a random walk on a graph and on the electrical network. In the third chapter, we give a criterion for recurrence and transience of Markov chains. We also provide sufficient conditions for the recurrence of Markov chains known as the Nash-Williams criterion. Then we give a theorem which, with some additional assumptions on the Markov chain X, provides sufficient conditions for transience of that chain. We conclude the thesis with several examples