Posplošeni latinski kvadrati

diplomsko delo

Boštjan Pogač (Author), Petra Žigert Pleteršek (Mentor)

Abstract

Posplošeni latinski kvadrat reda n je n % n tabela števil 1, 2, 3, % , k, taka, da se vsako število pojavi le enkrat v vsaki vrstici in le enkrat v vsakem stolpcu. Naj L(n,k) označuje množico vseh posplošenih latinskih kvadratov tipa (n,k). Posplošeni latinski kvadrat tipa (n,k) je n x n kvadrat, ki je pobarvan s k barvami označenimi z 1, 2, % , k, ta%ko, da se nobena barva ne pojavi dvakrat v vrstici ali stolpcu. Takšno barvanje imenujemo k-barvanje. Določitvena množica k-barvanja kvadrata reda n je množica pobarvanih celic tega n x n kvadrata takih, da lahko k-barvanje enolično razširimo do kvadrata iz L(n,k). Določitveno število, označeno z d(n,k), je moč najmanjše določitvene množice. Barvanje kvadrata je poimenovano delno barvanje, če niso vse celice kvadrata nujno pobarvane. Celice, ki jim delno barvanje ni pripisano, so nepobarvane. Delno barvanje je enolično razširljivo do L(n,k), če je obstaja natanko ena pot do razširitve kvadrata iz L(n,k).

Keywords

matematika;posplošeni kvadrati;latinski kvadrati;določitveno število;delno barvanje;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2009
Source:	Muta
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[B. Pogač]
UDC:	51(043.2)
COBISS:	16820488
Views:	2940
Downloads:	199
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Generalized Latin squares
Secondary abstract:	A generalized Latin square of type (n,k) is an n x n array of symbols 1, 2, %, k such that each of these symbols occurs at most once in each row and each column. Let L(n,k) denote the set of all generalized Latin squares of type (n,k). Let d(n,k) denote the cardinality of the minimal set S of given entries of an n x n array such that there exist a unique extension of S to a generalized Latin square of type (n,k). A coloring of a square is called partial coloring if not all of the cells of the square are necessarily colored. The cells to which the partial coloring does not assign a color are said to be uncolored. A partial coloring is said to extend to L(n,k) if there is a way to color the uncolored cells of given n x n square such that the resulting entirely colored square is in L(n,k). A partial coloring uniquely extends to L(n,k) (can be uniquely extended) if there is exactly one way to extend it to a square in L(n,k).
Secondary keywords:	Generalized Latin squares;minimum defining set d(n;k);partial coloring.;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	66 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	17725