| | 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 - 3 / 3
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: 123; Downloads: 7
.pdf Full text (411,17 KB)

2.
Računanje Wienerjevega indeksa uteženega grafa z združevanjem ?*-razredov
Simon Brezovnik, 2018, master's thesis

Abstract: Wienerjev indeks igra pomembno vlogo pri poznavanju kemijskih in fizikalnih lastnosti različnih spojin. Predstavlja vsoto razdalj med vsemi neurejenimi pari vozlišč znotraj grafa. Uteženi graf je graf skupaj s funkcijo, ki vsakemu vozlišču predpiše realno število, imenovano utež. Magistrsko delo obravnava računanje Wienerjevega indeksa uteženega grafa s pomočjo reduciranja na posebno skupino grafov, tj. kvocientne grafe in nadaljnje redukcije kvocientnih grafov na enostavnejše grafe. V prvem delu predstavimo nekaj osnovnih definicij in ugotovitev teorije grafov. Zapišemo osnovno definicijo Wienerjevega indeksa in njegovo razširitev na utežene grafe. Spoznamo Djoković-Winklerjevo relacijo in njeno tranzitivno zaprtje. Ob koncu prvega dela spoznamo definicijo delne kocke in zapišemo njeno novo karakterizacijo. Osrednji del magistrske naloge podaja novi metodi za izračun Wienerjevega indeksa nekaterih uteženih grafov. Glavni izrek povezuje izračun Wienerjevega indeksa uteženega grafa z vsoto Wienerjevih indeksov uteženih kvocientnih grafov prvotnega grafa po vseh Θ^∗-razredih, kjer Θ^∗ predstavlja tranzitivno zaprtje Djoković-Winklerjeve relacije. V zadnjem delu predstavimo uporabo zgoraj omenjenega izreka na posebni družini grafov G_n, na benzenoidnih sistemih ter na linearnih fenilenih F_n.
Keywords: Wienerjev indeks, delna kocka, uteženi graf, kvocientni graf, Djoković-Winklerjeva relacija, tranzitivno zaprtje
Published: 24.09.2018; Views: 432; Downloads: 96
.pdf Full text (1,00 MB)

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