Gráfico de Herschel
En la 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, el grafo poliédrico no hamiltoniano más pequeño . Lleva el nombre del astrónomo británico Alexander Stewart Herschel .
El gráfico de Herschel es un gráfico plano : se puede dibujar en el plano sin que ninguno de sus bordes se cruce. También está conectado por 3 vértices : la eliminación de dos de sus vértices deja un subgrafo conectado . Es un gráfico bipartito : sus vértices se pueden separar en dos subconjuntos de cinco y seis vértices respectivamente, de modo que cada borde tiene un punto final en cada subconjunto (los subconjuntos rojo y azul en la imagen). Al igual que con cualquier gráfico bipartito, el gráfico de Herschel es un gráfico perfecto : el número cromático de cada subgrafo inducido es igual al tamaño de la camarilla más grande de ese subgrafo. También tiene índice cromático 4, circunferencia 4, radio 3 y diámetro 4.
El gráfico de Herschel es plano y está conectado por 3 vértices, por lo que el teorema de Steinitz dice que es un gráfico poliédrico : existe un poliedro convexo (un eneaedro ) que tiene el gráfico de Herschel como esqueleto . [2] Este poliedro tiene nueve cuadriláteros por caras, que se pueden elegir para formar tres rombos y seis cometas . [1]
Su poliedro dual es un prisma triangular rectificado , formado como el casco convexo de los puntos medios de los bordes de un prisma triangular . Este poliedro tiene la propiedad de que sus caras no se pueden numerar de tal forma que aparezcan números consecutivos en caras adyacentes, y que el primer y último número también estén en caras adyacentes. Debido a que las numeraciones de caras poliédricas de este tipo se utilizan como "contadores de vida spindown" en el juego Magic: The Gathering , Constantinides & Constantinides (2018) nombran la realización del poliedro canónico de este poliedro dual como "la némesis del Lich". [3]
Como gráfico bipartito que tiene un número impar de vértices, el gráfico 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 números iguales de ambos tipos de vértice y debe tener una longitud par. Por lo tanto, un ciclo que pasa una vez por cada uno de los once vértices no puede existir en el gráfico de Herschel. Es el gráfico poliédrico no hamiltoniano más pequeño, ya sea que el tamaño del gráfico se mida en términos de su número de vértices, aristas o caras. [4] Existen otros gráficos poliédricos con 11 vértices y sin ciclos hamiltonianos (en particular, el gráfico de Goldner-Harary [5]) pero ninguno con menos bordes. [2]
Todos menos tres de los vértices del gráfico de Herschel tienen grado tres. La conjetura de Tait [6] establece que un gráfico poliédrico en el que cada vértice tiene un grado tres debe ser hamiltoniano, pero esto fue refutado cuando WT Tutte proporcionó un contraejemplo, el gráfico de Tutte mucho más grande . [7] Un refinamiento de la conjetura de Tait, la conjetura de Barnette de que cada grafo poliédrico bipartito 3-regular es hamiltoniano, permanece abierta. [8]
