Dimensión (teoría de grafos)

En matemáticas , y particularmente en teoría de grafos , la dimensión de un grafo es el menor entero $n$ tal que existe una "representación clásica" del grafo en el espacio euclidiano de dimensión $n$ con todas las aristas teniendo longitud unitaria.

En una representación clásica, los vértices deben ser puntos distintos, pero las aristas pueden cruzarse entre sí. ^[1]

La dimensión de un grafo $G$ se escribe . ${\estilo de visualización \dim G}$

Por ejemplo, el gráfico de Petersen se puede dibujar con aristas unitarias en , pero no en : por lo tanto, su dimensión es 2 (véase la figura de la derecha). $Estilo de visualización E2$ $Estilo de visualización E1$

Este concepto fue introducido en 1965 por Paul Erdős , Frank Harary y William Tutte . ^[2] Generaliza el concepto de gráfico de distancia unitaria a más de 2 dimensiones.

Ejemplos

Con 4 puntos igualmente espaciados, necesitamos 3 dimensiones.

Gráfica completa

En el peor de los casos, cada par de vértices está conectado, dando lugar a un gráfico completo .

Para sumergir el gráfico completo con todas las aristas con longitud unitaria, necesitamos el espacio euclidiano de dimensión . ^[3] Por ejemplo, se necesitan dos dimensiones para sumergir (un triángulo equilátero) y tres para sumergir (un tetraedro regular) como se muestra a la derecha. $Estilo de visualización K_{n}$ ${\estilo de visualización n-1}$ $Estilo de visualización K3$ $Estilo de visualización K_{4}$

\dim K_{n}=n-1

En otras palabras, la dimensión del grafo completo es la misma que la del símplex que tiene el mismo número de vértices.

El gráfico bipartito completo dibujado en el espacio euclidiano tridimensional. $Estilo de visualización K_{4,2}$

El gráfico bipartito completo dibujado en el espacio euclidiano tridimensional. $Estilo de visualización K_{4,2}$

Grafos bipartitos completos

Un gráfico de estrella dibujado en el plano con aristas de longitud unitaria.

Todos los gráficos en estrella , para , tienen dimensión 2, como se muestra en la figura de la izquierda. Los gráficos en estrella con $m$ igual a 1 o 2 solo necesitan dimensión 1. $Estilo de visualización K_ {m,1}}$ $m\geq 3$

La dimensión de un grafo bipartito completo , para , se puede dibujar como en la figura de la derecha, colocando $m$ vértices en un círculo cuyo radio es menor que una unidad, y los otros dos vértices uno a cada lado del plano del círculo, a una distancia adecuada de él. tiene dimensión 2, ya que se puede dibujar como un rombo unitario en el plano. $Estilo de visualización K_ {m,2}}$ $m\geq 3$ $Estilo de visualización K_{2,2}$

En resumen:

\dim K_{m,n}=1,2,3{\text{ o }}4

, dependiendo de los valores de

m

y

n

.

Dimensión y número cromático

Teorema : La dimensión de cualquier grafo $G$ es siempre menor o igual al doble de su número cromático :

\dim G\leq 2\,\chi (G)

Prueba

Esta prueba también utiliza círculos.

Escribimos $n$ como el número cromático de $G$ y asignamos los números enteros a los $n$ colores. En el espacio euclidiano -dimensional, con sus dimensiones denotadas , disponemos todos los vértices del color $n$ de forma arbitraria en el círculo dado por . $(1..n)$ ${\estilo de visualización 2n}$ $x_{1},x_{2},..x_{2n}$ $x_{2n-2}^{2}+x_{2n-1}^{2}=1/2,\quad x_{i}|(i\neq 2{n-2},i\neq 2{n-1})=0$

Entonces la distancia de un vértice de color $p$ a un vértice de color $q$ está dada por . ${\sqrt {x_{2p-2}^{2}+x_{2p-1}^{2}+x_{2q-2}^{2}+x_{2q-1}^{2}}}={\sqrt {1/2+1/2}}=1$

Dimensión euclidiana

El gráfico de la rueda con un radio quitado tiene dimensión 2.

La definición de la dimensión de un gráfico dada anteriormente dice, de la representación mínima $-n :$

Si dos vértices de $G$ están conectados por una arista, deben estar separados por una distancia unitaria;
Sin embargo, dos vértices separados por una unidad de distancia no están necesariamente conectados por una arista.

Esta definición es rechazada por algunos autores. Una definición diferente fue propuesta en 1991 por Alexander Soifer , para lo que él denominó la dimensión euclidiana de un grafo. ^[4] Anteriormente, en 1980, Paul Erdős y Miklós Simonovits ya la habían propuesto con el nombre de dimensión fiel . ^[5] Según esta definición, la representación minimal $-n$ es aquella tal que dos vértices del grafo están conectados si y solo si sus representaciones están a una distancia de 1.

Las figuras de la derecha muestran la diferencia entre estas definiciones, en el caso de un grafo de rueda que tiene un vértice central y seis vértices periféricos, al que se le ha quitado un radio. Su representación en el plano permite dos vértices a distancia 1, pero no están conectados.

Escribimos esta dimensión como . Nunca es menor que la dimensión definida anteriormente: $\nombre del operador {Edim} G$

\dim G\leq \nombre del operador {Edim} G

Dimensión euclidiana y grado máximo

Paul Erdős y Miklós Simonovits demostraron el siguiente resultado en 1980: ^[5]

Teorema : La dimensión euclidiana de un grafo $G$ no es mayor que el doble de su grado máximo más uno:

\operatorname {Edim} G\leq 2\,\Delta (G)+1

Complejidad computacional

Es NP-hard , y más específicamente completo para la teoría existencial de los números reales , probar si la dimensión o la dimensión euclidiana de un grafo dado es como máximo un valor dado. El problema sigue siendo difícil incluso para probar si la dimensión o la dimensión euclidiana es dos. ^[6]

Referencias

^ Algunos matemáticos consideran esto estrictamente como una " inmersión ", pero muchos teóricos de grafos, incluidos Erdős, Harary y Tutte, utilizan el término " incrustación ".
^ Erdős, P.; Harary, F.; Tutte, WT (1965). "Sobre la dimensión de un grafo" (PDF) . Mathematika . 12 (2): 118–122. doi :10.1112/s0025579300005222. hdl : 2027.42/152495 .
^ Kavangh, Ryan. "Exploraciones sobre la dimensionalidad de los gráficos" (PDF) . Consultado el 16 de agosto de 2018 .
^ Soifer, Alexander (2009). El libro de colorear matemático . Springer. ISBN 978-0-387-74640-1.
^ ab Erdős, P.; Simonovits, M. (1980). "Sobre el número cromático de grafos geométricos". Ars Combinatoria . 9 : 229–246. CiteSeerX 10.1.1.210.6641 . Zbl 0466.05031.
^ Schaefer, Marcus (2013), "Realizabilidad de grafos y vínculos", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer, págs. 461–482, CiteSeerX 10.1.1.220.9651 , doi :10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.

[1] Algunos matemáticos consideran esto estrictamente como una " inmersión ", pero muchos teóricos de grafos, incluidos Erdős, Harary y Tutte, utilizan el término " incrustación ".

[2] Erdős, P.; Harary, F.; Tutte, WT (1965). "Sobre la dimensión de un grafo" (PDF) . Mathematika . 12 (2): 118–122. doi :10.1112/s0025579300005222. hdl : 2027.42/152495 .

[3] Kavangh, Ryan. "Exploraciones sobre la dimensionalidad de los gráficos" (PDF) . Consultado el 16 de agosto de 2018 .

[4] Soifer, Alexander (2009). El libro de colorear matemático . Springer. ISBN 978-0-387-74640-1.

[esi-5] Erdős, P.; Simonovits, M. (1980). "Sobre el número cromático de grafos geométricos". Ars Combinatoria . 9 : 229–246. CiteSeerX 10.1.1.210.6641 . Zbl 0466.05031.

[6] Schaefer, Marcus (2013), "Realizabilidad de grafos y vínculos", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer, págs. 461–482, CiteSeerX 10.1.1.220.9651 , doi :10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4.