En teoría de grafos , una rama de las matemáticas , el grafo de Herschel es un grafo bipartito no dirigido con 11 vértices y 18 aristas. Es un grafo poliédrico (el grafo de un poliedro convexo ), y es el grafo poliédrico más pequeño que no tiene un ciclo hamiltoniano , un ciclo que pasa por todos sus vértices. Recibe su nombre en honor al astrónomo británico Alexander Stewart Herschel , debido a los estudios de Herschel sobre los ciclos hamiltonianos en grafos poliédricos (pero no de este grafo).
El grafo de Herschel tiene tres vértices de grado cuatro (los tres vértices azules alineados verticalmente en el centro de la ilustración) y ocho vértices de grado tres. Cada uno de los dos vértices de grado cuatro comparten dos vecinos de grado tres, formando un ciclo de cuatro vértices con estos vecinos compartidos. Hay tres de estos ciclos, que pasan por seis de los ocho vértices de grado tres (rojos en la ilustración). Otros dos vértices de grado tres (azules) no participan en estos ciclos de cuatro vértices; en cambio, cada uno es adyacente a tres de los seis vértices rojos. [1]
El grafo de Herschel es un grafo poliédrico ; esto significa que es un grafo plano , uno que puede dibujarse en el plano sin que ninguna de sus aristas se cruce, y que es conexo por 3 vértices : la eliminación de dos de sus vértices deja un subgrafo conexo . [1] Es un grafo bipartito : cuando está coloreado con cinco vértices azules y seis rojos, como se ilustra, cada arista tiene un punto final rojo y un punto final azul. [2]
Tiene simetría diedral de orden 6 , para un total de 12 miembros de su grupo de automorfismos . Los vértices de grado cuatro se pueden permutar arbitrariamente, lo que da seis permutaciones y, además, para cada permutación de los vértices de grado cuatro, hay una simetría que mantiene fijos estos vértices e intercambia pares de vértices de grado tres. [1]
Por el teorema de Steinitz , todo grafo que es plano y conexo por 3 vértices tiene un poliedro convexo con el grafo como su esqueleto . [3] Debido a que el grafo de Herschel tiene estas propiedades, [1] puede representarse de esta manera por un poliedro convexo, un eneaedro que tiene un poliedro que tiene nueve cuadriláteros como sus caras. [4] Esto puede elegirse de modo que cada automorfismo del grafo corresponda a una simetría del poliedro, en cuyo caso tres de las caras serán rombos o cuadrados, y las otras seis serán cometas . [1]
El poliedro dual es un prisma triangular rectificado , que puede formarse como la envoltura convexa de los puntos medios de las aristas de un prisma triangular . Cuando se construye de esta manera, tiene tres caras cuadradas en los mismos planos que las caras cuadradas del prisma, dos caras de triángulos equiláteros en los planos de los extremos triangulares del prisma y seis caras de triángulos isósceles más . Este poliedro tiene la propiedad de que sus caras no pueden numerarse de tal manera que aparezcan números consecutivos en caras adyacentes, y de tal manera que el primer y el último número también estén en caras adyacentes, porque tal numeración correspondería necesariamente a un ciclo hamiltoniano en el gráfico de Herschel. Las numeraciones de caras poliédricas de este tipo se utilizan como "contadores de vidas de spindown" en el juego Magic: The Gathering , para rastrear las vidas de los jugadores, girando el poliedro hacia una cara adyacente cada vez que se pierde una vida. Una carta en el juego, el Lich, permite a los jugadores regresar de un estado casi perdido con una sola vida a su número inicial de vidas. Debido a que el poliedro dual para el gráfico de Herschel no se puede numerar de tal manera que este paso conecte caras adyacentes, Constantinides y Constantinides (2018) nombran la realización poliédrica canónica de este poliedro dual como "la némesis del Lich". [5]
Como grafo bipartito que tiene un número impar de vértices, el grafo de Herschel no contiene un ciclo hamiltoniano (un ciclo de aristas que pasa por cada vértice exactamente una vez). Porque, en cualquier grafo bipartito, cualquier ciclo debe alternar entre los vértices a cada lado de la bipartición, y por lo tanto debe contener cantidades iguales de ambos tipos de vértices y debe tener una longitud par. Por lo tanto, un ciclo que pase una vez por cada uno de los once vértices no puede existir en el grafo de Herschel. Un grafo se llama hamiltoniano siempre que contenga un ciclo hamiltoniano, por lo que el grafo de Herschel no es hamiltoniano. Tiene el menor número de vértices, el menor número de aristas y el menor número de caras de cualquier grafo poliédrico no hamiltoniano. [6] Existen otros grafos poliédricos con 11 vértices y sin ciclos hamiltonianos (notablemente el grafo de Goldner-Harary ) [7] pero ninguno con menos aristas. [6]
Todos los vértices del grafo de Herschel, excepto tres, tienen grado tres. Un grafo se denomina cúbico o 3-regular cuando todos sus vértices tienen grado tres. PG Tait conjeturó [8] que un grafo poliédrico 3-regular debe ser hamiltoniano; esto fue refutado cuando WT Tutte proporcionó un contraejemplo, el grafo de Tutte , que es mucho más grande que el grafo de Herschel. [9] Un refinamiento de la conjetura de Tait, la conjetura de Barnette de que todo grafo poliédrico bipartito 3-regular es hamiltoniano, permanece abierta. [10]
Todo grafo planar maximalista que no tenga un ciclo hamiltoniano tiene un grafo de Herschel como grafo menor . Se conjetura que el grafo de Herschel es uno de los tres grafos no hamiltonianos con 3 vértices conexos y grafos menores-minimalistas. Los otros dos son el grafo bipartito completo y un grafo formado al dividir el grafo de Herschel y en dos mitades simétricas mediante separadores de tres vértices y luego combinar una mitad de cada grafo. [11]
El grafo de Herschel también proporciona un ejemplo de un grafo poliédrico para el cual el grafo medial no tiene descomposición hamiltoniana en dos ciclos hamiltonianos disjuntos en sus aristas. El grafo medial del grafo de Herschel es un grafo regular de 4 con 18 vértices, uno por cada arista del grafo de Herschel; dos vértices son adyacentes en el grafo medial siempre que las aristas correspondientes del grafo de Herschel sean consecutivas en una de sus caras. [12] Es conexo por 4 vértices y esencialmente conexo por 6 aristas . Aquí, un grafo es conexo por 4 vértices o conexo por aristas si la eliminación de menos de vértices o aristas (respectivamente) no puede desconectarlo. Los grafos planos no pueden ser conexos por 6 aristas, porque siempre tienen un vértice de grado cinco como máximo, y la eliminación de las aristas vecinas desconecta el grafo. La terminología "esencialmente conectado por 6 aristas" significa que se ignora esta forma trivial de desconectar el gráfico y es imposible desconectar el gráfico en dos subgráficos que tengan cada uno al menos dos vértices eliminando cinco aristas o menos. [13]
El grafo de Herschel recibe su nombre de Alexander Stewart Herschel , un astrónomo británico que escribió un artículo temprano sobre el juego icosiano de William Rowan Hamilton . Se trata de un rompecabezas que implica encontrar ciclos hamiltonianos en un poliedro, normalmente el dodecaedro regular . El grafo de Herschel describe el poliedro convexo más pequeño que se puede utilizar en lugar del dodecaedro para dar un juego que no tiene solución. El artículo de Herschel describió soluciones para el juego icosiano solo en los grafos del tetraedro regular y el icosaedro regular ; no describió el grafo de Herschel. [14] El nombre "grafo de Herschel" aparece temprano en un libro de texto de teoría de grafos de John Adrian Bondy y USR Murty , publicado en 1976. [15] El grafo en sí fue descrito anteriormente, por ejemplo por HSM Coxeter . [4]
