Slučajne šetnje na grafovima

master's thesis

• Author: Tin Barišin
• Mentor: Zoran Vondraček (mentor)
• Committee member: Zoran Vondraček (predsjednik povjerenstva)
• Committee member: Rudi Mrazović (član povjerenstva)
• Committee member: Snježana Lubura Strunjak (član povjerenstva)
• Committee member: Bojan Basrak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-02-10, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Grafovi s težinama se mogu interpretirati na više načina: kao slučajni proces ili električna mreža. Iz raznih interpretacija grafa slijede zgodna svojstva grafova koja nam mogu biti korisna za opisivanje geometrije grafa. Osnovno svojstvo slučajnih šetnji su prolaznost i povratnost. Električne mreže predstavljaju potpuno drukčiji pogled na grafove od slučajnih šetnji te omogućuju interpretaciju prolaznosti i povratnosti preko efektivnog otpora. Varijacijski problemi se prirodno nadovezuju na teoriju električnih mreža i omogućavaju nam bolje razumijevanje geometrije grafa s obzirom na prolaznost i povratnost. Primjerice, kako brisanje i zamjena bridova utječe na efektivni otpor grafa. Koristeći ovaj pristup izvodimo nove tehnike za dokazivanje prolaznosti i povratnosti. Razne vrste grafova možemo povezati konceptom grubih izometrija koje čuvaju određene odnose među grafovima. Glavni cilj ovog diplomskog rada je proučavati svojstva grafova vezanih uz slučajne šetnje: prolaznost i povratnost te dokazati njihovu stabilnost na grube izometrije. Korisnost ovog svojstva je sljedeća: za prolazan ili povratan graf, prolaznost ili povratnost grafa lako slijedi za sve grafove koji su mu grubo izometrični, što znači da gruba izometrija čuva određenu vrstu strukture u grafu koja je važna.

Abstract (english)

Weighted graphs can be easily interpreted in several ways: as a stochastic process or electric network. From these different interpretations many different properties of graphs can be derived and used to further describe its geometry. The fundamental properties of random walks are transience and recurrence. Electric networks represent completely different approach on graph interpretation regarding random walks and enable us to interpret transience and recurrence through the concept of effective resistance. Variational problems are natural upgrade on the theory of electric networks and enable us to further understand connection of graph geometry to transience and recurrence. For example, how cutting and shorting the edges affect effective resistance. Using these approaches we derive new techniques for proving transience and recurrence. Furthermore, different types of graphs can be connected using concept of rough isometries that preserve certain relations between graphs. The main idea of this thesis is to investigate the properties of graphs connected to random walks: transience and recurrence and prove their stability under rough isometries. Usefulness of this property is following: for a graph that is transient or recurrent, transience or recurrence comes easily for all graphs that are roughly isometric to him, meaning that rough isometry preserves some kind of graph structure.

• Keywords: grafovi s težinama; geometrija grafa; slučajne šetnje
• Keywords (english): weighted graphs; graph geometry; random walks
• Language: croatian
• URN:NBN: urn:nbn:hr:217:361420
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-07-22 10:24:03