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 gráfico químico que representa el 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 celosía .
Historia
El índice de Wiener lleva el nombre de 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] Basado en 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 se ha estudiado en matemáticas puras, bajo varios nombres que incluyen 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 proximidad 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]
Ejemplo
El butano (C 4 H 10 ) tiene dos isómeros estructurales diferentes : n- butano, con una estructura lineal de cuatro átomos de carbono, e 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.
n-butano
Isobutano
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 entre sí (los tres pares de centro hoja) y tres pares a distancia dos (los pares hoja-hoja). Por 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, como el gráfico de n -butano, [8] y para cualquier -vertex estrella tales como la gráfica de isobutano. [9]
Por lo tanto, 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.
Relación con las propiedades químicas.
Wiener mostró que el número índice de Wiener está estrechamente relacionado con los puntos de ebullición de las moléculas de alcanos . [2] Un trabajo posterior sobre las relaciones cuantitativas estructura-actividad mostró que también se correlaciona con otras cantidades, incluidos los parámetros de su punto crítico , [10] la densidad , tensión superficial y viscosidad de su fase líquida, [11] y la van der Waals área de superficie de la molécula. [12]
Cálculo en gráficos arbitrarios
El índice de Wiener se puede calcular directamente usando 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 una ruta es solo su número de bordes), estas distancias se pueden calcular repitiendo un algoritmo de búsqueda de amplitud primero , 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 el 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. 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]
Cálculo en tipos especiales de gráfico.
Cuando el gráfico subyacente es un árbol (como ocurre, por ejemplo, con los alcanos originalmente estudiados por Wiener), el índice de Wiener puede calcularse 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 las rutas 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 tales 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 con los pesos de sus dos extremos. Si v es un vértice de la hoja del árbol, entonces el índice de Wiener del árbol puede calcularse fusionando v con su padre (sumando sus pesos juntos), 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 el borde de v a su padre. Al eliminar repetidamente las hojas de esta manera, el índice de Wiener se puede calcular en tiempo lineal. [13]
Para gráficos que se construyen como productos de gráficos más simples, el índice de Wiener del gráfico de productos 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 de borde a borde) se pueden incrustar isométricamente en el producto cartesiano de tres árboles, lo que permite que sus índices de Wiener se calculen en tiempo lineal utilizando la fórmula del producto junto con el árbol de tiempo lineal. algoritmo. [22]
Problema inverso
Gutman y Yeh (1995) consideraron el problema de determinar qué números se pueden representar como el índice de Wiener de un gráfico. [23] Demostraron que todos menos dos números enteros positivos tienen tal representación; las dos excepciones son los números 2 y 5, que no son el índice Wiener de ningún gráfico. Para las gráficas que deben ser bipartitas, encontraron que, nuevamente, casi todos los números enteros se pueden representar, con un conjunto más grande de excepciones: ninguno de los números en el conjunto
- {2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39}
se puede representar 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 se pueden representar como índices de Wiener de árboles, con un conjunto de 49 valores excepcionales:
- 2, 3, 5, 6, 7, 8, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 26, 27, 30, 33, 34, 37, 38, 39, 41, 43, 45, 47, 51, 53, 55, 60, 61, 69, 73, 77, 78, 83, 85, 87, 89, 91, 99, 101, 106, 113, 147, 159 (secuencia A122686 en la OEIS )
La conjetura fue probada más tarde por Wagner, Wang y Yu. [24] [25]
Referencias
- ^ Rouvray, Dennis H. (2002), "El rico legado de medio siglo del índice Wiener", en Rouvray, Dennis H .; King, Robert Bruce (eds.), Topology in Chemistry: Discrete Mathematics of Molecules , Horwood Publishing, págs. 16–37.
- ^ a b Wiener, H. (1947), "Determinación estructural de los puntos de ebullición de la parafina", Journal of the American Chemical Society , 1 (69): 17-20, doi : 10.1021 / ja01193a005.
- ^ Todeschini, Roberto; Consonni, Viviana (2000), Manual de descriptores moleculares , Wiley, ISBN 3-527-29913-0.
- ^ Rouvray (2002) . Ver en particular la Tabla 2 en la p. 32.
- ^ Harary, Frank (1959), "Status and contrastatus", Sociometry , 22 : 23–43, doi : 10.2307 / 2785610 , MR 0134798
- ^ a b Entringer, RC; Jackson, DE; Snyder, DA (1976), "Distancia en gráficos", Checoslovaco Mathematical Journal , 26 (101): 283-296, MR 0543771.
- ^ Šoltés, Ľubomír (1991), "Transmisión en gráficos: un límite y eliminación de vértices", Mathematica Slovaca , 41 (1): 11-16, MR 1094978.
- ↑ Comodescribe Rouvray (2002) , esta fórmula ya fue dada por Wiener (1947) .
- ^ Bonchev, D .; Trinajstić, N. (1977), "Teoría de la información, matriz de distancia y ramificación molecular", Journal of Chemical Physics , 67 (10): 4517–4533, Bibcode : 1977JChPh..67.4517B , doi : 10.1063 / 1.434593 , hdl : 10338.dmlcz / 104047.
- ^ Stiel, Leonard I .; Thodos, George (1962), "Los puntos de ebullición normales y las constantes críticas de los hidrocarburos alifáticos saturados", AIChE Journal , 8 (4): 527–529, doi : 10.1002 / aic.690080421.
- ^ Rouvray, DH; Crafford, BC (1976), "La dependencia de las propiedades físico-químicas de los factores topológicos", South African Journal of Science , 72 : 47.
- ^ Gutman, Ivan; Körtvélyesi, T. (1995), "Índices de Wiener y superficies moleculares", Zeitschrift für Naturforschung , 50a : 669–671.
- ^ a b c Mohar, Bojan ; Pisanski, Tomaž (1988), "Cómo calcular el índice de Wiener de un gráfico", Journal of Mathematical Chemistry , 2 (3): 267–277, doi : 10.1007 / BF01167206 , MR 0966088.
- ^ Floyd, Robert W. (junio de 1962), "Algorithm 97: Shortest Path", Communications of the ACM , 5 (6): 345, doi : 10.1145 / 367766.368168.
- ^ Warshall, Stephen (enero de 1962), "Un teorema sobre matrices booleanas", Journal of the ACM , 9 (1): 11-12, doi : 10.1145 / 321105.321107.
- ^ Johnson, Donald B. (1977), "Algoritmos eficientes para rutas más cortas en redes dispersas", Journal of the ACM , 24 (1): 1–13, doi : 10.1145 / 321992.321993.
- ^ Bersohn, Malcom (1983), "Un algoritmo rápido para el cálculo de la matriz de distancia de una molécula", Journal of Computational Chemistry , 4 (1): 110-113, doi : 10.1002 / jcc.540040115.
- ^ Müller, WR; Szymanski, K .; Knop, JV; Trinajstić, N. (1987), "Un algoritmo para la construcción de la matriz de distancia molecular", Journal of Computational Chemistry , 8 (2): 170-173, doi : 10.1002 / jcc.540080209.
- ^ Canfield, ER; Robinson, RW; Rouvray, DH (1985), "Determinación del índice de ramificación molecular de Wiener para el árbol general", Journal of Computational Chemistry , 6 (6): 598–609, doi : 10.1002 / jcc.540060613 , MR 0824918.
- ^ Cabello, Sergio; Knauer, Christian (2009), "Algoritmos para gráficos de ancho de árbol acotado mediante búsqueda de rango ortogonal", Geometría computacional , 42 (9): 815–824, doi : 10.1016 / j.comgeo.2009.02.001 , MR 2543804.
- ^ Yeh, Yeong Nan; Gutman, Ivan (1994), "Sobre la suma de todas las distancias en gráficos compuestos", Matemáticas discretas , 135 (1–3): 359–365, doi : 10.1016 / 0012-365X (93) E0092-I , MR 1310892.
- ^ Chepoi, Victor; Klavžar, Sandi (1997), "El índice de Wiener y el índice de Szeged de sistemas benzenoides en tiempo lineal", Journal of Chemical Information and Computer Sciences , 37 (4): 752–755, doi : 10.1021 / ci9700079. Para algoritmos anteriores para bencenoides basados en su estructura de cubo parcial , consulte Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Etiquetado de sistemas benzenoides que refleja las relaciones vértice-distancia" (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi : 10.1021 / ci00025a030.
- ^ Gutman, Ivan; Yeh, Yeong-Nan (1995), "La suma de todas las distancias en gráficos bipartitos", Mathematica Slovaca , 45 (4): 327–334, MR 1387048.
- ^ Wagner, Stephan G. (2006), "Una clase de árboles y su índice de Wiener", Acta Applicandae Mathematicae , 91 (2): 119-132, doi : 10.1007 / s10440-006-9026-5 , MR 2249544.
- ^ Wang, Hua; Yu, Guang (2006), "Todos menos 49 números son índices de árboles de Wiener", Acta Applicandae Mathematicae , 92 (1): 15-20, doi : 10.1007 / s10440-006-9037-2 , MR 2263469.
enlaces externos
- Weisstein, Eric W. "Índice de Wiener" . MathWorld .