20.500.12556/DKUM-17919 ADAPTIVNA IDENTIFIKACIJA V GRAFIH ADAPTIVE IDENTIFICATION IN GRAPHS Diplomsko delo obravnava adaptivne identifikacijske kode v grafih, ki so povezane z identi- fikacijskimi kodami. Pri tem obravnavamo problem, kjer fizelimo odkriti okvarjeno vozlišče v grafu tako, da postavljamo vprašanja ali neka krogla vsebuje okvarjeno vozlišče. Cilj adaptivnih identifikacijskih kod je minimizirati število vprašanj, ki so potrebna za odkritje okvarjenega vozlišča, če slednje obstaja. To število označimo z ar(G). V uvodnem poglavju definiramo osnovne pojme iz teorije grafov in kod v grafih, ki jih uporabljamo v nadaljevanju. V drugem poglavju določimo zgornjo in spodnjo mejo za število ar(G) v regularnih grafih. V podpoglavjih omejimo število ar(G) v kvadratni, kral- jevi in trikotni mreži. Ob tem obravnavamo tudi primere, ko je okvarjenih več vozlišč. V tretjem poglavju predstavimo igro Renyijevega tipa, kjer iščemo neznano točko (x; y) v pravokotni mreži s postavljanjem vprašanj glede na podpravokotnike. Pri tem je cilj minimizirati število vprašanj. Pri tem uporabimo drevesno in linearno iskanje. In this thesis, we consider adaptive identification, which is closely connected with identifying codes in graphs. We are able to ask if there is a faulty vertex in the ball Br(x). The goal in adaptive identification is to minimize the maximum number of queries, which are necessary to discover the faulty vertex, if it exists. We denote by ar(G) this optimum number. In the initial section we give necessary definitions from graph theory and codes in graphs that we need later. In second section we show the lower and upper bound for the parameter ar(G) in regular graphs. In the subsections we limit the number ar(G) in square, king and triangular lattice. We also consider the cases, where there can be l faulty vertices, for l>1. In third section we present Renyi type of game, where we are looking for unknown point (x; y) in rectangle lattice by posing questions to subrectangles. Our goal here is also to minimize the number of queries. For this we use tree and linear search. identifikacijska koda adaptivna identifikacija popolna koda pokrivna koda linearno iskanje drevesno iskanje identifying code adaptive identification perfect code covering code linear search tree search true true false [P. Stanet] Slovenski jezik Angleški jezik Diplomsko delo 2011-03-30 12:07:36 2011-04-06 14:13:12 2022-04-13 10:16:14 2023-12-23 03:14:15 2011 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 18258440 URN:SI:UM:DK:OZMAINM5 UNI_Stanet_Peter_2011.pdf UNI_Stanet_Peter_2011.pdf 1 A9004B241DAE21CF4C54A05076C41ADF 19e04dfe4ff3d521f86a253f32290cc3c6ebecdde3e54663989f43b2a75eb5d5 0166386f-7c05-11eb-bb7a-00155d0001ca 20.500.12556/dkum/99419c3f-8035-404e-be69-ab8e6367c221 https://dk.um.si/Dokument.php?lang=slv&id=21151 Fakulteta za naravoslovje in matematiko 0 0 0