En teoría de grafos , un grafo de Harris se define como un grafo euleriano , resistente y no hamiltoniano . [1] [2] Los grafos de Harris se introdujeron en 2013 cuando, en la Universidad de Michigan , Harris Spungen conjeturó que un grafo euleriano resistente sería suficiente para ser hamiltoniano . [3] Sin embargo, Douglas Shaw refutó esta conjetura , descubriendo un contraejemplo con un orden de 9 y un tamaño de 14. [1] Actualmente, hay 241.375 grafos de Harris conocidos . [2] El grafo de Harris mínimo , el grafo de Hirotaka , tiene un orden de 7 y un tamaño de 12. [1] [2]
Un k-percebe es un camino entre dos nodos de longitud k donde cada nodo en el camino tiene un grado de 2. La floración es el proceso de agregar un 2-percebe entre dos nodos en el camino más corto entre dos nodos de grado impar . La floración de un grafo resistente , no hamiltoniano que tiene un número par de nodos con grados impares produce un grafo de Harris . [2]
Si se agrega una rueda de 5 entre un borde en un gráfico de Harris y otro borde en otro gráfico de Harris , y se conectan entre sí dos nodos de cada rueda de 5 que no estaban conectados al gráfico original , entonces el resultado será un gráfico de Harris . [2]
Reemplazar una arista de un gráfico de Harris existente con un percebe de dos puntas crea un gráfico de Harris ya que se conservarán todos los grados anteriores, mientras que el percebe tiene un grado de 2 por definición, por lo que el gráfico sigue siendo euleriano . Dado que ahora es aún más difícil que el gráfico sea hamiltoniano , y dado que la tenacidad del gráfico sigue siendo la misma, agregar un percebe en cualquier lugar mantiene el gráfico euleriano , tenaz y no hamiltoniano. [2]
El gráfico de Hirotaka es el gráfico de Harris mínimo con orden 7 y tamaño 12. [1] [2] Douglas Shaw demostró que es mínimo, y el código Java escrito por Shubhra Mishra y Marco Troper demostró que es único. [2]
El primer gráfico de Harris descubierto fue el gráfico de Shaw , que tiene orden 9 y tamaño 14. [1] [2] [3]
El gráfico de Harris mínimo sin percebes , o gráfico de López , tiene orden 13 y tamaño 33. Fue creado en respuesta a una conjetura de que los gráficos de Harris sin percebes no existen. [2]
Después de que Harris Spungen hiciera su conjetura en 2013, [3] Doug Shaw descubrió poco después un contraejemplo , el grafo de Harris . Jayna Fishman y Elizabeth Petrie encontraron dos grafos de Harris más en el mismo año. Durante los siguientes años, se descubrieron tres grafos de Harris más , hasta que Hirotaka Yoneda descubrió lo que se pensaba que era el grafo de Harris mínimo en 2018. [1] En 2023, Akshay Anand implementó un verificador de grafos de Harris en Java . [4] Ese mismo año, se encontraron 241.375 grafos de Harris de orden 12 o menos, y se demostró que el grafo de Hirotaka era único mediante el código escrito por Shubhra Mishra y Marco Troper. [2]
Los gráficos de Harris son particularmente valiosos para la enseñanza de la teoría de grafos porque poseen propiedades y métodos de fácil comprensión para encontrarlas y verificarlas. [1] [2] Ofrecen un equilibrio ideal entre desafío y accesibilidad, lo que los convierte en un problema atractivo para estudiantes de varios niveles. [3]
Trabajar con gráficos de Harris alienta a los estudiantes a experimentar con diferentes conceptos y soluciones, lo que promueve la creatividad y el pensamiento matemático. Este proceso mantiene a los estudiantes comprometidos y colaborando entre sí, ya que a menudo trabajan juntos para verificar posibles soluciones, lo que mejora el trabajo en equipo y las habilidades de resolución de problemas colectiva. [3]