Möbiusstege

Möbiusstegen  är en kubisk cirkulerande graf med ett jämnt antal hörn , bildad från en cykel med hörn genom att lägga till kanter (kallade "steg") som förbinder motsatta par av kretsar. Så uppkallad eftersom den består av cykler med längden 4 [1] som är sammankopplade med gemensamma kanter och topologiskt bildar en Möbiusremsa . Den kompletta tvådelade grafen (" hus och brunnar " graf) är en Möbius-stege (till skillnad från de andra har den ytterligare cykler med längd 4).

Studerades först av Guy och Harari [2] .

Egenskaper

Vilken Möbius-stege som helst är en icke- planär vertexgraf . Antalet korsningar av Möbius-stegen är en, och grafen kan bäddas in utan självkorsningar i ett torus- eller projektivt plan (det vill säga det är en toroidformad graf ). Lee [3] studerade inbäddningen av dessa grafer i ytor av högre genus.

Möbiustrappor är vertextransitiv , men (med undantag för ) inte kanttransitiv  - varje kant på cykeln som stegen bildas av tillhör en enda 4-kantscykel, medan varje stegpong tillhör två sådana cykler.

Om , då är tvådelad . När , enligt Brooks sats , är det kromatiska talet 3. Det är känt [4] att Möbius-stegen bestäms unikt av dess Tatta-polynom .

Möbiusstegen har 392 spännande träd . Denna graf har också det största antalet spännande träd bland kubiska grafer med samma antal hörn [5] [6] . Men bland kubiska grafer med 10 hörn har Petersen-grafen det största antalet spännande träd , vilket inte är en Möbius-stege.

Möbius- stegars Tuttpolynom kan erhållas med en enkel rekursiv formel [7] .

Räkna minderåriga

Möbiustrappor spelar en viktig roll i teorin om graph minors . Det tidigaste resultatet av denna typ är Wagners teorem [8] att en graf som inte innehåller -moll kan bildas med hjälp av klicksummor för att kombinera plana grafer och Möbius-stegen (i detta sammanhang kallad Wagner-grafen .

Alla 3-kopplade nära-planära grafer [9] är Möbius-stegar eller tillhör ett litet antal andra familjer, och resten av de nära-planära graferna kan erhållas från dessa grafer med hjälp av ett antal enkla operationer [10] .

Nästan alla[ förtydliga ] grafer som inte innehåller en kub som moll kan erhållas från Möbius-stegar som ett resultat av sekventiell tillämpning av enkla operationer [11] .

Kemi och fysik

1982 syntetiserades en molekylstruktur i form av en Möbius-stege [12] och sedan dess har sådana grafer varit intressanta för kemister och kemisk stereografi [13] , särskilt i ljuset av DNA-molekyler som liknar Möbius-stegen. Med detta i åtanke har de matematiska symmetrierna för inbäddningar av Möbius-stegar särskilt studerats i [14] .

Möbius-stegar används som en modell av en supraledande ring i experiment för att studera effekterna av ledningstopologi i interaktionen mellan elektroner [15] [16] .

Kombinatorisk optimering

Möbius-stegar används också inom datavetenskap som en del av en heltalsprogrammeringsmetod för att ställa in packnings- och linjära ordningsproblem. Vissa konfigurationer i dessa problem kan användas för att definiera ytor av polytoper som beskriver avslappning av villkoren för linjär programmering . Dessa ansikten kallas Möbiustrappans begränsningar [17] [18] [19] [20] .

Se även

Anteckningar

  1. ↑ McSorley, 1998 .
  2. ↑ Guy, Harari, 1967 .
  3. ↑ Lee, 2005 .
  4. ↑ De Mieu, Nua, 2004 .
  5. ↑ Jacobson, Rivin, 1999 .
  6. ↑ Valdes, 1991 .
  7. ↑ Biggs, Daymrell, Sands, 1972 .
  8. ↑ Wagner, 1937 .
  9. ↑ En nästan plan graf  är en icke-planär graf för vilken vilken som helst icke-trivial moll är plan
  10. ↑ Gubser, 1996 .
  11. ↑ Maharri, 2000 .
  12. ↑ Walba, Richards, Haltiwanger 1982 .
  13. ↑ Simon, 1992 .
  14. ↑ Flapan, 1989 .
  15. ↑ Mila, Stafford, Capponi, 1998 .
  16. ↑ Deng, Xu, Liu, 2002 .
  17. ↑ Bolotashvili, Kovalev, Girlich, 1999 .
  18. ↑ Borndörfer, Weissmantel, 2000 .
  19. ↑ Grötschel, Jünger, Reinelt, 1985 .
  20. ↑ Newman, Vempala, 2001 .

Litteratur

Länkar