¿Demostración de que la relación entre vértices y aristas en una cuadrícula infinita (cuadrada) es de 1:2?

Question

Estoy haciendo la afirmación de que la proporción de vértices y aristas en una cuadrícula cuadrada infinita es $1:2$ . Necesito este hecho para deducir otros teoremas específicos para mi problema, sin embargo no encuentro ninguna teoría sobre rejillas infinitas.

Preferiría citar alguna bibliografía al respecto (tal vez también para rejillas hexagonales y triangulares).

Si no existe literatura formal que cubra ese tema, me gustaría escribir la prueba. Mi pensamiento hasta ahora es que cada vértice tiene $4$ aristas conectadas a él y cada arista $2$ vértices, lo que hace que $2$ a $4$ relación $-> 1:2$ . Sin embargo, creo que esto no es lo suficientemente formal y que la prueba debería incluir el infinito de la red.

Por favor, publica una posible bibliografía o una prueba formal si crees que la mía no es suficiente.

Answer 1

Si estamos siendo "cuidadosos con $\infty$ ", entonces consideremos un $n \times n$ rejilla cuadrada (con $n^2$ vértices). En esta cuadrícula, hay $(n-2)^2$ vértices interiores, que tienen $4$ bordes fuera de ellos; $4(n-2)$ vértices de borde, que tienen $3$ bordes fuera de ellos; $4$ vértices de esquina, que tienen $2$ bordes fuera de ellos.

Por la fórmula de la suma de grados, la suma de estos números da el doble de aristas (porque cada arista se cuenta dos veces, una por cada uno de sus extremos). Si llamamos al número de aristas $m$ entonces $$ 2m = 4(n-2)^2 + 3(4n-8) + 2(4) = 4n^2-4n $$ por lo que hay $2n^2-2n$ bordes. La relación $\frac mn$ de aristas sobre vértices es $\frac{2n^2-2n}{n^2} = 2 - \frac 2n$ que se acerca a $2$ como $n \to \infty$ .

Podemos ser totalmente rigurosos y aún así hacer menos trabajo con el análisis asintótico. Si afirmáramos que cada vértice tiene grado $4$ y, por lo tanto, que $2m = 4n^2$ , nos equivocaríamos sólo en los bordes de la frontera. Pero hay $O(n)$ bordes a lo largo de cada frontera, cuyo grado difiere de $4$ por una constante, por lo que tenemos $2m = 4n^2 + O(n)$ y por lo tanto $\frac mn = \frac{2n^2 + O(n)}{n^2} = 2 + O(\frac1n)$ . Una vez más, como $n \to \infty$ Esto se acerca a $0$ .

Además, podemos considerar una rejilla cuadrada toroidal finita, que se "envuelve" en los bordes, al estilo Pac-Man. Entonces cada vértice tiene grado $4$ y la relación entre vértices y aristas es $1:2$ sin aproximación.

Answer 2

La respuesta es bastante sencilla. Seguro que hay una prueba matemática, dada una $n \times n$ plaza, habrá $(n+1)²$ vértices y $2n(n+1)$ bordes, lo que equivale a $∞²$ a $2∞²$ como $n$ va a $∞$ . Sin embargo, esta es la explicación menos divertida.

Juguemos a un juego, construimos una rejilla cuadrada completamente de vértices unidos con aristas. En la primera imagen, añadimos repetidamente una línea conectada a un punto, en la segunda añadimos dos líneas conectadas a un punto, y en el extremo derecho añadimos $3$ conectado a uno. Como puedes ver, si no hay suficientes vértices, acabarán faltando líneas, mientras que si hay demasiados, acabarán faltando puntos. Ahora bien, dependiendo de cómo se juegue, pueden faltar algunas líneas o puntos de cualquier manera, pero a menos que haya un $2$ a $1$ relación, no hay manera de llenar todos los espacios. Adelante, inténtalo, es imposible, por mucho que lo intentes.

Sé que esa explicación no era tan matemática como uno esperaría, pero me imaginé que este sería un problema de un solo método, así que quería proporcionar algo único de todas las otras respuestas. Sin embargo, si quieres que amplíe mi explicación introductoria, sólo tienes que comentar y si estarás encantado de hacerlo.

Answer 3

Considera que cualquier vértice tiene cuatro aristas conectadas a él. Elige dos aristas que sean adyacentes, es decir, que sean lados adyacentes de un cuadrado. El vértice y las dos aristas se pueden trasladar a cualquier otro vértice y esto divide todos los vértices y aristas. Así, la proporción de vértices y aristas es $1:2$ . Lo importante es la conexión local entre vértices y aristas, a pesar de que hay muchas formas diferentes de emparejar aristas y vértices. Sólo hay una forma que es invariable por traslación.

Una prueba similar se aplica a una malla unidimensional infinita en la que la relación es $1:1$ .

Una prueba similar se aplica a una malla infinita (triangular) en la que la relación es $1:3$ .

En general, si se tiene una malla homogénea infinita con el grado de cada vértice siendo una constante $D$ entonces, como cada arista conecta exactamente dos vértices, la relación entre vértices y aristas es $2:D$ . Esto se aplica a infinitos árboles homogéneos como caso especial.

Por lo tanto, en el caso de una red hexagonal infinita, la relación es $2:3$ .

Las mismas pruebas se aplican a un ciclo finito, a un cilindro infinito y a un toro finito identificando formalmente las aristas de las cuadrículas infinitas. Está claro que para un ciclo finito existe un $1:1$ relación entre vértices y aristas, y esto también se aplica en el límite de un ciclo infinito. El número total infinito de vértices o aristas no supone ninguna diferencia. Lo que cuenta son las conexiones locales entre ellas.

Si quieres ser realmente cuidadoso, considera el entramado de puntos en el plano con coordenadas enteras como vértices con aristas horizontales $\{(n,y)\}$ donde $m\le y<m+1$ y bordes verticales $\{(x,m)\}$ donde $n\le x<n+1$ . Cada cuadrado del período es $\{(x,y)\}$ donde $n\le x<n+1, m\le y<m+1$ y cada uno contiene un punto de red $(n,m)$ un borde horizontal y un borde vertical. La relación es $1:2$ en cualquier plaza del período. Pruebas similares se aplican a otros casos.

Leer el artículo de Wikipedia Par fundamental de periodos para la idea relacionada de paralelogramo de período fundamental que es muy importante en la teoría de la función elíptica.