| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
KARTEZIČNI PRODUKT GRAFOV
Iris Merkač, 2009, undergraduate thesis

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
Published: 27.01.2021; Views: 225; Downloads: 16
.pdf Full text (411,17 KB)

Search done in 0.01 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica