| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:KARTEZIČNI PRODUKT GRAFOV
Authors:Merkač, Iris (Author)
Žigert, Petra (Mentor) More about this mentor... New window
Files:.pdf UNI_Merkac_Iris_2009.pdf (411,17 KB)
MD5: 1F90BF8DCCEB4271ED219BB72362A37D
 
Language:Slovenian
Work type:Undergraduate thesis (m5)
Typology:2.11 - Undergraduate Thesis
Organization:FF - Faculty of Arts
Abstract: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 Θ.
Keywords:kartezični produkt, hiperkocke, delne kocke, Hammingovi grafi, relacija Θ, kvocientni graf, kanonična vložitev
Year of publishing:2009
Publisher:[I. Merkač]
Source:Maribor
UDC:51(043.2)
COBISS_ID:17090056 New window
NUK URN:URN:SI:UM:DK:5I2WSZDN
Views:125
Downloads:8
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FF
FNM
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:THE CARTESIAN PRODUCT OF GRAPHS
Abstract: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.
Keywords:the Cartesian product, hypercubes, partial cubes, Hamming graphs, relation Θ, quotient graph, canonical embedding


Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica