DISKRIMINATORNE KODE V DVODELNIH GRAFIHKolarič, Denis (Avtor) Kovše, Matjaž (Mentor) identifikacijska kodadiskriminatorna kodadvodelni grafposameznikatributhiperkockadrevoalgoritemravninski grafV uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju in povemo še nekaj o kodah v grafih. V naslednjem poglavju definiramo diskriminatorne kode, podamo nekaj primerov in dokažemo spodnjo in zgornjo mejo za moč minimalne diskriminatorne kode izražene glede na število atributov. V tretjem poglavju pokažemo povezavo med diskriminatornimi in identifikacijskimi kodami v hiperkockah. V četrtem poglavju obravnavamo diskriminatorne kode v drevesih in opišemo algoritem linearne časovne zahtevnosti glede na število vozlišč drevesa, ki za dano drevo poišče minimalno diskriminatorno kodo v drevesu in njegovo delovanje prikažemo na primeru. V zadnjem poglavju podamo za vnaprej podano število atributov konstrukcijo dvodelnih ravninskih grafov brez dvojčkov, ki imajo največje število posameznikov in pokažemo povezavo z ravninskimi triangulacijami.[D. Kolarič]20102010-09-30 16:38:49Diplomsko delo16104UDK: 51(043.2)COBISS_ID: 17925896NUK URN: URN:SI:UM:DK:TH2HL8XHsl