Generando gráficos de circunferencia

10

Deje . Necesito generar gráficos simples G de circunferencia g de modo que el conjunto de todos los g- ciclos forme una cubierta de doble borde de G (es decir, cada borde es compartido por exactamente dos g- ciclos), y tal que la intersección de dos g -cycles es un vértice, un borde o está vacío. Los gráficos generados deben ser arbitrariamente grandes.g3GggGgg

El método de generación debería tener algo de aleatoriedad, pero no en un sentido trivial. Quiero poder obtener gráficos bastante complicados. Por ejemplo, imagine una cuadrícula rectangular en el plano. Si identificamos los lados opuestos del rectángulo delimitador, obtenemos un gráfico que satisface todos los requisitos anteriores para g = 4 . Calificaría este gráfico como simple.n×mg=4

¿Existe algún método de este tipo?

Cualquier referencia a problemas similares también es apreciada.

llamar
fuente
3
Entonces, ¿desea que los -cycles sean las caras de una incrustación poliédrica del gráfico en alguna superficie? (Una incrustación gráfica es "poliédrica" ​​si cada cara de la incrustación es un disco, y cualquiera de las dos caras comparten un vértice común, comparten un borde común o no se cruzan en absoluto.)g
Jeffε
@ Jɛ ff E Sí. Si se garantiza que todas las -cycles son caras, y todas las caras son g -cycles, entonces esa es una descripción equivalente. gg
Becko
@ Jɛ ff E ¿Sabes dónde puedo encontrar gráficos distintos de 4 regulares y sus incrustaciones poliédricas? No tienen que ser gráficos enormes, pero me gustaría ver otros gráficos que satisfagan las propiedades que solicité además de la que mencioné. También sé que decidir la capacidad de inserción poliédrica es NP-completo gracias a esta respuesta . A pesar de eso, también me gustaría saber de un algoritmo que encuentre una incrustación poliédrica si la hay. ¿Conoces algún recurso / papel / ... que explique tal algoritmo?
Becko
¿Existe un vínculo entre 4 gráficos regulares y las incrustaciones poliédricas? ¿Alguien tiene una descripción de eso? Hace años buscó documentos sobre la generación aleatoria de gráficos regulares, hay bastantes, por lo tanto, si puede reformular esta pregunta en términos de gráficos regulares, podría generar más posibilidades.
vzn
ggg

Respuestas:

4

Mi idea a medias era demasiado ambiciosa. Lo incluyo a continuación para referencia, pero la condición de distancia que especifiqué en realidad no es suficiente para garantizar una gran circunferencia.

Existen mapas de superficie arbitrariamente grandes y altamente simétricos con gran circunferencia, pero las pruebas de existencia publicadas se basan en gran medida en la teoría de grupos en lugar de la topología o la geometría per se.

gdr1/g+1/d<1/2gdrrg

Una vez que tenga uno de estos mapas de superficie, se pueden generar mapas más grandes con la misma circunferencia y grado construyendo espacios de cobertura.


G

  • Gg

  • GGggG

  • GGg

g

GgGGGGg

Gddg1/d+1/g<1/2

Jeffε
fuente
Además, los gráficos que obtiene de esta construcción son expansores.
Jeffε
g
¿Qué es un gráfico expansor ?
Becko
1
@becko, deberías buscar en Google antes de preguntar :) en.wikipedia.org/wiki/Expander_graph
Kaveh
@Kaveh Ok. Lo siento, me perdí eso :)
becko