En la teoría de grafos geométricos , una rama de las matemáticas, un gráfico de cerilla es un gráfico que se puede dibujar en el plano de tal manera que sus bordes son segmentos de línea de longitud uno que no se cruzan entre sí. Es decir, es un gráfico que tiene una incrustación que es simultáneamente un gráfico de distancia unitaria y un gráfico plano . De manera informal, se pueden hacer gráficos con cerillas colocando cerillas que no se crucen en una superficie plana, de ahí el nombre. [1]
Gráfico de Harborth | |
---|---|
Vértices | 52 |
Bordes | 104 |
Radio | 6 |
Diámetro | 9 |
Circunferencia | 3 |
Tabla de gráficos y parámetros |
Gráfico de tres fósforos regulares | |
---|---|
Vértices | 54 |
Bordes | 81 |
Circunferencia | 5 |
Tabla de gráficos y parámetros |
Gráficos de fósforos regulares
Gran parte de la investigación sobre gráficos de cerillas se ha centrado en gráficos regulares , en los que cada vértice tiene el mismo número de vecinos. Este número se llama grado de la gráfica.
Se sabe que hay gráficas de cerillas que son regulares de cualquier grado hasta 4. Las gráficas completas con uno, dos y tres vértices (un solo vértice, un solo borde y un triángulo) son todas gráficas de cerilla y son 0- , 1- y 2-regulares respectivamente. El gráfico más pequeño de tres fósforos regulares se forma a partir de dos copias del gráfico de diamante colocadas de tal manera que los vértices correspondientes estén a una distancia unitaria entre sí; su doble cubierta bipartita es el gráfico de 8 prismas cruzados . [1]
En 1986, Heiko Harborth presentó el gráfico que llevaría su nombre, Harborth Graph . Con 104 aristas y 52 vértices, es el ejemplo más pequeño conocido de un gráfico de 4 fósforos regular . [2] Es un gráfico rígido . [3]
Cada gráfico de cuatro cerillas regulares contiene al menos 20 vértices. [4] Actualmente se conocen ejemplos de gráficos de cuatro cerillas regulares para todos los vértices ≥ 52, excepto 53, 55, 56, 58, 59, 61 y 62. Los gráficos con 54, 57, 65, 67, 73, 74 , 77 y 85 vértices se publicaron por primera vez en 2016. Para 52, 54, 57, 60 y 64 vértices solo se conoce un ejemplo. De estos cinco gráficos, solo el que tiene 60 vértices es flexible, los otros cuatro son rígidos. [5]
No es posible que un gráfico de cerillas normal tenga un grado superior a cuatro. [4] El gráfico más pequeño de tres fósforos regulares sin triángulos (circunferencia ≥ 4) tiene 20 vértices, como lo demostraron Kurz y Mazzuoccolo. [6] El ejemplo más pequeño conocido de un gráfico de tres cerillas regulares de circunferencia 5 tiene 54 vértices y fue presentado por primera vez por Mike Winkler en 2019. [7]
Complejidad computacional
Es NP-difícil probar si un gráfico plano no dirigido dado se puede realizar como un gráfico de cerilla. [8] [9] Más precisamente, este problema es completo para la teoría existencial de los reales . [10] Kurz (2011) proporciona algunos criterios necesarios fácilmente probados para que un gráfico sea un gráfico de cerillas, pero estos tampoco son criterios suficientes: un gráfico puede pasar las pruebas de Kurz y aún no ser un gráfico de cerillas. [11]
También es NP-completo determinar si un gráfico de cerillas tiene un ciclo hamiltoniano , incluso cuando los vértices del gráfico tienen coordenadas enteras que se dan como parte de la entrada al problema. [12]
Enumeración combinatoria
Los números de gráficos de cerillas distintos (no isomórficos) se conocen para 1, 2, 3, ... hasta diez aristas; ellos son:
Por ejemplo, los tres gráficos diferentes que se pueden hacer con tres cerillas son un gráfico de garra , un gráfico de triángulo y un gráfico de trayectoria de tres bordes .
Clases especiales de gráficos
La uniformidad de las longitudes de los bordes se ha considerado durante mucho tiempo como una cualidad deseable en el dibujo de gráficos , [15] y algunas clases específicas de gráficos planos siempre se pueden dibujar con bordes completamente uniformes.
Cada árbol se puede dibujar de tal manera que, si los bordes de las hojas del árbol fueran reemplazados por rayos infinitos, el dibujo dividiría el plano en regiones poligonales convexas, sin cruces. Para tal dibujo, si las longitudes de cada borde se cambian arbitrariamente, sin cambiar la pendiente del borde, el dibujo permanecerá plano. En particular, es posible elegir que todos los bordes tengan la misma longitud, lo que da como resultado la realización de un árbol arbitrario como un gráfico de cerillas. [dieciséis]
Una propiedad similar es cierta para las gráficas cuadradas , las gráficas planas que se pueden dibujar en el plano de tal manera que cada cara acotada es un cuadrilátero y cada vértice se encuentra en la cara ilimitada o tiene al menos cuatro vecinos. Estos gráficos se pueden dibujar con paralelogramos de todas las caras, de tal manera que si un subconjunto de aristas que son todas paralelas entre sí se alargan o acortan simultáneamente para que sigan teniendo todas la misma longitud, entonces no se puede introducir ningún cruce. En particular, es posible normalizar los bordes para que todos tengan la misma longitud y obtener una realización de cualquier gráfico cuadrado como un gráfico de cerillas. [17]
Clases de gráficos relacionados
Cada gráfico de cerillas es un gráfico de unidad de distancia . Los gráficos de centavos son los gráficos que se pueden representar mediante tangencias de círculos unitarios que no se superponen. Cada gráfico de un centavo es un gráfico de cerillas. Sin embargo, algunos gráficos de cerillas (como el gráfico de cerillas cúbicas de ocho vértices de la primera ilustración) no son gráficos de centavo, porque realizarlos como un gráfico de cerillas hace que algunos vértices no adyacentes estén más cerca que la unidad de distancia entre sí.
Referencias
- ^ a b Weisstein, Eric W. "Gráfico de cerillas" . MathWorld .
- ^ Harborth, Heiko (1994), "Match sticks in the plane", en Guy, RK; Woodrow, RE (eds.), The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canadá, 1986 , Washington, DC: Asociación Matemática de América , págs. 281–288. Como se cita en:Weisstein, Eric W. "Gráfico de cerillas" . MathWorld .
- ^ Gerbracht, Eberhard H.-A. (2011), "Symbol-crunching the Harborth graph", Advances in Applied Mathematics , 47 (2): 276-281, doi : 10.1016 / j.aam.2010.09.003 , MR 2803803. Para obtener detalles adicionales, consulte el preimpreso anterior de Gerbracht "Polinomios mínimos para las coordenadas del gráfico de Harborth" (2006), arXiv: math / 0609360 .
- ^ a b Kurz, Sascha; Pinchasi, Rom (2011), "Gráficos de cerillas regulares", American Mathematical Monthly , 118 (3): 264-267, arXiv : 1401.4372 , doi : 10.4169 / amer.math.monthly.118.03.264 , MR 2800336.
- ^ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2017), "Nuevos gráficos mínimos (4; n) -regulares de cerillas", Geombinatoria , 27 : 26–44, arXiv : 1604.07134.
- ^ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010), "Gráficos de tres cerillas regulares con circunferencia dada", Geombinatoria , 19 : 156-175, arXiv : 1401.4360.
- ^ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2020), "Un gráfico de tres cerillas regulares de circunferencia 5 que consta de 54 vértices", Geombinatoria , 29 : 116-121, arXiv : 1903.04304.
- ^ Eades, Peter ; Wormald, Nicholas C. (1990), "El dibujo de gráfico de longitud de borde fijo es NP-hard", Discrete Applied Mathematics , 28 (2): 111-134, doi : 10.1016 / 0166-218X (90) 90110-X.
- ^ Cabello, Sergio; Demaine, Erik D .; Rote, Günter (2007), "Incrustaciones planas de gráficos con longitudes de borde especificadas" (PDF) , Journal of Graph Algorithms and Applications , 11 (1): 259–276, doi : 10.7155 / jgaa.00145.
- ^ Abel, Zachary; Demaine, Erik D .; Demaine, Martin L .; Eisenstat, Sarah; Lynch, Jayson; Schardl, Tao B. (2016), "¿Quién necesita cruces? Dureza de la rigidez del gráfico plano", en Fekete, Sándor; Lubiw, Anna (eds.), 32o Simposio Internacional sobre Geometría Computacional (SoCG 2016) , Actas Internacionales de Informática de Leibniz (LIPIcs), 51 , Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, págs. : 15, doi : 10.4230 / LIPIcs.SoCG.2016.3 , ISBN 978-3-95977-009-5.
- ^ Kurz, Sascha (2011), "Reconocimiento rápido de gráficos planos de distancia no unitaria", Geombinatoria , 21 (1): 25–33, arXiv : 1401.4375 , MR 2858668.
- ^ Itai, Alon; Papadimitriou, Christos H .; Szwarcfiter, Jayme Luiz (1982), "Rutas de Hamilton en gráficos de cuadrícula", SIAM Journal on Computing , 11 (4): 676–686, doi : 10.1137 / 0211056 , MR 0677661.
- ^ Salvia, Raffaele (2013), Un catálogo de gráficos de cerillas , arXiv : 1303.5965
- ^ Vaisse, Alexis (2015). "Gráficos Matchstick con hasta 10 bordes" .
- ^ Fruchterman, Thomas MJ; Reingold, Edward M. (1991), "Dibujo de gráficos por ubicación dirigida por la fuerza", Software: práctica y experiencia , Wiley, 21 (11): 1129-1164, doi : 10.1002 / spe.4380211102.
- ^ Carlson, Josiah; Eppstein, David (2006), "Árboles con caras convexas y ángulos óptimos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Proceedings of the 14th International Symposium on Graph Drawing , Lecture Notes in Computer Science, 4372 , Springer-Verlag, págs. 77-88, arXiv : cs.CG/0607113 , doi : 10.1007 / 978- 3-540-70904-6_9 , ISBN 978-3-540-70903-9, Señor 2393907.
- ^ Eppstein, David; Wortman, Kevin A. (2011), "Resolución angular óptima para dibujos simétricos de caras", Journal of Graph Algorithms and Applications , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155 / jgaa.00238.