En la teoría química de grafos , 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 representa los no- átomos de hidrógeno en la molécula. [1]
El índice de Wiener se puede utilizar para la representación de redes informáticas y para mejorar la seguridad del hardware de red .
El índice de Wiener lleva el nombre de Harry Wiener , quien lo introdujo en 1947; Wiener lo llamó entonces "el número de ruta". [2] Es el índice topológico más antiguo relacionado con la ramificación molecular. [3] En base a su éxito, muchos otros índices topológicos de gráficos químicos, basados en información en la matriz de distancias del gráfico, se han desarrollado posteriormente al trabajo de Wiener. [4]
La misma cantidad también ha sido estudiada en matemáticas puras, bajo varios nombres, incluido el estado bruto, [5] la distancia de un gráfico, [6] y la transmisión. [7] El índice de Wiener también está estrechamente relacionado con la centralidad de cercanía de un vértice en un gráfico, 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 con frecuencia 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 uno del otro, 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 distancias uno del otro (los tres pares hoja-centro) y tres pares a distancia dos (los pares hoja-hoja). Por lo tanto, su índice de Wiener es
Estos números son ejemplos de fórmulas para casos especiales del índice de Wiener: es para cualquier gráfico de trayectoria de vértice, como el gráfico de n -butano, [8] y para cualquier estrella de vértice , 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 número índice de Wiener está estrechamente correlacionado con los puntos de ebullición de las moléculas de alcano . [2] Trabajos posteriores sobre las relaciones cuantitativas estructura-actividad mostraron que también está correlacionada 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 la furgoneta . Área de superficie 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 está ponderado (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 ym es su número de aristas.
Para gráficos ponderados, se puede utilizar el algoritmo Floyd-Warshall [13] [14] [15] o el algoritmo de Johnson , [16] con tiempo de ejecución O( n 3 ) u O( nm + n 2 log n ) respectivamente. En la literatura de informática química también se han desarrollado algoritmos alternativos pero menos eficientes basados en la multiplicación repetida de matrices . [17] [18]
Cuando el gráfico subyacente es un árbol (como ocurre, por ejemplo, con 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 un solo borde 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 desde árboles hasta 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 se puede calcular 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 las rutas. que pasan por la arista desde v hasta su padre. Quitando repetidamente las hojas de esta manera, se puede calcular el índice de Wiener en tiempo lineal. [13]
Para gráficas que se construyen como productos de gráficas más simples, el índice de Wiener de la gráfica 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 pegando hexágonos regulares de borde a 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 árbol de tiempo lineal. algoritmo. [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 tal 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 gráficos que deben ser bipartitos, encontraron que nuevamente casi todos los números enteros se pueden representar, con un conjunto mayor de excepciones: ninguno de los números del conjunto
se puede representar como el índice de Wiener de un gráfico bipartito.
Gutman y Yeh conjeturaron, pero no pudieron demostrar, 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 demostrada más tarde por Wagner, Wang y Yu. [24] [25]
