Geração de gráficos de perímetro modo que os ciclos mínimos formem uma cobertura de borda dupla

10

Seja . Preciso gerar gráficos simples de circunferência modo que o conjunto de todas as -cycles forme uma cobertura de borda dupla de (ou seja, toda aresta é compartilhada por exatamente duas -cycles), e de modo que a interseção de duas -cycles é um vértice, uma aresta ou vazio. Os gráficos gerados devem ser arbitrariamente grandes.g3GggGgg

O método de geração deve ter alguma aleatoriedade, mas não em um sentido trivial. Quero poder obter gráficos bastante complicados. Por exemplo, imagine uma grade retangular no plano. Se identificarmos os lados opostos do retângulo delimitador, obteremos um gráfico que satisfaz todos os requisitos acima para . Eu qualificaria este gráfico como simples.n×mg=4

Existe algum método desse tipo?

Todas as referências a problemas semelhantes também são apreciadas.

becko
fonte
3
Então você quer que as motocicletas sejam as faces de alguma incorporação poliédrica do gráfico em alguma superfície? (A incorporação gráfico é "poliédrica" se cada face da incorporação é um disco, e quaisquer duas faces compartilham um vértice comum, compartilham uma aresta comum, ou não se cruzam em tudo.)g
Jeffε
@ Jɛ ff E Sim. Se todas as motocicletas são garantidas como faces e todas as faces são garantidas como motocicletas, essa é uma descrição equivalente. ggg
Becko
@ Jɛ ff E Você sabe onde posso encontrar gráficos 4-regulares distintos e seus revestimentos poliédricos? Eles não precisam ser gráficos enormes, mas eu gostaria de ver outros gráficos que satisfaçam as propriedades que solicitei além da que mencionei. Sei também que decidir a incorporabilidade poliédrica é NP-completo, graças a esta resposta . Apesar disso, eu também gostaria de saber de um algoritmo que encontre uma incorporação poliédrica, se houver. Você conhece algum recurso / artigo / ... que explique esse algoritmo?
Becko
existe uma ligação entre 4 gráficos regulares e incorporações poliédricas? alguém tem uma descrição disso? anos atrás, procuramos artigos sobre a geração aleatória de gráficos regulares, existem alguns, portanto, se você puder reformular esta pergunta em termos de gráficos regulares, isso poderá levar a mais possibilidades.
vzn
@vzn Suponha que eu tenha uma incorporação poliédrica como a sugerida por Jeff. Todos os rostos são -cycles. O gráfico duplo obtido desta incorporação é regular. Talvez isso possa ser invertido: comece com um gráfico regular e encontre seu dual de alguma forma. Era o que eu tinha em mente. g gggg
Becko

Respostas:

4

Minha idéia meio cozida era um pouco ambiciosa. Incluí-o abaixo para referência, mas a condição de distância especificada não é suficiente para garantir uma circunferência grande.

Existem mapas de superfície altamente simétricos arbitrariamente grandes e com grande perímetro, mas as provas de existência publicadas são amplamente baseadas na teoria de grupos e não na topologia ou na geometria em si.

Especificamente, para quaisquer números inteiros , , e tais que , existe um mapa de superfície regular em que toda face possui arestas, todo vértice tem grau e todo não contratável o ciclo na superfície cruza pelo menos arestas. Aqui significa "regulares" , tanto que cada vértice tem o mesmo grau e que, para qualquer par de arestas dirigidas, existe um automorfismo da incorporação que envia dirigido borda para o outro. Definir suficientemente grande nesta construção garante que a circunferência do gráfico seja . Veja, por exemplo:d r 1 / g + 1 / d < 1 / 2 g d r r ggdr1/g+1/d<1/2gdrrg

Depois de ter um desses mapas de superfície, mapas maiores com a mesma circunferência e grau podem ser gerados através da construção de espaços de cobertura.


Aqui está uma maneira (semi-cozida) de gerar esses gráficos. Seja um gráfico plano com as seguintes propriedades:G

  • Toda face delimitada de tem exatamente arestas.gGg

  • A face externa de tem um número par de arestas; chamar estas as bordas do limite de . (Essa condição é mantida automaticamente quando é par; se é ímpar, deve ter um número par de faces delimitadas.)G g g LGGggG

  • É possível emparelhar as arestas de limite de , de modo que a distância em de qualquer aresta de limite até seu parceiro seja pelo menos . Essa condição não é realmente suficiente; a condição exata necessária aqui não é clara.G gGGg

Gráficos de plano arbitrariamente grandes com essas propriedades podem ser construídos tomando uma porção finita suficientemente grande de uma telha regular do plano hiperbólico por gonsg .

Finalmente, para obter um gráfico de superfície onde cada face possui comprimento , identifique pares de arestas de contorno em acordo com o emparelhamento descrito acima. As faces delimitadas de se tornam as faces de uma incorporação celular de em alguma superfície fechada sem limites. A condição de distância no emparelhamento garante que a circunferência de seja  . g L L L ' L ' gGgGGGGg

Ao escolher e o emparelhamento com mais cuidado, uma vez é possível construir gráficos - regulares arbitrariamente grandes que satisfaçam sua condição de perímetro, para quaisquer números inteiros e tais que . Mesmo dentro dessas restrições, a construção tem muitos graus de liberdade.d d g 1 / d + 1 / g < 1 / 2Gddg1/d+1/g<1/2

Jeffε
fonte
Além disso, os gráficos que você obtém dessa construção são expansores.
Jeffε
Quando identifico um par de arestas de contorno, como posso ter certeza de que os outros pares de arestas ainda estão mais afastados que um do outro? g
Becko
O que é um gráfico de expansão ?
Becko
11
@becko, você deve Google antes de pedir :) en.wikipedia.org/wiki/Expander_graph
Kaveh
@Kaveh Ok. Desculpe eu perdi isso :)
Becko