Gráfico 3-regular e circuito de Euler de duas vias
Um planejador urbano construiu uma cidade isolada cuja rede rodoviária consiste em $2N$rotatórias, cada uma conectando exatamente três estradas. Uma série de túneis e pontes garantem que todas as estradas da cidade se cruzem apenas nas rotundas. Todas as estradas são de mão dupla e cada rotatória é orientada no sentido horário. Vlad passou recentemente no teste de direção e está nervoso com rotundas. Ele começa a dirigir de sua casa e sempre faz a primeira edição em cada rotatória que encontra. Acontece que sua jornada inclui todas as estradas da cidade em ambas as direções antes de ele voltar ao ponto de partida na direção de partida. Para quais valores de$N$ Isso é possível?
Tentei transformar isso em um problema de teoria dos grafos equivalente, no qual podemos aplicar alguns resultados em circuitos de Euler ou semelhantes, mas sem essas reformulações parecem úteis. Qualquer ajuda apreciada!
Respostas
$\text{Partial answer}$
Que os vértices do nosso gráfico (as rotundas) sejam $v_1,v_2,...,v_{2N}$. Vamos provar que cada estranho$N$ trabalha e discute sobre mesmo $N$.
$\text{For odd }N$
Claro, casos $N=3$ e $N=5$ trabalhos ($N$ devemos ser $\geq 2$ para o gráfico fazer sentido, então não podemos discutir sobre $N=1$) Aqui estão$2$ configurações que mostram que $N=3$ e $N=5$ trabalhos:
Vamos agora mostrar que se $N_1$ e $N_2$ trabalhar então $N_1+N_2+1$trabalho. Suponha que temos$2$ gráficos $G_1$ e $G_2$, Um com $2N_1$ vértices e o outro com $2N_2$vértices, que funcionam. Selecione$2$ vértices que estão conectados de $G_1$, $v_1$ e $v_2$ e $2$ vértices que estão conectados de $G_2$, $u_1$ e $u_2$. Adicionar$2$ mais vértices, $w_1$ e $w_2$.
Se provarmos, podemos conectar alguns vértices de modo que o novo gráfico funcione (que tem $2\cdot(N_1+N_2+1)$), provamos que se $N_1$ e $N_2$ são números válidos, então é $N_1+N_2+1$.
Faremos as seguintes operações:
- apague a borda entre $v_1$ e $v_2$
- apague a borda entre $u_1$ e $u_2$
- conectar $v_1$ e $w_1$
- conectar $v_2$ e $w_2$
- conectar $u_1$ e $w_1$
- conectar $u_2$ e $w_2$
- conectar $w_1$ e $w_2$
Portanto, a partir desta configuração inicial
nós alcançamos esta configuração
Na verdade, não vou explicar passo a passo por que funciona, mas uma simples análise da viagem que o carro fará com essas novas pequenas mudanças irá, de fato, confirmar que esse novo gráfico funciona.
Portanto, $N_1$, $N_2$ trabalho implica que $N_1+N_2+1$trabalho. Nós mostramos$3$ e $5$ trabalho, então todo estranho $N$ trabalho. $\text{ }\blacksquare$
$\text{For even }N$
Para meu desapontamento, não consegui apresentar uma contradição ou uma prova para um dos casos menores. Observe que é$2k$ é uma solução, então qualquer número par maior $\geq 2k+4$ é claramente uma solução (usando o resultado acima, $N_1$ e $N_2$ trabalhos $\Rightarrow$ $N_1+N_2+1$ trabalho).
$N=2$ claramente não funciona e, bem, para $N=4$Passei cerca de uma hora testando configurações e não consegui encontrar uma que funcionasse. Eu não acho que haja uma maneira de provar que tal gráfico existe sem pelo menos um exemplo, que não pode ser encontrado quando$N$ é par, então tentei provar que mesmo $N$ não funciona.
Tentei várias abordagens, como coloração de bordas, invariantes e alguns outros truques, mas novamente não consegui obter uma contradição. Eu só quero salientar que é impossível controlar as configurações ao tentar refutar que mesmo$N$. É difícil, porque você tem que falar teoricamente e não pode contar com nenhuma configuração. Dê uma olhada neste:
Suponha que você esteja vindo da borda azul em direção $v$. No primeiro caso, você deixaria na borda verde,$vv_1$4, mas no segundo caso, você deixaria na borda vermelha $vv_2$:
É por isso que o posicionamento dos pontos é crucial, para refutar que mesmo $N$ funciona é muito difícil, pois não podemos fazer observações relacionadas à configuração.
Para ser honesto, nem tenho certeza se mesmo $N$deve ou não deve funcionar. Por um lado, das (muito) muitas configurações possíveis, uma pode funcionar, mas, por outro lado, pode haver uma pequena condição que o impede de funcionar. Espero que essa "dissecção" do problema tenha ajudado de alguma forma.
Resposta parcial
Deixe-me formalizar. Se você entrar em uma rotatória por estrada$i$ você sai na estrada $(i \mod 3) +1$.
Seja Ri a estrada i da rotatória R.
$N=1$ é uma solução para o seu problema. conecte as duas rotatórias A e B da seguinte forma: para todos os i: Ai está conectado a Bi
Agora mostramos isso para $N_1,N_2$ solução do seu problema então $N_1+N_2+1$ é uma solução também.
Deixei $T_1,T_2$ ser dois towA_1s com respectivamente $2N_1,2N_2$rotunda. Deixei$A_1,B_1$ ser duas rotatórias conectadas em $T_1$ e $A_2,B_2$ conectado em $T_2$. Nós construímos uma cidade$T_3$ da seguinte forma: adicionamos duas rotatórias $C$ e $D$ e conecte da seguinte maneira:
- $A_1$ com $C.1$
- $B_1$ com $C_2$
- $C_3$ com $D_3$
- $A_2$ com $D_1$
- $B_2$ com $D_2$
$T_3$ é uma solução para o seu problema com $2N_1+2N_2+2=2(N_1+N_2+1)$ rotundas.
Assim, cada ímpar $N$ é uma solução.
Os comentários de @Alex Ravsky nos dizem que $N=2$não é uma solução. Pode ser que os números pares sejam impossíveis (ainda não sei). Vou tentar pensar uma redução com a mesma ideia, a fim de provar isso
wece e mais tarde Vlad forneceram uma prova de que tal turnê pode existir para cada $N$. Mostramos que não pode haver tal turnê, mesmo$N$.
Incorpore o gráfico em uma superfície bidimensional. Para que a noção de "sentido horário" seja bem definida, a superfície deve ser orientável. Agora, o número de vértices é$2N$ e o número de arestas é $3N$. Se houver um passeio como o que você descreveu, a incorporação pode ser considerada como um mapa com uma única face (que tem$6N$lados). Mas a generalização da fórmula de Euler,$$ V-E+F=2-2g, $$ deve segurar, onde $g$é o gênero da superfície na qual o gráfico está embutido. Então nós temos$$ 2N-3N+1=2-2g. $$ Isso é uma contradição se $N$ é mesmo.
Adicionado: a incorporação desejada é obtida desenhando o gráfico em uma esfera com alças, que é uma superfície orientável. Para explicar um pouco mais, comece desenhando o gráfico na esfera. Haverá, em geral, alguns cruzamentos de bordas. O gráfico deve ser desenhado de acordo com a ordem especificada no sentido horário das arestas em cada vértice (rotatória). Para impor essa ordem, às vezes até mesmo um gráfico planar pode precisar ser desenhado com cruzamentos de aresta.
Remova ou redirecione as arestas (sem violar as restrições de ordem das arestas) até que não haja mais cruzamentos. Isso pode ser feito de forma que o gráfico permaneça conectado. Agora adicione as arestas removidas de volta, uma de cada vez: se uma aresta pode ser desenhada dentro de uma única face, faça isso. (A face será dividida em duas faces.) Se não puder, os pontos de inserção da aresta ficam em duas faces diferentes. Faça orifícios em cada uma dessas faces e una-os com um tubo. Nesse processo, as faces começaram como duas superfícies, cada uma homeomórfica a um disco e terminou como uma única superfície homeomórfica a um cilindro. Agora direcione a aresta através do cilindro, que corta o cilindro de forma que ele seja novamente homeomórfico a um disco.
Uma vez que todas as arestas tenham sido adicionadas de volta, temos a incorporação desejada do gráfico em uma superfície orientável. Esta é uma incorporação de 2 células, o que significa que todas as faces são homeomórficas aos discos, uma propriedade necessária para aplicar a fórmula de Euler.
As ideias neste esboço vêm de um pequeno artigo,
JH Lindsay, Um tratamento elementar da incorporação de um gráfico em uma superfície . The American Mathematical Monthly 66 (2) (1959) 117-118.
e da tese de mestrado de Jack Edmond
Edmonds, John Robert (1960). Uma representação combinatória para superfícies poliédricas orientadas . University of Maryland.
Uma citação deste último:
Teorema 2. Dado um grafo linear conectado com uma ordenação cíclica arbitrariamente especificada das arestas de cada vértice, existe um poliedro topologicamente único, de dois lados, Cujas arestas e vértices são o gráfico dado e cujas ordenações das arestas no sentido horário em cada vértice (com respeito para um dos lados) são conforme especificado.
Essas ideias têm uma longa história, remontando a Lothar Heffter na década de 1890. A noção de associar um embedding a uma especificação das ordens das arestas em cada vértice de um gráfico agora é conhecida como sistema de rotação . Se você quiser experimentar as ideias, pode verificar que existem essencialmente três sistemas de rotação diferentes para$K_4$, produzindo três embeddings diferentes, um esférico (gênero $0$) incorporação com quatro faces triangulares e duas toroidais (gênero $1$) embeddings, cada um com duas faces - um triângulo e um nonagon ou um quadrilátero e um octagon.