20.500.12556/RUL-184957 Prirejanja v kemijskih grafih in njihova preštevanja magistrsko delo Matchings in chemical graphs and their counting Delo obravnava štetje prirejanj v grafih s poudarkom na njihovi uporabi v kemijski teoriji grafov, kjer prirejanja ustrezajo Kekuléjevim strukturam molekul in določajo njihovo aromatsko stabilnost. Glavni problem je izračun Hosoyevega indeksa, ki je pomemben molekulski deskriptor fizikalno-kemijskih lastnosti spojin. Ker je štetje prirejanj v splošnih grafih računsko zahtevno, saj problem štetja popolnih prirejanj in posledično splošnih $k$-prirejanj) sodi v razred #P-polnih problemov, se delo osredotoča na specifične razrede grafov. Z učinkovitimi metodami, med katerimi osrednjo vlogo igra metoda prenosnih matrik, lahko za te razrede izračunamo Hosoyev indeks v polinomskem času. Te metode preko rekurzivnih zvez omogočajo izračun Hosoyevega indeksa za kompleksne grafe, take so benzenoidne in koronoidne verige, ciklični sistemi ter zaporedno amalgamirani grafi. The thesis examines the counting of matchings in graphs, focusing on their application in chemical graph theory, where matchings correspond to the Kekulé structures of molecules and determine their aromatic stability. The primary objective is the calculation of the Hosoya index, a molecular descriptor that encodes structural information relevant to the physicochemical properties of compounds. Since counting matchings in general graphs is computationally hard, as the problem of counting perfect matchings (and consequently general $k$-matchings) belongs to the class of #P-complete problems, the work focuses on specific graph classes. Using efficient methods, among which the transfer matrix method plays a central role, the Hosoya index for these classes can be computed in polynomial time. Through recursive relations, these methods enable calculation of the Hosoya index for complex graphs, such as benzenoid and coronoid chains, cyclic systems, and successively amalgamated graphs. kemijska teorija grafov prirejanje štetje prirejanj Hosoyev indeks $k$-prirejanje metoda prenosnih matrik chemical graph theory matching counting matchings Hosoya index $k$-matching transfer matrix method true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2026-07-18 08:15:27 2026-07-18 08:15:31 2026-07-28 14:34:30 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 160693 285044483 21981.pdf 21981.pdf 1 2E29DB551ED176555F17E73419105C4D 085ac39ca11419d0c39f4056a5ed13222644b9ca47dfd85587b5afca84a08a97 dcf72fe3-826f-11f1-9b0d-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=240418 Fakulteta za matematiko in fiziko 0 0 0