Generowanie wykresów obwodu

Niech . Muszę wygenerować proste wykresy obwodu tak aby zestaw wszystkich motocykli tworzy podwójną osłonę (to znaczy, każda krawędź jest dzielona przez dokładnie dwa motocykle) i takie, że przecięcie dowolnych dwóch motocykle to albo wierzchołek, krawędź, albo pusty. Wygenerowane wykresy powinny być dowolnie duże.G g g G g $g\geq 3$$G$$g$$g$$G$$g$$g$

Metoda generowania powinna mieć pewną przypadkowość, ale nie w trywialnym znaczeniu. Chcę być w stanie uzyskać dość skomplikowane wykresy. Na przykład wyobraź sobie prostokątną siatkę w płaszczyźnie. Jeśli zidentyfikujemy przeciwległe boki prostokąta ograniczającego, otrzymamy wykres, który spełnia wszystkie powyższe wymagania dla . Zakwalifikowałbym ten wykres jako prosty.g = $n\times m$$g=4$

Czy jest taka metoda?

Doceniane są również wszelkie odniesienia do podobnych problemów.

Mój na wpół upieczony pomysł był trochę zbyt ambitny. Podaję to poniżej w celach informacyjnych, ale określony przeze mnie warunek odległości nie jest w rzeczywistości wystarczający do zagwarantowania dużego obwodu.

Istnieją dowolnie duże, bardzo symetryczne mapy powierzchni o dużym obwodzie, ale opublikowane dowody istnienia oparte są w dużej mierze na teorii grupy, a nie na topologii lub geometrii jako takiej.

W szczególności, dla każdej liczby całkowite , d i r , takie, że 1 / g + 1 / d < 1 / 2 , to jest regularny mapy powierzchni, w którym każda ściana posiada g krawędzie, każdy wierzchołek ma stopień D , a co nie kurczliwe cykl na powierzchni przecina przynajmniej r krawędzie. Tutaj „regularny” oznacza zarówno, że każdy wierzchołek ma ten sam stopień, i że dla każdej pary ukierunkowanych krawędzi występuje automorfizm osadzania, który wysyła skierowaną krawędź na drugi. Ustawienie $g$$d$$r$$1/g + 1/d < 1/2$$g$$d$$r$$r$wystarczająco duża w tej konstrukcji gwarantuje, że obwód wykresu wynosi . Zobacz na przykład:$g$

• Roman Nedela i Martin Škoviera. Regularne mapy na powierzchniach o dużej szerokości płaskiej. European J. Combinatorics 22 (2): 243--262, 2001.

• Jozef Širáň. Reprezentacje grup trójkątów i konstrukcje zwykłych map. Proc. London Math. Soc. 82 (3): 513–532, 2001.

Po utworzeniu takiej mapy powierzchni można wygenerować większe mapy o tym samym obwodzie i tym samym stopniu, budując zakrywające przestrzenie.

Oto jeden (częściowo upieczony) sposób generowania takich wykresów. Niech będzie wykresem płaskim o następujących właściwościach:$G$

• Każda ograniczona powierzchnia ma dokładnie g krawędzie.$G$$g$

• Zewnętrzna powierzchnia ma parzystą liczbę krawędzi; nazwać je przez krawędzie brzegowe o G . (Ten warunek obowiązuje automatycznie, gdy g jest parzysty; jeśli g jest nieparzysty, G musi mieć parzystą liczbę ograniczonych powierzchni).$G$$G$$g$$g$$G$

• Możliwe jest sparowanie krawędzi granicy , tak aby odległość w G od dowolnej krawędzi granicy do jej partnera wynosiła co najmniej g . Ten warunek w rzeczywistości nie wystarczy; dokładny wymagany tutaj stan jest niejasny.$G$$G$$g$

$g$

$G'$$g$$G$$G$$G'$$G'$$g$

$G$$d$$d$$g$$1/d + 1/g < 1/2$