En la teoría de grafos químicos , el índice de Wiener (también número de Wiener ) introducido por Harry Wiener , es un índice topológico de una molécula , definido como la suma de las longitudes de los caminos más cortos entre todos los pares de vértices en el grafo químico que representan los átomos distintos del hidrógeno en la molécula. [1]
El índice de Wiener se puede utilizar para la representación de redes de computadoras y para mejorar la seguridad del hardware de red .
El índice de Wiener debe su nombre a Harry Wiener , quien lo introdujo en 1947; en ese momento, Wiener lo llamó el "número de ruta". [2] Es el índice topológico más antiguo relacionado con la ramificación molecular. [3] Basándose en su éxito, se han desarrollado muchos otros índices topológicos de gráficos químicos, basados en información en la matriz de distancia del gráfico, posteriormente al trabajo de Wiener. [4]
La misma cantidad también ha sido estudiada en matemáticas puras, bajo varios nombres incluyendo el estado bruto, [5] la distancia de un grafo, [6] y la transmisión. [7] El índice de Wiener también está estrechamente relacionado con la centralidad de proximidad de un vértice en un grafo, una cantidad inversamente proporcional a la suma de todas las distancias entre el vértice dado y todos los demás vértices que se ha utilizado frecuentemente en sociometría y la teoría de redes sociales . [6]
El butano (C 4 H 10 ) tiene dos isómeros estructurales diferentes : el n -butano, con una estructura lineal de cuatro átomos de carbono, y el isobutano , con una estructura ramificada. El gráfico químico del n -butano es un gráfico de trayectoria de cuatro vértices , y el gráfico químico del isobutano es un árbol con un vértice central conectado a tres hojas.
La molécula de n -butano tiene tres pares de vértices a una distancia entre sí, dos pares a una distancia dos y un par a una distancia tres, por lo que su índice de Wiener es
La molécula de isobutano tiene tres pares de vértices a una distancia entre sí (los tres pares hoja-centro), y tres pares a una distancia dos (los pares hoja-hoja). Por lo tanto, su índice de Wiener es
Estos números son instancias de fórmulas para casos especiales del índice de Wiener: es para cualquier gráfico de ruta de vértice tal como el gráfico de n -butano, [8] y para cualquier estrella de vértice tal como el gráfico de isobutano. [9]
Así, aunque estas dos moléculas tienen la misma fórmula química y el mismo número de enlaces carbono-carbono y carbono-hidrógeno, sus diferentes estructuras dan lugar a diferentes índices de Wiener.
Wiener demostró que el índice de Wiener está estrechamente relacionado con los puntos de ebullición de las moléculas de alcano . [2] Trabajos posteriores sobre relaciones cuantitativas estructura-actividad mostraron que también está relacionado con otras cantidades, incluidos los parámetros de su punto crítico , [10] la densidad , la tensión superficial y la viscosidad de su fase líquida, [11] y el área superficial de van der Waals de la molécula. [12]
El índice de Wiener se puede calcular directamente utilizando un algoritmo para calcular todas las distancias por pares en el gráfico. Cuando el gráfico no tiene ponderación (por lo que la longitud de un camino es solo su número de aristas), estas distancias se pueden calcular repitiendo un algoritmo de búsqueda en amplitud , una vez para cada vértice inicial. [13] El tiempo total para este enfoque es O( nm ), donde n es el número de vértices en el gráfico y m es su número de aristas.
Para los gráficos ponderados, se puede utilizar en su lugar el algoritmo Floyd-Warshall [13] [14] [15] o el algoritmo de Johnson [16] con un tiempo de ejecución de O( n 3 ) o de O( nm + n 2 log n ) respectivamente. También se han desarrollado algoritmos alternativos pero menos eficientes basados en la multiplicación repetida de matrices dentro de la literatura de informática química. [17] [18]
Cuando el gráfico subyacente es un árbol (como es cierto, por ejemplo, para los alcanos estudiados originalmente por Wiener), el índice de Wiener se puede calcular de manera más eficiente. Si el gráfico se divide en dos subárboles eliminando una sola arista e , entonces su índice de Wiener es la suma de los índices de Wiener de los dos subárboles, junto con un tercer término que representa los caminos que pasan por e . Este tercer término se puede calcular en tiempo lineal calculando la suma de las distancias de todos los vértices desde e dentro de cada subárbol y multiplicando las dos sumas. [19] Este algoritmo de divide y vencerás se puede generalizar de árboles a gráficos de ancho de árbol acotado y conduce a algoritmos de tiempo casi lineal para dichos gráficos. [20]
Un método alternativo para calcular el índice de Wiener de un árbol, de Bojan Mohar y Tomaž Pisanski , funciona generalizando el problema a gráficos con vértices ponderados, donde el peso de un camino es el producto de su longitud por los pesos de sus dos puntos finales. Si v es un vértice de hoja del árbol, entonces el índice de Wiener del árbol puede calcularse fusionando v con su padre (sumando sus pesos), calculando el índice del árbol más pequeño resultante y agregando un término de corrección simple para los caminos que pasan por el borde desde v hasta su padre. Al eliminar repetidamente hojas de esta manera, el índice de Wiener puede calcularse en tiempo lineal. [13]
En el caso de los gráficos que se construyen como productos de gráficos más simples, el índice de Wiener del gráfico del producto a menudo se puede calcular mediante una fórmula simple que combina los índices de sus factores. [21] Los bencenoides (gráficos formados al pegar hexágonos regulares borde con borde) se pueden incrustar isométricamente en el producto cartesiano de tres árboles, lo que permite calcular sus índices de Wiener en tiempo lineal utilizando la fórmula del producto junto con el algoritmo del árbol de tiempo lineal. [22]
Gutman y Yeh (1995) consideraron el problema de determinar qué números pueden representarse como el índice de Wiener de un gráfico. [23] Demostraron que todos los números enteros positivos, excepto dos, tienen esa representación; las dos excepciones son los números 2 y 5, que no son el índice de Wiener de ningún gráfico. Para los gráficos que deben ser bipartitos, descubrieron que nuevamente casi todos los números enteros pueden representarse, con un conjunto más grande de excepciones: ninguno de los números en el conjunto
puede representarse como el índice de Wiener de un gráfico bipartito.
Gutman y Yeh conjeturaron, pero no pudieron probar, una descripción similar de los números que pueden representarse como índices de Wiener de árboles, con un conjunto de 49 valores excepcionales:
La conjetura fue probada posteriormente por Wagner, Wang y Yu. [24] [25]
