Möbiův žebřík

Möbiův žebřík  je kubický oběžný graf se sudým počtem vrcholů , vytvořený z cyklu s vrcholy přidáním hran (nazývaných „příčky“) spojujícími opačné páry vrcholů cyklu. Pojmenováno tak, protože sestává z cyklů délky 4 [1] spojených společnými hranami a topologicky tvořících Möbiův pás . Kompletní bipartitní graf (graf „ domy a studny “) je Möbiův žebřík (na rozdíl od ostatních má další cykly o délce 4).

Nejprve studoval Guy a Harari [2] .

Vlastnosti

Jakýkoli Möbiův žebřík je nerovinný vrcholový graf. Počet překročení Möbiova žebříku je jeden a graf lze vložit bez průsečíků do torusové nebo projektivní roviny (tj. je to toroidní graf ). Lee [3] studoval vkládání těchto grafů do povrchů vyšších rodů.

Möbiovy schody jsou vrcholově tranzitivní , ale (s výjimkou ) ne hraně tranzitivní  - každá hrana cyklu, ze kterého je žebřík vytvořen, patří do jednoho 4hranného cyklu, zatímco každá příčka patří do dvou takových cyklů.

Jestliže , pak je bipartitní . Když je podle Brooksova teorému chromatické číslo 3. Je známo [4] , že Möbiův žebřík je jednoznačně určen jeho polynomem Tatta .

Möbiův žebřík má 392 kostrových stromů . Tento graf má také největší počet kostry mezi kubickými grafy se stejným počtem vrcholů [5] [6] . Mezi kubickými grafy s 10 vrcholy má však Petersenův graf největší počet kostry , což není Möbiův žebřík.

Tuttovy polynomy Möbiových žebříků lze získat jednoduchým rekurzivním vzorcem [7] .

Počítat nezletilé

Möbiovy schody hrají důležitou roli v teorii graf minors . Nejranějším výsledkem tohoto typu je Wagnerova věta [8] , že graf, který neobsahuje -minory, lze vytvořit pomocí klikových součtů pro kombinaci rovinných grafů a Möbiova žebříku (v této souvislosti nazývaného Wagnerův graf .

Všechny 3-spojené téměř rovinné grafy [9] jsou Möbiovy žebříky nebo patří do malého počtu jiných rodin a zbytek téměř rovinných grafů lze z těchto grafů získat pomocí řady jednoduchých operací [10] .

Téměř všechny[ upřesnit ] grafy, které neobsahují kostku jako vedlejší, lze získat z Möbiových žebříků jako výsledek sekvenční aplikace jednoduchých operací [11] .

Chemie a fyzika

V roce 1982 byla syntetizována molekulární struktura ve formě Möbiova žebříku [12] a od té doby jsou takové grafy zajímavé pro chemiky a chemickou stereografii [13] , zejména ve světle molekul DNA podobných Möbiovu žebříku. S ohledem na tuto skutečnost byly matematické symetrie vložení Möbiových žebříků speciálně studovány v [14] .

Möbiovy žebříky se používají jako model supravodivého prstence v experimentech ke studiu vlivů topologie vedení při interakci elektronů [15] [16] .

Kombinatorická optimalizace

Möbiovy žebříky se také používají v informatice jako součást přístupu celočíselného programování k problémům s balením množin a lineárním uspořádáním. Některé konfigurace v těchto úlohách mohou být použity k definování ploch polytopů , které popisují relaxaci podmínek lineárního programování . Tyto plochy se nazývají omezení Möbiových schodů [17] [18] [19] [20] .

Viz také

Poznámky

  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. ↑ Téměř rovinný graf  je nerovinný graf, pro který je každá netriviální vedlejší rovina rovinná
  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 .

Literatura

Odkazy