Erzeugen von Graphen des Umfangs

10

Sei . Ich muss einfache Graphen G des Umfangs g erzeugen, so dass die Menge aller g- Zyklen eine doppelte Kantenabdeckung von G bildet ( dh jede Kante wird von genau zwei g- Zyklen geteilt), und so, dass der Schnittpunkt von zwei beliebigen g- Zyklen sind entweder ein Scheitelpunkt, eine Kante oder leer. Die generierten Grafiken sollten beliebig groß sein.g3GggGgg

Die Methode der Erzeugung sollte eine gewisse Zufälligkeit haben, aber nicht in einem trivialen Sinne. Ich möchte in der Lage sein, ziemlich komplizierte Grafiken zu erhalten. Stellen Sie sich zum Beispiel ein rechteckiges Gitter in der Ebene vor. Wenn wir die gegenüberliegenden Seiten des Begrenzungsrechtecks ​​identifizieren, erhalten wir ein Diagramm, das alle oben genannten Anforderungen für g = 4 erfüllt . Ich würde dieses Diagramm als einfach qualifizieren.n×mg=4

Gibt es eine solche Methode?

Hinweise auf ähnliche Probleme sind ebenfalls willkommen.

winko
quelle
3
Sie möchten also, dass die Zyklen die Flächen einer polyedrischen Einbettung des Graphen auf eine Oberfläche sind? (Eine Grapheneinbettung ist "polyedrisch", wenn jede Seite der Einbettung eine Scheibe ist und zwei beliebige Flächen einen gemeinsamen Scheitelpunkt, eine gemeinsame Kante oder überhaupt keinen Schnittpunkt haben.)g
Jeffε
@ Jɛ ff E Ja. Wenn garantiert ist, dass alle Zyklen Gesichter sind und alle Gesichter garantiert g- Zyklen sind, dann ist das eine äquivalente Beschreibung. gg
Becko
@ Jɛ ff E Weißt du, wo ich verschiedene 4-reguläre Graphen und ihre polyedrischen Einbettungen finden kann? Es müssen keine riesigen Grafiken sein, aber ich würde gerne andere Grafiken sehen, die die von mir angeforderten Eigenschaften erfüllen, außer den von mir erwähnten. Ich weiß auch, dass die Entscheidung über die Einbettbarkeit von Polyedern dank dieser Antwort NP-vollständig ist . Trotzdem würde ich gerne einen Algorithmus kennen, der eine polyedrische Einbettung findet, wenn es eine gibt. Kennen Sie eine Ressource / ein Papier / ..., die einen solchen Algorithmus erklärt?
Becko
Gibt es eine Verbindung zwischen 4 regulären Graphen und polyedrischen Einbettungen? Hat jemand eine Beschreibung davon? Vor Jahren wurden Artikel zum zufälligen Generieren regulärer Diagramme nachgeschlagen. Es gibt einige. Wenn Sie diese Frage in Bezug auf reguläre Diagramme umformulieren können, führt dies möglicherweise zu mehr Möglichkeiten.
vzn
@vzn Angenommen, ich habe eine polyedrische Einbettung wie die von Jeff vorgeschlagene. Alle Gesichter sind Zyklen. Der aus dieser Einbettung erhaltene Doppelgraph ist g- regelmäßig. Vielleicht kann dies umgekehrt werden: Beginnen Sie mit einem g- regulären Graphen und finden Sie dessen Dual irgendwie. Das hatte ich mir vorgestellt. ggg
Becko

Antworten:

4

Meine halbherzige Idee war etwas zu ehrgeizig. Ich füge es unten als Referenz hinzu, aber die von mir angegebene Abstandsbedingung reicht nicht aus, um einen großen Umfang zu gewährleisten.

Es gibt beliebig große hochsymmetrische Oberflächenkarten mit großem Umfang, aber veröffentlichte Existenzbeweise basieren größtenteils auf Gruppentheorie und nicht auf Topologie oder Geometrie an sich.

gdr1/g+1/d<1/2gdrrgroß genug in dieser Konstruktion garantiert, dass der Umfang des Graphen . Siehe zum Beispiel:g

Sobald Sie eine solche Oberflächenkarte haben, können größere Karten mit demselben Umfang und Grad durch Erstellen von Abdeckungsräumen erstellt werden.


Hier ist eine (halbgebackene) Möglichkeit, solche Diagramme zu erstellen. Sei ein ebener Graph mit den folgenden Eigenschaften:G

  • Jede begrenzte Fläche von hat genau g Kanten.Gg

  • Die Außenseite von hat eine gerade Anzahl von Kanten; nennen diese die Begrenzungskanten von G . (Diese Bedingung gilt automatisch, wenn g gerade ist. Wenn g ungerade ist, muss G eine gerade Anzahl von begrenzten Flächen haben.)GGggG

  • Es ist möglich, die Grenzkanten von zu paaren , so dass der Abstand in G von jeder Grenzkante zu ihrem Partner mindestens g beträgt . Dieser Zustand ist eigentlich nicht genug; Der genaue Zustand, der hier benötigt wird, ist unklar.GGg

g

GgGGGGg

Gddg1/d+1/g<1/2

Jeffε
quelle
Außerdem sind die Diagramme, die Sie aus dieser Konstruktion erhalten, Expander.
Jeffs
g
Was ist ein Expander- Graph?
Becko
1
@becko, sollten Sie Google, bevor Sie fragen :) en.wikipedia.org/wiki/Expander_graph
Kaveh
@ Kaveh Ok. Entschuldigung, das habe ich verpasst :)
Becko