Diskriminatorne kode v dvodelnih grafih

diplomsko delo

Denis Kolarič (Avtor), Matjaž Kovše (Mentor)

Povzetek

V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju in povemo tudi 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.

Ključne besede

matematika;grafi;dvodelni grafi;kode;identifikacija;diskriminatorne kode;posamezniki;atributi;hiperkocke;drevesa;algoritmi;ravninski grafi;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2010
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[D. Kolarič]
UDK:	51(043.2)
COBISS:	17925896
Št. ogledov:	2311
Št. prenosov:	194
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	DISCRIMINATING CODES IN BIPARTITE GRAPH
Sekundarni povzetek:	In the preliminaries we give necessary definitions from graph theory and codes in graphs that we need later. In the next chapter we define discriminating codes, give some examples and show lower and upper bounds for the size of minimal discriminating codes, expressed in terms of the number of atributes of a given graph. In the third chapter we show the relation between discriminating and identifying codes in hypercubes. In the fourth chapter discriminating codes in trees are treated and linear time algorithm for finding a minimal discriminating code in a tree is given and ilustrated with an example. In the last chapter we describe all bipartite planar graphs without twins with a property, that for a given number of atributes they have the maximal number of individuals, and we show their relation with planar triangulations.
Sekundarne ključne besede:	identifying code;discriminating code;bipartite graph;individual;atribute;hypercube;tree;algorithm;planar graph;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	60 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	18845