Resumen

Un politopo convexo es el casco convexo de un conjunto finito de puntos en el espacio euclidiano . Preservando la relacin de adyacencia-incidencia entre los vrtices de un politopo, se construye su grafo estructural. Un grafo se denomina Hamilton-conectado si existe al menos un camino Hamiltoniano entre cualquiera de sus dos vrtices. El ndice de desvo se define como la suma de las longitudes de las distancias ms largas, es decir, los desvos entre vrtices de un grafo. Los grafos Hamiltonianos y Hamilton-conectados tienen diversas aplicaciones en informtica e ingeniera elctrica, mientras que el ndice de desvo tiene importantes aplicaciones en qumica. Comprobar si un grafo est conectado por Hamilton y calcular el ndice de desvos de un grafo arbitrario son problemas NP-completos. En este trabajo estudiamos estos problemas simultneamente para ciertas familias de politopos convexos. Construimos dos familias infinitas de politopos convexos conectados por Hamilton. La conectividad Hamilton se demuestra construyendo caminos Hamiltonianos entre cualquier par de vrtices. A continuacin, utilizamos la conectividad Hamilton para calcular el ndice de desvo de estas familias. Tambin se ha construido una familia de politopos convexos no conectados por Hamilton para demostrar que no todas las familias de politopos convexos estn conectadas por Hamilton.

• Materias:Algoritmos (Matemáticas) Algebra Ingeniería Lógica matemática Matemáticas
• Subjects:Agorithms (Math) Algebra Engineering Mathematical logic mathematics
• Palabras claves:Politopo convexo; Hamilton-conectado; índice de desvío; Grafo; Camino hamiltoniano; NP-completo
• Keywords:Convex polytope; Hamilton-connected; Detour index; Graph; Hamiltonian path; NP-complete