20.500.12556/DKUM-93223 Primeri uporabe pregleda grafov v globino na študijskem programu 2. stopnje Matematika Use cases of depth first search in graphs magistrsko delo V magistrski nalogi predstavimo različne algoritme, ki temeljijo na pregledu grafov v globino (DFS). Delovanje DFS algoritma prikažemo na problemih iz teorije grafov in teorije iger. Predstavimo osnovne pojme teorije grafov in analiziramo delovanje ter časovno zahtevnost DFS algoritma.Definiramo pojem krepke povezanosti in krepko povezanih komponent. Obravnavamo dva algoritma za iskanje krepko povezanih komponent v usmerjenih grafih (Kosaraju-Sharirjev in Tarjanov algoritem), ki ju implementiramo v programskem jeziku Python. V zadnjem poglavju preučujemo uporabo DFS algoritma v teoriji iger. Predstavimo minimax algoritem, ki se uporablja za določanje optimalne poteze v igrah z dvema igralcema in ga optimiziramo z alfa-beta obrezovanjem. Predstavljeno implementiramo v programskem jeziku Python, kjer analiziramo delovanje algoritmov na primeru igre križci in krožci. In this master’s thesis, we present various algorithms based on the depth-first search (DFS). The functioning of the DFS algorithm is demonstrated through problems from graph theory and game theory. We introduce the fundamental concepts of graph theory and analyze the functionality and the time complexity of the DFS algorithm. We define the concept of strong connectivity and strongly connected components. We examine two algorithms for finding strongly connected components in directed graphs (the Kosaraju-Sharir and Tarjan algorithms), both of which are implement in Python. In the final chapter, we explore the application of the DFS algorithm in game theory. We present the minimax algorithm, which is used to determine an optimal move in two-player games, and optimize it using alpha-beta pruning. The approach is implemented in Python, where we analyze the algorithm's performance using the example of the game tic-tac-toe. DFS krepka povezanost Tarjanov algoritem Kosaraju-Sharirjev algoritem minimax alfa-beta obrezovanje teorija iger Python. DFS strong connectivity Kosaraju-Sharir algorithm Tarjan algorithm minimax alpha-beta pruning game theory Python. true true false [M. Galun] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-06-13 15:20:02 2025-07-10 11:12:43 2025-07-11 03:29:21 0000-00-00 00:00:00 2025 0 Maribor 0 Maribor VIII, 51 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 242077187 MAG_Galun_Masa_2025.pdf MAG_Galun_Masa_2025.pdf 1 BE2456D079BA8A71C54BAC5BC5A44186 5754eb0435531661064c659e4f1e7c66432d55b022d905f52f4d25be38fb6ba5 0cf9ce45-485c-11f0-9652-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=192177 Fakulteta za naravoslovje in matematiko 0 0 0