Metrične dimenzije usmerjenih cirkulantnih grafov

slovenski

2026

letnik 13, številka 2

celoštevilsko linearno programiranje   cirkulantni grafi   kardinalnost množice vozlišč   metrična dimenzija grafa

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

Metrična dimenzija grafa predstavlja najmanjšo kardinalnost množice vozlišč, s katero se lahko enolično določi vsa ostala vozlišča grafa glede na njihove razdalje do izbranih vozlišč. V članku je obravnavana metrična dimenzija v smeri urinega kazalca usmerjenih cirkulantnih grafov ?$C(n, d)$?. Najprej je predstavljen celoštevilski linearni program za izračun metrične dimenzije poljubnega usmerjenega grafa ter analiza njegove časovne zahtevnosti. Nato so z računalniškimi eksperimenti izračunane metrične dimenzije grafov ?$C(n, d)$? za ?$n \le 40$? in na podlagi dobljenih rezultatov je oblikovanih več domnev in splošnih lastnosti. Dokazana je formula za razdaljo med poljubnima vozliščema in izraz za premer grafa ?$C(n, d)$? ter izpeljane so splošne zgornje in spodnje meje za metrično dimenzijo. Poleg tega so podane natančne vrednosti metrične dimenzije za nekatere posebne družine grafov, med drugim za ?$C(n, 1)$?, ?$C(n, 2)$?, ?$C(n, n-1)$? in ?$C(n, n-2)$?. Rezultati nakazujejo tesno povezavo med parametroma ?$n$? in ?$d$? ter odpirajo več vprašanj za nadaljnje raziskovanje metrične dimenzije usmerjenih cirkulantnih grafov.

23.09.2026