Nacionalni portal odprte znanosti

Problem splošne lege v grafih je poiskati največjo možno množico vozlišč z lastnostjo, da nobena tri od njih ne ležijo na skupni najkrajši poti. Problem medsebojne vidnosti v grafih je najti največje število vozlišč, ki jih je mogoče izbrati tako, da ima vsak par vozlišč najkrajšo pot med seboj, pri ...

Za lepljena dvojiška drevesa so določene vse štiri invariante problema vzajemne vidnosti in vse štiri invariante problema splošne lege. Število ustreznih ekstremnih množic je pridobljeno v vseh osmih primerih. Rezultati so nadalje razširjeni na lepljena ▫$t$▫-arna drevesa, nekateri pa tudi na splošn ...

Raznolikost problemov vzajemne vidnosti obsega štiri elemente, enako kot raznolikost problemov splošne lege. Osnovni problem je določiti število elementov največjih takšnih množic. V tem članku je teh osem invariant preučevanih na grafih Sierpińskega ▫$S_p^n$▫. Določene so za grafe ▫$S_p^2$▫, ▫$p\ge ...

Če je ▫$x\in V(G)$▫, potem je ▫$S\subseteq V(G)\setminus\{x\}$▫ množica ▫$x$▫-vidnosti, če za vsak ▫$y\in S$▫ obstaja najkrajša ▫$x,y$▫-pot, ki se izogiba ▫$S$▫. Število ▫$x$▫-vidnosti ▫$v_x(G)$▫ je največja kardinalnost množice ▫$x$▫-vidnosti, največja vrednost ▫$v_x(G)$▫ med vsemi vozlišči ▫$x$▫ g ...