7 votos

¿Hay solo siete gráficos planos 3-conectados con ciertas simetrías?

Sólo existen cinco poliedros regulares, y sólo dos más si tenemos en cuenta la cuasi-regulares los poliedros. Así que en la suma, hay siete (convexo) poliedros que son de vértice y arista-transitiva.

Desde el 1-esqueleto de (convexo) poliedros son exactamente los 3 conectados grafos planares (por Steinitz teorema), y el vértice y el borde de la transitividad de un poliedro implica las mismas simetrías para su 1-esqueleto, llegué a la siguiente "realización":

Hay sólo siete de vértice y arista-transitiva, 3-conectado, grafos planares (uno para cada cuasi-poliedro regular).

Es esto cierto o me estoy perdiendo algo?

5voto

user30382 Puntos 48

Como se señaló en los comentarios, su conclusión doen't siga como hay un gráfico que no proviene de un (cuasi)-poliedro regular. Es una pregunta interesante, y creo que tengo una prueba. Tengo poco conocimiento de la teoría de grafos, así que quizás yo haya demasiado complicado las cosas. Primero, algunas anotaciones:

Deje $G$ ser finito, vértice y arista-transitiva $3$-conectado plano gráfico. Debido a $G$ es de vértice transitiva es regular, a decir de grado $d$. Debido a $G$ es el borde transitiva tiene en la mayoría de los dos tipos de caras. Es decir, existen enteros $n_2\geq n_1\geq3$ de manera tal que cada cara de $G$ ha $n_1$ o $n_2$ bordes. Si todas las caras tienen el mismo número de aristas, establezca $n_2=n_1$. Vamos $V$, $E$ y $F$ denotar el número de vértices, aristas y caras de $G$, respectivamente, y deje $F_i$ denotar el número de caras con $n_i$ bordes.

Proposición 1. El grado $d$ satisface $3\leq d\leq5$.

Claramente $E=\frac{d}{2}V$$F\leq\frac{d}{3}V$. Por Euler tenemos $$2=V-E+F\leq V-\frac{d}{2}V+\frac{d}{3}V=\left(1-\frac{d}{6}\right)V,$$ lo que muestra que $d<6$. Claramente $d>2$ porque $G$ $3$- conectado, por lo $3\leq d\leq5$.

Proposición 2. El número de aristas de las caras más pequeñas $n_1$ satisface $3\leq n_1\leq 5$.

Tenga en cuenta que $F\leq\frac{d}{n_1}V$ con igualdad si y sólo si $n_1=n_2$, así que de nuevo por Euler $$2=V-E+F\leq V-\frac{d}{2}V+\frac{d}{n_1}V=\left(1-\frac{d}{2}+\frac{d}{n_1}\right)V,$$ y debido a que $d\geq3$ $n_1>2$ se sigue que $1-\frac{3}{2}+\frac{3}{n_1}>0$, lo que equivale a $n_1<6$.

Observación 3. De lo anterior también es claro que si $n_1>3$, luego $$0<1-\frac{d}{2}+\frac{d}{n_1}\leq1-\frac{d}{2}+\frac{d}{4}=1-\frac{d}{4},$$ lo que muestra que $d>4$, y, por tanto, $d=5$ por la proposición 1.

Proposición 4. El número de bordes de las más caras de $n_2$ satisface $3\leq n_2\leq 5$.

Si $n_1=n_2$ hemos terminado, así que supongamos $n_1\neq n_2$. A continuación, cada borde es adyacente a dos caras de diferentes tamaños, de ahí que cada vértice es adyacente a un número de caras, y por lo $d$ es incluso. Por la proposición 1 obtenemos $d=4$ y por lo tanto por observación 3 obtenemos $n_1=3$.

Debido a $G$ es el borde transitiva, contando el número de aristas para cada tipo de rostro se muestra que el$n_iF_i=E$$i=1,2$. Como se señaló antes de $E=\frac{d}{2}V=2V$$3F_1=n_2F_2=E=2V$, así que podemos ver que $$2=V-E+F=V-2V+F_1+F_2 =\left(1-2+\frac{2}{3}+\frac{2}{n_2}\right)V =\left(-\frac{1}{3}+\frac{2}{n_2}\right)V,$$ que como antes muestra que $n_2<6$.


Esto nos deja con la siguiente tabla de siete combinaciones posibles de valores de $n_1$, $n_2$ y $d$, y el correspondiente valor de $V$ es fácil de calcular: \begin{align*} n_1&&n_2&&d&&V\\ \hline 3&&3&&3&&4 \\ 3&&3&&4&&6 \\ 3&&3&&5&&12\\ 4&&4&&3&&8 \\ 5&&5&&3&&20\\ 3&&4&&4&&12\\ 3&&5&&4&&30 \end{align*} Por algún patán ad hoc argumentos que he sido capaz de demostrar que durante los primeros seis combinaciones hay una ventaja única - y el vértice-transitiva $3$-conectado plano gráfico de $G$ con estos valores, que es por supuesto en el gráfico que viene de un (cuasi)-poliedro regular. El séptimo ha sido un poco demasiado grande para mí para descartar otras gráficas que el icosidodecaedro, pero con algo de esfuerzo, no debería ser demasiado difícil para hacerlo. (Estoy bastante convencido de que no hay otros).


Anexo: Como un ejemplo de algunos de los que no son triviales 'ad-hockery', voy a ilustrar sexto caso anterior, con algunos pequeños huecos a rellenar por el lector. Aquí $n_1=3$, $n_2=4$, $d=4$ y $V=12$. En cada vértice, dos cuadrados y dos triángulos se encuentran en la hilera, y en cada extremo se encuentra junto a un triángulo y un cuadrado. Así que para cualquier dado un vértice $A$, podemos recurrir inmediatamente a los vértices $B$, $C$, $D$ y $E$ adyacente, que forman dos triángulos, decir $ABC$$ADE$. Tenga en cuenta que $B$ $C$ no puede ser adyacente a $D$$E$, ya que de lo contrario tres triángulos se reunirá en $A$. Luego de dos plazas para reunirse en $A$, sin pérdida de generalidad $B$ $E$ tienen en común un vecino, decir $F$, e $C$ $D$ tienen en común un vecino, decir $G$, lo que da la siguiente imagen:

enter image description here

Tenga en cuenta que $F$ $G$ son de hecho diferentes, ya que de lo contrario los bordes $BC$ $DE$ sería adyacentes a los dos triángulos. Las líneas de puntos en la imagen representan los bordes restantes para el dibujado de los vértices, como sabemos que la gráfica de es $4$-regular. Como cada borde es adyacente a un cuadrado y un triángulo, obtenemos la siguiente imagen:

enter image description here

Porque no hay dos triángulos que comparten un borde, los vértices adyacentes en las esquinas de la imagen son de hecho diferentes. Es decir,$T\neq U$$T\neq W$$V\neq U$$V\neq W$. Si $T=V$$U=W$, entonces tenemos un $4$-gráfico regular en $9$ vértices, que claramente no se extiende a un $3$-gráfica conectada en $12$ vértices. Si $T=V$$U\neq W$, entonces hay dos vértices de la izquierda para ser dibujado, y sólo dos vértices en el grafo que se puede conectar, contradiciendo $4$-regularidad. Por lo $T\neq V$ y por simetría $U\neq W$.

A continuación, sólo un vértice queda dibujado, y por $4$-regularidad se debe compartir un borde con precisión $T$, $U$, $V$ y $W$. A continuación, sólo dos bordes entre $T$, $U$, $V$ y $W$ quedan. Ellos no pueden ser $TU$ o $VW$ porque entonces los dos triángulos compartir un borde. Ellos no pueden ser $TV$ o $UW$ porque [el argumento de que faltan por ahora]. De ahí se $TW$$UV$, y así tenemos el $1$-esqueleto de la cuboctahedron.

2voto

Hank Puntos 156

Sí. Con todas esas restricciones, estás restringido a esos siete poliedros.

Si sacas la parte plana, puedes poner una cuadrícula$7\times7$ en un toro. También hay muchos otros gráficos que puede hacer, como los siguientes:

gráficos transitivos

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X