Delvis terning

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.

Historie

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] .

Eksempler

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:

Betragt en graf, hvis toppunkter består af alle mulige bitstrenge med længden 2n + 1 , der har enten n eller n + 1 bit, der ikke er nul. To hjørner af denne graf er tilstødende, hvis deres etiketter adskiller sig med en enkelt bit. Denne markering definerer en indlejring af denne graf i en hyperkube (en graf af alle bitstrenge af en given længde med samme tilstødende betingelse). Den resulterende graf er en todelt Kneser-graf . Den således opnåede graf med n = 2 har 20 hjørner og 30 kanter og kaldes Desargues grafen .
Alle mediangrafer er partielle terninger [8] . Træer og hyperkuber er specielle tilfælde af mediangrafer. Da mediangrafer inkluderer rammegrafer , simpleksgrafer , og Fibonacci-terninger , såvel som dækkende grafer af endelige fordelingsgitter , er de alle partielle terninger.
Grafer dobbelt til linjekonfigurationer i det euklidiske plan er delvise terninger. Mere generelt, for enhver konfiguration af hyperplaner i det euklidiske rum af enhver dimension, er en graf, der har et toppunkt for hver celle i konfigurationen og en kant for to tilstødende celler, en delvis terning [9] .
En delvis terning, hvor hvert hjørne har præcis tre naboer, er kendt som en kubisk delvis terning. Selvom nogle uendelige familier af kubiske partielle terninger er kendt, sammen med andre sporadiske eksempler, er den eneste kendte kubiske partielle terning, som ikke er plan , Desargues-grafen [10] .
Den underliggende graf for enhver antimatroid , der har et toppunkt for hvert sæt i antimatroiden og en kant for alle to sæt, der adskiller sig med et enkelt element, er altid en delvis terning.
Det direkte produkt af ethvert endeligt sæt af partielle terninger er en anden partiel terning [11] .

Djokovic-Winkler-forholdet

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 . $\Theta$ $e=\{x,y\}$ $f=\{u,v\}$ $\Theta$ $e{\mathrel {\Theta }}f$ $d(x,u)+d(y,v)\ikke =d(x,v)+d(y,u)$

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. $\Theta$

Anerkendelse

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. $O(n^{2})$ $n$ $O(nm)$ $O(n^{2})$

Dimension

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] . $n$ $n-1$

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] .

Anvendelser til kemisk grafteori

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] .

Noter

↑ Ovchinnikov, 2011 , s. 127, Definition 5.1.
↑ Firsov, 1965 .
↑ 1 2 Djokovic, 1973 .
↑ 12 Winkler , 1984 .
↑ Kuzmin, Ovchinnikov, 1975 .
↑ Falmagne, Doignon, 1997 .
↑ Ovchinnikov, 2011 , s. 174.
↑ Ovchinnikov, 2011 , s. 163–165, afsnit 5.11, "Mediangrafer".
↑ Ovchinnikov, 2011 , s. 207–235, kapitel 7, "Hyperplanarrangementer".
↑ Eppstein, 2006 .
↑ Ovchinnikov, 2011 , s. 144–145, afsnit 5.7, "Kartesiske produkter af delvise terninger".
↑ Winkler, 1984 , s. Sætning 4.
↑ Ovchinnikov, 2011 , s. 29, 139, definition 2.13, sætning 5.19.
↑ Eppstein, 2008 .
↑ Ovchinnikov, 2011 , s. 142–144, afsnit 5.6, "Isometrisk dimension".
↑ Ovchinnikov, 2011 , s. 157–162, afsnit 5.10, "Unikhed af isometriske indlejringer".
↑ Hadlock, Hoffman, 1978 ; Eppstein, 2005 ; Ovchinnikov, 2011 , kapitel 6, "Gitterindlejringer", s. 183–205.
↑ 12 Eppstein , 2009 .
↑ Cabello, Eppstein, Klavžar, 2011 .
↑ Klavžar, Gutman, Mohar, 1995 , forslag 2.1 og 3.1; Imrich, Klavžar, 2000 , s. 60; Ovchinnikov, 2011 , afsnit 5.12, "Gennemsnitlig længde og Wienerindekset", s. 165–168.

Litteratur

S. Cabello, D. Eppstein, S. Klavžar. Fibonacci-dimensionen af en graf // Electronic Journal of Combinatorics. - 2011. - T. 18 , no. 1 . - arXiv : 0903.2507 .
D.z. Djokovic. Afstandsbevarende undergrafer af hyperkuber // Journal of Combinatorial Theory . - 1973. - T. 14 , no. 3 . — S. 263–267 . - doi : 10.1016/0095-8956(73)90010-5 .
David Eppstein. Gitterdimensionen af en graf // European Journal of Combinatorics. - 2005. - T. 26 , no. 6 . — S. 585–592 . - doi : 10.1016/j.ejc.2004.05.001 . - arXiv : cs.DS/0402028 .
David Eppstein. Kubiske delterninger fra simple arrangementer // Electronic Journal of Combinatorics. - 2006. - T. 13 , no. 1 . - arXiv : math.CO/0510263 .
David Eppstein. Proc. 19. ACM-SIAM-symposium om diskrete algoritmer. - 2008. - S. 1258-1266.
David Eppstein. Proc. 16. internationale symposium om graftegning, Heraklion, Kreta, 2008 . - Springer-Verlag, 2009. - T. 5417. - S. 384-389. — (Forelæsningsnotater i datalogi). - doi : 10.1007/978-3-642-00219-9_37 .
J.-C. Falmagne, J.-P. Doignon. Stokastisk udvikling af rationalitet // Teori og beslutning. - 1997. - T. 43 . — s. 107–138 . - doi : 10.1023/A:1004981430688 .
Firsov VV Om isometrisk indlejring af en graf i en boolsk terning // Kybernetik. - 1965. - Udgave. 6 . - S. 95-96 .
F. Hadlock, F. Hoffman. Manhattan træer // Utilitas Mathematica. - 1978. - T. 13 . — s. 55–67 . Som citeret i ( Ovchinnikov 2011 ).
Wilfried Imrich, Sandi Klavzar. Produktgrafer: Struktur og anerkendelse. - John Wiley & Sons, 2000. - (Wiley-Interscience Series in Discrete Mathematics and Optimization). - ISBN 978-0-471-37039-0 .
Sandi Klavžar, Ivan Gutman, Bojan Mohar. Mærkning af benzenoidsystemer, som afspejler toppunkt-afstandsrelationerne // Journal of Chemical Information and Computer Sciences. - 1995. - T. 35 , no. 3 . — S. 590–593 . doi : 10.1021 / ci00025a030 .
V. B. Kuzmin, S. V. Ovchinnikov. Geometrien af præferencerum. I // Automation og telemekanik. - 1975. - Udgave. 12 . - S. 140-145 .
Sergei Ovchinnikov. grafer og kuber. - 2011. . Se kapitel 5, Partial Cubes, s. 127–181.
Peter M Winkler. Isometrisk indlejring i produkter af komplette grafer // Diskret anvendt matematik. - 1984. - T. 7 , no. 2 . — S. 221–225 . - doi : 10.1016/0166-218X(84)90069-6 .