20.500.12556/DKUM-11484 KARTEZIČNI PRODUKT GRAFOV THE CARTESIAN PRODUCT OF GRAPHS 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čih 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čih 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 Θ. 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. kartezični produkt hiperkocke delne kocke Hammingovi grafi relacija Θ kvocientni graf kanonična vložitev the Cartesian product hypercubes partial cubes Hamming graphs relation Θ quotient graph canonical embedding true true false [I. Merkač] Slovenski jezik Angleški jezik Diplomsko delo 2009-08-27 19:42:27 2021-01-27 17:24:37 2022-04-11 23:53:44 2022-04-18 03:14:28 2009 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 17090056 URN:SI:UM:DK:5I2WSZDN UNI_Merkac_Iris_2009.pdf UNI_Merkac_Iris_2009.pdf 1 1F90BF8DCCEB4271ED219BB72362A37D 853782f569d7811e0bed36e4d7b725de968dc79615541c4c8d7a40d90ef918f3 2297931a-7c03-11eb-bb7a-00155d0001ca 20.500.12556/dkum/20bee3ec-5275-4003-8188-6aa2fbe74c13 https://dk.um.si/Dokument.php?lang=slv&id=10226 Filozofska fakulteta 0 0 0