Delvis kub - Partial cube

I grafteorin är en partiell kub en graf som är isometrisk till en undergraf av en hyperkub . Med andra ord kan en partiell kub identifieras med en subgraf av en hyperkub på ett sådant sätt att avståndet mellan två hörn i delkuben är samma som avståndet mellan dessa hörn i hyperkuben. På motsvarande sätt är en partiell kub en graf vars hörn kan märkas med bitsträngar av lika längd på ett sådant sätt att avståndet mellan två hörn i diagrammet är lika med Hamming-avståndet mellan deras etiketter. En sådan märkning kallas en Hamming-märkning ; den representerar en isometrisk inbäddning av den partiella kuben i en hyperkub.

Historia

Firsov (1965) var den första som studerade isometriska inbäddningar av grafer i hyperkuber. Diagrammen som medger sådana inbäddningar kännetecknades av Djoković (1973) och Winkler (1984) och fick senare delkuber. En separat forskningslinje om samma strukturer, i terminologin för familjer av uppsättningar snarare än av hyperkubmärkning av grafer, följdes av bland andra Kuzmin & Ovchinnikov (1975) och Falmagne & Doignon (1997) .

Exempel

Ett exempel på en partiell kub med en Hamming-märkning på sina hörn. Denna graf är också en mediangraf .

Varje träd är en delvis kub. Antag att ett träd T har m- kanter och numrerar dessa kanter (godtyckligt) från 0 till m  - 1. Välj en rotkod r för trädet, godtyckligt och märk varje toppunkt v med en sträng av m- bitar som har en 1 i läge i närhelst kant i ligger på vägen från r till v i T . Till exempel kommer r i sig att ha en etikett som alla är nollbitar, dess grannar kommer att ha etiketter med en enda 1-bit, etc. Då är Hamming-avståndet mellan två etiketter avståndet mellan de två topparna i trädet, så detta märkning visar att T är en partiell kub.

Varje hyperkubdiagram är i sig en partiell kub, som kan märkas med alla olika bitsträngar som är lika med dimensionen hos hyperkuben.

Mer komplexa exempel inkluderar följande:

• Tänk på diagrammet vars vertexetiketter består av alla möjliga (2 n + 1) -siffriga bitsträngar som har antingen n eller n + 1 icke-nollbitar, där två hörn är intill när deras etiketter skiljer sig med en enda bit. Denna märkning definierar en inbäddning av dessa grafer i en hyperkub (diagrammet för alla bitsträngar av en viss längd, med samma angränsningsförhållande) som visar sig vara distansbevarande. Den resulterande grafen är en tvåparts Kneser-graf ; grafen som bildas på detta sätt med n = 2 har 20 hörn och 30 kanter, och kallas Desargues-grafen .
• Alla mediandiagram är delvisa kuber. Träd och hyperkubdiagram är exempel på mediandiagram. Eftersom median grafer innefattar squaregraphs , simplex grafer och Fibonacci kuber , såväl som de täckande grafer av ändliga distributiva gitter , dessa är alla partiella kuber.
• Den plana dubbla grafen för ett linjearrangemang i det euklidiska planet är en partiell kub. Mer allmänt, för varje hyperplanarrangemang i euklidiskt utrymme med valfritt antal dimensioner, är diagrammet som har ett toppunkt för varje cell i arrangemanget och en kant för varje två intilliggande celler en partiell kub.
• En partiell kub där varje toppunkt har exakt tre grannar kallas en kubisk delkub. Även om flera oändliga familjer av kubiska partikuber är kända, tillsammans med många andra sporadiska exempel, är den enda kända kubiska partiella kuben som inte är en plan graf Desargues-grafen.
• Den underliggande grafen för vilken antimatroid som helst , med ett toppunkt för varje uppsättning i antimatroid och en kant för varje två uppsättningar som skiljer sig åt med ett enda element, är alltid en partiell kub.
• Den kartesiska produkten av alla ändliga uppsättningar partiella kuber är en annan partiell kub.
• En underindelning av en komplett graf är en partiell kub om och bara om antingen varje fullständig grafkant är indelad i en tvåkantig bana, eller om det finns ett komplett diagramverktyg vars infallande kanter är ouppdelade och alla icke-infallande kanter har delats upp i jämna längder.

Relationen Djoković – Winkler

Många av satserna om partiella kuber baseras direkt eller indirekt på ett visst binärt förhållande definierat i kanterna av diagrammet. Detta förhållande, först beskrivet av Djoković (1973) och ges en motsvarande definition i termer av avstånd av Winkler (1984) , betecknas med  . Två kanter och definieras som i relationen  , skriven , om . Denna relation är reflexiv och symmetrisk , men i allmänhet är den inte övergående . ${\ displaystyle \ Theta}$${\ displaystyle e = \ {x, y \}}$${\ displaystyle f = \ {u, v \}}$${\ displaystyle \ Theta}$${\ displaystyle e {\ mathrel {\ Theta}} f}$${\ displaystyle d (x, u) + d (y, v) \ not = d (x, v) + d (y, u)}$

Winkler visade att en ansluten graf är en partiell kub om och bara om den är bipartit och förhållandet  är övergående. I det här fallet bildar det en ekvivalensrelation och varje ekvivalensklass skiljer två anslutna underbilder av grafen från varandra. En Hamming-märkning kan erhållas genom att tilldela en bit av varje etikett till var och en av ekvivalensklasserna i förhållandet Djoković – Winkler; i en av de två anslutna underbilderna åtskilda av en ekvivalensklass av kanter har alla hörnpunkterna ett 0 i den positionen på sina etiketter, och i den andra anslutna undergraferna har alla hörn en 1 i samma position. ${\ displaystyle \ Theta}$

Erkännande

Partiella kuber kan kännas igen och en Hamming-märkning konstrueras i  tid, var  är antalet hörn i diagrammet. Med en partiell kub är det enkelt att konstruera ekvivalensklasserna i förhållandet Djoković – Winkler genom att göra en första breddsökning från varje toppunkt, totalt tid ; den -time igenkänningsalgoritm snabbar detta upp genom att använda bit-nivå parallellism att utföra flera bredd första sökningar i en enda passage genom grafen, och sedan applicerar en separat algoritm för att verifiera att resultatet av denna beräkning är en giltig partiell kub märkning. ${\ displaystyle O (n ^ {2})}$${\ displaystyle n}$${\ displaystyle O (nm)}$${\ displaystyle O (n ^ {2})}$

Dimensionera

Den isometriska dimensionen för en partiell kub är den minsta dimensionen för en hyperkub på vilken den kan vara isometriskt inbäddad och är lika med antalet ekvivalensklasser i förhållandet Djoković-Winkler. Till exempel isometrisk dimension ett är -vertex träd sitt antal kanter . En inbäddning av en partiell kub i en hyperkub av denna dimension är unik, upp till symmetrierna hos hyperkuben. ${\ displaystyle n}$${\ displaystyle n-1}$

Varje hyperkub och därmed varje partiell kub kan inbäddas isometriskt i ett helgitter . Den gitterdimension av en kurva är den minimala dimensionen för ett heltal gitter in i vilken grafen kan isometriskt inbäddade. Gitterdimensionen kan vara betydligt mindre än den isometriska dimensionen; för ett träd är det till exempel hälften av antalet löv i trädet (avrundat upp till närmaste heltal). Gitterdimensionen för vilken graf som helst och en gitterinbäddning av minsta dimension kan hittas i polynomtid av en algoritm baserad på maximal matchning i ett hjälpdiagram.

Andra typer av dimensioner av partiella kuber har också definierats, baserat på inbäddning i mer specialiserade strukturer.

Tillämpning på kemisk grafteori

Isometriska inbäddningar av grafer i hyperkuber har en viktig tillämpning i kemisk grafteori . En benzenoidgraf är en graf som består av alla hörn och kanter som ligger på och i det inre av en cykel i ett sexkantigt galler . Sådana grafer är molekyldiagrammen för bensenoidkolvätena , en stor klass av organiska molekyler. Varje sådan graf är en delvis kub. En Hamming-märkning av en sådan graf kan användas för att beräkna Wiener-index för motsvarande molekyl, som sedan kan användas för att förutsäga vissa av dess kemiska egenskaper.

En annan molekylär struktur bildad av kol, diamantkubik , bildar också partiella kubdiagram.

Anteckningar

Referenser

• Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Isometriska inbäddningar av uppdelade kompletta grafer i hypercube" (PDF) , SIAM Journal on Discrete Mathematics , 22 (3): 1226–1238, doi : 10.1137 / 070681909 , MR  2424849
• Cabello, S .; Eppstein, D .; Klavžar, S. (2011), "The Fibonacci dimension of a graph", Electronic Journal of Combinatorics , 18 (1), P55, arXiv : 0903.2507 , Bibcode : 2009arXiv0903.2507C , doi : 10.37236 / 542.
• Djoković, Dragomir Ž. (1973), "Distansbevarande underbilder av hyperkuber", Journal of Combinatorial Theory , serie B, 14 (3): 263–267, doi : 10.1016 / 0095-8956 (73) 90010-5 , MR  0314669.
• Eppstein, David (2005), "The gitter dimension of a graph", European Journal of Combinatorics , 26 (6): 585–592, arXiv : cs.DS / 0402028 , doi : 10.1016 / j.ejc.2004.05.001.
• Eppstein, David (2006), "Cubic partial kuber från enkla arrangemang" , Electronic Journal of Combinatorics , 13 (1), R79, arXiv : math.CO/0510263 , doi : 10.37236 / 1105.
• Eppstein, David (2008), "Att känna igen partiella kuber i kvadratisk tid", Proc. 19: e ACM-SIAM-symposiet om diskreta algoritmer , s. 1258–1266, arXiv : 0705.1025 , Bibcode : 2007arXiv0705.1025E.
• Eppstein, David (2009), "Isometric diamond subgraphs", Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008 , Lecture Notes in Computer Science, 5417 , Springer-Verlag, s. 384–389, arXiv : 0807.2218 , doi : 10.1007 / 978-3-642-00219-9_37.
• Falmagne, J.-C. ; Doignon, J.-P. (1997), "Stochastic evolution of rationality", Teori och beslut , 43 (2): 107–138, doi : 10.1023 / A: 1004981430688.
• Firsov, VV (1965), "Om isometrisk inbäddning av en graf i en boolsk kub", Cybernetics , 1 : 112–113, doi : 10.1007 / bf01074705. Som citerats av Ovchinnikov (2011) .
• Hadlock, F .; Hoffman, F. (1978), "Manhattan-träd", Utilitas Mathematica , 13 : 55–67. Som citerats av Ovchinnikov (2011) .
• Imrich, Wilfried; Klavžar, Sandi (2000), Produktdiagram: Structure and Recognition , Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, ISBN 978-0-471-37039-0, MR  1788124.
• Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Märkning av bensenoidsystem som återspeglar vertexdistansrelationerna" (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi : 10.1021 / ci00025a030.
• Kuzmin, V .; Ovchinnikov, S. (1975), "Geometri för preferensrum I", Automation och fjärrkontroll , 36 : 2059–2063. Som citerats av Ovchinnikov (2011) .
• Ovchinnikov, Sergei (2011), Grafer och kuber , Universitext, Springer. Se särskilt kapitel 5, "Partiella kuber", s. 127–181.
• Winkler, Peter M. (1984), "Isometrisk inbäddning i produkter med kompletta grafer", Diskret tillämpad matematik , 7 (2): 221–225, doi : 10.1016 / 0166-218X (84) 90069-6 , MR  0727925.