Biblioteca122.294 documentos en línea

Artículo

On Hamilton-Connectivity and Detour Index of Certain Families of Convex PolytopesSobre la conectividad de Hamilton y el índice de desvío de ciertas familias de politopos convexos

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.

  • Tipo de documento:
  • Formato:pdf
  • Idioma:Inglés
  • Tamaño: Kb

Cómo citar el documento

Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.

Este contenido no est� disponible para su tipo de suscripci�n

Información del documento