VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Convex drawings of the complete graph: topology meets geometry
    Arroyo, Alan ...
    V geometrijski risbi grafa ▫$K_n$▫, trivialno vsak 3-cikel omejuje konveksno območje: če sta dva vozlišča v tem območju, potem to velja tudi za (geometrijsko) povezavo med njima. Za topološko risbo ... ▫$D$▫ grafa ▫$K_n$▫ na sferi rečemo, da je konveksna, če vsak 3-cikel omejuje zaprto območje ▫$R$▫ (na katerikoli od dveh strani 3-cikla), pri tem pa imata poljubna dva vozlišča v ▫$R$▫ (topološko) povezavo med njima vsebovano v ▫$R$▫. Konveksne risbe po eni strani posplošujejo geometrijske risbe, po drugi strani pa so poddružina topoloških risb. Zato bi bilo lahko presenetljivo, če bi bile vse optimalne (to je, z minimalnim številom presečišč) topološke risbe grafa ▫$K_n$▫ konveksne. Vseeno pa storimo prvi korak k dokazu, da so konveksne: pokažemo, da če ▫$D$▫ vsebuje nekonveksen ▫$K_5$▫, vse njegove razširitve do ▫$K_7$▫ pa ne vsebujejo nobenega drugega nekonveksnega ▫$K_5$▫, potem ▫$D$▫ ni optimalen (brez sklicevanja na domnevo o številu presečišč grafa ▫$K_n$)▫. To je prvi primer netrivialnih lokalnih argumentov, ki dajejo zadostne pogoje za suboptimalnost. Na našo prošnjo je Aichholzer računalniško potrdil, da je, vse do ▫$n = 12$▫, vsaka optimalna risba grafa ▫$K_n$▫ konveksna. Konveksnost naravno dopušča izpopolnitve, kot sta npr. lastnosti hereditarno konveksen (▫$h$▫-konveksen) in lično konveksen (▫$f$▫-konveksen). Hierarhija premočrten ▫$\subseteq$▫ ▫$f$▫-konveksen ▫$\subseteq$▫ ▫$h$▫-konveksen ▫$\subseteq$▫ konveksen ▫$\subseteq$▫ topološki opisuje relacije med geometrijskimi in topološkimi risbami. Znano je, da je ▫$f$▫-konveksnost ekvivalentna psevdolinearnosti (ki posplošuje premočrtnost) in da je ▫$h$▫-konveksnost ekvivalentna psevdosferičnosti (ki posplošuje sferično geodetskost). Karakteriziramo ▫$h$▫-konveksnost s tremi prepovedanimi (topološkimi) podrisbami. Ta hierarhija predstavlja okvir za obravnavo posplošitev tudi drugih geometrijskih problemov v zvezi z množicami točk v ravnini. Predstavimo dva primera takšnih problemov, in sicer o številu odprtih trikotnikov ter o obstoju konveksnih ▫$k$▫-kotnikov.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 22, no. 3, 2022, #P3.04 (str. 415-441))
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2022
    Jezik - angleški
    COBISS.SI-ID - 117983491

    Povezava(-e):

    https://amc-journal.eu/index.php/amc/article/download/2134/1739
    Digitalna knjižnica Slovenije - dLib.si
    DOI

vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 22, no. 3, 2022, #P3.04 (str. 415-441))
loading ...
loading ...
loading ...

Vnos na polico