I grafteori er en delvis terning en undergraf af en hyperkube , der bevarer afstande (i form af grafer) - afstanden mellem to vilkårlige hjørner af undergrafen er den samme som i den originale graf [1] . Tilsvarende er en delvis terning en graf, hvis hjørner kan mærkes med bitstrenge af samme længde, således at afstanden mellem to spidser i grafen er lig med Hamming-afstanden mellem de to etiketter. Denne markering kaldes Hamming-markeringen , og den repræsenterer en isometrisk indlejring af en delvis terning i en hyperkube.
V. Firsov [2] var den første til at studere isometriske indlejringer af grafer i hyperkuber. Grafer, der tillader sådanne indlejringer, blev beskrevet af D. Djokovic [3] og P. Winkler [4] og blev senere kaldt "delkuber". En uafhængig forskningslinje om de samme strukturer i terminologien af familier af sæt , snarere end mærkning af hyperkuber, blev udviklet blandt andre af V. Kuzmin og S. Ovchinnikov [5] samt Falmagnet og Doinon [6] [7] .
Ethvert træ er en delvis terning. Antag, at et træ T har m kanter, og antallet af disse kanter (i vilkårlig rækkefølge) fra 0 til m − 1. Vi vælger et vilkårligt rodpunkt r til træet og tildeler hvert hjørne v en etiket (bitstreng) m bits lang, som indeholder 1 ved position i , hvis kant i ligger på stien fra r til v i træ T . For eksempel vil selve toppunktet r have en etiket med nuller, og alle de hjørner, der støder op til det, vil have et 1 i samme position, og så videre. Så vil Hamming-afstanden mellem to etiketter være lig med afstanden mellem de tilsvarende hjørner af træet, så denne mærkning viser, at træet T er en delvis terning.
Enhver hyperkubegraf er i sig selv en delvis terning, som kan markeres med forskellige bitstrenge med en længde svarende til hyperkubens dimension.
Mere komplekse eksempler:
Mange teoremer om partielle terninger er baseret direkte eller indirekte på en eller anden binær relation defineret på grafens kanter. Dette forhold, først beskrevet af Djokovic [3] , er betegnet med . Winkler gav en tilsvarende definition af forholdet med hensyn til afstand [4] . To kanter og er i relation (skrevet ) hvis . Denne relation er refleksiv og symmetrisk , men generelt set ikke transitiv .
Winkler viste, at en forbundet graf er en delvis terning, hvis og kun hvis den er todelt og relationen er transitiv [12] [13] . I dette tilfælde danner relationen en ækvivalensrelation , og hver ækvivalensklasse adskiller to forbundne undergrafer af grafen fra hinanden. En Hamming-label kan opnås ved at tildele en bit i hver etiket for hver ækvivalensklasse i Djokovic-Winkler-relationen. I en af de to forbundne undergrafer adskilt af en kantækvivalensrelation har etiketter 0 i den tilsvarende position, og i den anden forbundne undergraf har alle etiketter i samme position 1.
Delkuber kan genkendes, og Hamming-markeringen for dem er bygget i tid , hvor er antallet af grafens hjørnepunkter [14] . Givet en delvis terning kan man direkte konstruere Djokovic-Winkler-ækvivalensklasser ved at bruge bredde-først-søgning fra hvert vertex i samlet tid . Genkendelsesalgoritmen fremskynder søgningen over tid ved at bruge parallelitet på bitniveau til at udføre flere bredde-først-søgninger i et enkelt grafpassage, og derefter bruge en separat algoritme til at kontrollere, at resultatet er et gyldigt delvist terninglayout.
Den isometriske dimension af en delvis terning er minimumsdimensionen af en hyperkube, hvori en graf kan indlejres isometrisk og er lig med antallet af ækvivalensklasser i Djokovic-Winkler-relationen. For eksempel er den isometriske dimension af et træ med hjørner lig med antallet af dets kanter, . Indlejringen af en delvis kube i en hyperkube af denne dimension er unik op til hyperkubesymmetrier [15] [16] .
Enhver hyperkube, og derfor enhver delvis terning, kan isometrisk indlejres i et heltalsgitter , og gitterdimensionen for en delvis terning er minimumsdimensionen af et heltalsgitter, hvori en delvis terning kan indlejres. Dimensionen af gitteret kan vise sig at være væsentlig mindre end den isometriske dimension. For eksempel er det for et træ lig med halvdelen af antallet af blade i træet (afrundet til nærmeste heltal). Dimensionen af et gitter for enhver graf og indlejringen i et gitter med minimumsdimension kan findes i polynomiel tid ved hjælp af en algoritme baseret på at finde den største matchning i en hjælpegraf [17] .
Andre typer af partielle terningdimensioner er defineret, baseret på mere specifikke strukturer [18] [19] .
Isometriske indlejringer af grafer i en hyperkube har vigtige anvendelser i kemisk grafteori . En benzoidgraf er en graf, der består af hjørner og kanter, der ligger på en cyklus og inde i en cyklus i et sekskantet gitter . Sådanne grafer er molekylære grafer for benzoidkulbrinter , en stor klasse af organiske molekyler. Hver sådan graf er en delvis terning. Hamming-mærkningen af en sådan graf kan bruges til at beregne Wiener-indekset for det tilsvarende molekyle, som kan bruges til at forudsige nogle kemiske egenskaber [20] . En anden molekylær struktur dannet af kulstof, strukturen af diamant , svarer også til partielle terninger [18] .