Kartezični produkt grafov

diplomsko delo

Iris Merkač (Avtor), Petra Žigert Pleteršek (Mentor)

Povzetek

Diplomsko delo je sestavljeno iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in podamo definicije ter osnovne lastnosti kartezičnega produkta dveh ali več grafov. V naslednjem poglavju podamo definiciji hiperkocke in delne kocke, ter spoznamo da so hiperkocke najpreprostejši razred kartezičnega produkta. Nato se posvetimo Djoković-Winklerjevi relaciji Î%, za katero ugotovimo, da je definirana na množici povezav grafa in da je bistvenega pomena za kartezični produkt. Poglavje zaključimo s preprostim algoritmom prepoznavanja hiperkock. V zadnjem poglavju definiramo Hammingove grafe in delne Hammingove grafe. Opazimo tudi, da so hiperkocke edini dvodelni Hammingovi grafi. V nadaljevanju raziščemo kanonično vložitev grafov v kartezični produkt dveh ali več kvocientnih grafov, katere dobimo iz ekvivalenčnih razredov tranzitivne ovojnice relacije Î%. Nato dokažemo Graham-Winklerjev izrek, ki pove, da je kanonična vložitev izometrija. Ker je izračunavanje tranzitivne ovojnice relacije Î% bistveno pri izračunavanju kanonične vložitve, na koncu podamo algoritem, ki izračuna tranzitivno ovojnico relacije Î%.

Ključne besede

matematika;grafi;kartezični produkt;hiperkocke;delne kocke;Hammingovi grafi;kanonična vložitev;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2009
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[I. Merkač]
UDK:	51(043.2)
COBISS:	17090056
Št. ogledov:	340
Št. prenosov:	32
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	THE CARTESIAN PRODUCT OF GRAPHS
Sekundarni povzetek:	The diploma work consists of three chapters. In the first chapter the basic concepts of the graph theory are introduced. Definitions and basic characteristic for the Cartesian product of two or several graphs are presented. In the next chapter the definitions of hypercubes and partial cubes are given, and we realize that hypercubes are the simplest class of Cartesian product. Then the Djoković-Winkler relation is introduced, which is defined on the edge set of the graph and is essential for the Cartesian product. The chapter is concluded with a simple recognition algorithm for hypercubes. In the last chapter Hamming graphs and also partial Hamming graphs are defined. It is also noticed that hypercubes are the only bipartite Hamming graphs. After that canonical embedding of graphs in the Cartesian product of two or several quotient graphs is being investigated, which are obtained from equivalence classes of a transitive closure of a relation. Then a Graham-Winkler Theorem is proven, which indicates that the canonical embedding is an isometry. Since the calculation of a transitive closure of the relation is essential for calculating a canonical embedding at the end an algorithm that calculates the transitive closure of a relation is given.
Sekundarne ključne besede:	the Cartesian product;hypercubes;partial cubes;Hamming graphs;relation Θ;quotient graph;canonical embedding;
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:	X, 49 f.
ID:	12506119