Vzajemna vidnost in celotna vzajemna vidnost v grafihKastelic, Žan (Avtor) Klavžar, Sandi (Mentor) grafvzajemna vidnostleksikografski produkt grafovkartezični produkt grafovNaj bo $G=(V(G),E(G))$ graf in $X \subseteq V(G)$. Pravimo, da je množica $X$ vzajemno vidna, če za par vozlišč $u,v \in X$ velja, da na najkrajši poti med njima ne leži nobeno drugo vozlišče iz $X$. Vzajemna vidnost grafa $G$ je kardinalna vrednost katerekoli največje vzajemno vidne množice, $\mu(G)=|X|$. Naj bo še $X_t \subseteq V(G)$. Množica $X_t$ je celotno vzajemno vidna, če med poljubnima vozliščema iz $V(G)$ obstaja najkrajša pot, na kateri ne leži vozlišče iz $X_t$. Kardinalnost katerekoli največje celotno vzajemno vidne množice $X_t$ imenujemo celotna vzajemna vidnost grafa $G$, ki jo označimo z $\mu_t(G)=|X_t|$. S pomočjo različnih grafovskih invariant so podane spodnje in zgornje meje za $\mu(G)$ in $\mu_t(G)$. Za nekatere družine grafov in njihove produkte so podane točne vrednosti. Dokazano je, da je problem NP-poln.20252025-02-26 08:15:06Magistrsko delo/naloga167519sl