Венский индекс

В химической теории графов , определяемый как сумма длин кратчайших путей между всеми индекс Винера (также число Винера), введенный Гарри Винером, представляет собой топологический индекс молекулы парами вершин химического графа, представляющих не- атомы водорода в молекуле. ^[1]

Индекс Винера можно использовать для представления компьютерных сетей и повышения безопасности аппаратного обеспечения решетки .

История

Индекс Винера назван в честь Гарри Винера , который представил его в 1947 году; в то время Винер называл это «номер пути». ^[2] Это старейший топологический индекс, связанный с молекулярным ветвлением. ^[3] Благодаря его успеху впоследствии после работы Винера были разработаны многие другие топологические индексы химических графов, основанные на информации в матрице расстояний графа. ^[4]

Та же самая величина изучалась и в чистой математике под разными названиями, включая грубый статус, ^[5] расстояние графа, ^[6] и передача. ^[7] Индекс Винера также тесно связан с центральностью близости вершины в графе, величиной, обратно пропорциональной сумме всех расстояний между данной вершиной и всеми другими вершинами, которая часто используется в социометрии и теории социальных сетей . ^[6]

Пример

Бутан (C ₄ H ₁₀ ) имеет два различных структурных изомера : н -бутан с линейным строением из четырех атомов углерода и изобутан с разветвленной структурой. Химический граф н- с четырьмя вершинами бутана представляет собой граф путей , а химический граф изобутана представляет собой дерево с одной центральной вершиной, соединенной с тремя листьями.

Два изомера бутана
н-бутан
изобутан

Молекула н -бутана имеет три пары вершин на расстоянии одна друг от друга, две пары на расстоянии два и одну пару на расстоянии три, поэтому ее индекс Винера равен

3\times 1+2\times 2+1\times 3=10.

Молекула изобутана имеет три пары вершин на расстоянии одна друг от друга (три пары лист-центр) и три пары на расстоянии два (пары лист-лист). Следовательно, его индекс Винера равен

3\times 1+3\times 2=9.

Эти числа являются примерами формул для особых случаев индекса Винера: это $(n^{3}-n)/6$ для любого $n$ -граф вершинного пути, такой как граф н -бутана, ^[8] и $(n-1)^{2}$ для любого $n$ -вершинная звезда , такая как график изобутана. ^[9]

Таким образом, хотя эти две молекулы имеют одинаковую химическую формулу и одинаковое количество углерод-углеродных и углерод-водородных связей, их разная структура приводит к разным индексам Винера.

Связь с химическими свойствами

что число индекса Винера тесно коррелирует с температурой кипения молекул алканов Винер показал , . ^[2] Более поздние работы по количественным связям структура-активность показали, что она также коррелирует с другими величинами, включая параметры ее критической точки . ^[10] плотность фазы , поверхностное натяжение жидкой и вязкость , ^[11] и площадь поверхности Ван-дер-Ваальса молекулы. ^[12]

Расчет в произвольных графах

Индекс Винера можно рассчитать напрямую, используя алгоритм вычисления всех попарных расстояний в графе. Когда граф невзвешен (поэтому длина пути равна количеству ребер), эти расстояния можно вычислить, повторяя алгоритм поиска в ширину один раз для каждой начальной вершины. ^[13] Общее время для этого подхода составляет O( nm ), где n — количество вершин в графе, а m — количество его ребер.

Для взвешенных графов вместо этого можно использовать алгоритм Флойда – Уоршалла. ^[13]^[14]^[15] или алгоритм Джонсона , ^[16] со временем работы O( n ³) или O( нм + n ² log n ) соответственно. Альтернативные, но менее эффективные алгоритмы, основанные на повторном умножении матриц, также были разработаны в литературе по химической информатике. ^[17]^[18]

Расчет в специальных типах графиков

Когда основной граф представляет собой дерево (как это верно, например, для алканов, первоначально изученных Винером), индекс Винера можно рассчитать более эффективно. Если граф разделен на два поддерева путем удаления одного ребра e , то его индекс Винера представляет собой сумму индексов Винера двух поддеревьев вместе с третьим членом, представляющим пути, проходящие через e . Этот третий член можно вычислить за линейное время путем вычисления суммы расстояний всех вершин от e внутри каждого поддерева и умножения двух сумм. ^[19] Этот алгоритм «разделяй и властвуй» можно обобщить от деревьев до графов ограниченной ширины дерева и привести к алгоритмам с почти линейным временем для таких графов. ^[20]

Альтернативный метод расчета индекса Винера дерева, предложенный Бояном Мохаром и Томажем Писански , работает путем обобщения проблемы на графы со взвешенными вершинами, где вес пути является произведением его длины на веса двух его конечных точек. Если v является листовой вершиной дерева, то индекс Винера дерева можно вычислить путем слияния v с его родительским элементом (сложением их весов), вычисления индекса полученного меньшего дерева и добавления простого корректирующего члена для путей. которые проходят через ребро от v к его родителю. Повторно удаляя листья таким образом, индекс Винера можно рассчитать за линейное время. ^[13]

Для графов, построенных как произведения более простых графов, индекс Винера графа произведения часто можно вычислить с помощью простой формулы, объединяющей индексы его факторов. ^[21] Бензеноиды (графы, образованные склеиванием ребер к ребру правильных шестиугольников) можно изометрически вставлять в декартово произведение трех деревьев, что позволяет вычислять их индексы Винера за линейное время с использованием формулы произведения вместе с алгоритмом дерева линейного времени. ^[22]

Обратная задача

Гутман и Йе (1995) рассмотрели проблему определения того, какие числа могут быть представлены как индекс Винера графа. ^[23] Они показали, что все положительные целые числа, кроме двух, имеют такое представление; двумя исключениями являются числа 2 и 5, которые не являются индексом Винера ни на одном графике. Для графов, которые должны быть двудольными, они снова обнаружили, что почти все целые числа могут быть представлены, с большим набором исключений: ни одно из чисел в наборе

{2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39}

можно представить как индекс Винера двудольного графа.

Гутман и Йе предположили, но не смогли доказать, аналогичное описание чисел, которые можно представить как индексы Винера деревьев с набором из 49 исключительных значений:

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 (последовательность А122686 в ОЭИС )

Гипотеза была позже доказана Вагнером, Вангом и Ю. ^[24]^[25]

Ссылки

^ Рувре, Деннис Х. (2002), «Богатое наследие полувекового индекса Винера», Рувре, Деннис Х.; Кинг, Роберт Брюс (ред.), Топология в химии: дискретная математика молекул , Horwood Publishing, стр. 16–37, ISBN 9781898563761 .
^ Перейти обратно: ^а ^б Винер, Х. (1947), «Структурное определение температуры кипения парафина», Журнал Американского химического общества , 1 (69): 17–20, doi : 10.1021/ja01193a005 , PMID 20291038 .
^ Тодескини, Роберто; Консонни, Вивиана (2000), Справочник молекулярных дескрипторов , Wiley, ISBN 3-527-29913-0 .
^ Рувре (2002) . См., в частности, Таблицу 2 на с. 32.
^ Харари, Фрэнк (1959), «Статус и контраст», Социометрия , 22 (1): 23–43, doi : 10.2307/2785610 , JSTOR 2785610 , MR 0134798
^ Перейти обратно: ^а ^б Энтрингер, RC; Джексон, Делавэр; Снайдер, Д.А. (1976), «Расстояние в графиках», Чехословацкий математический журнал , 26 (101): 283–296, doi : 10.21136/CMJ.1976.101401 , MR 0543771 .
^ Шолтес, Любомир (1991), «Передача в графах: граница и удаление вершин», Mathematica Slovaca , 41 (1): 11–16, MR 1094978 .
^ Как описывает Рувре (2002) , эта формула уже была дана Винером (1947) .
^ Бончев Д.; Тринайстич, Н. (1977), «Теория информации, матрица расстояний и молекулярное разветвление», Journal of Chemical Physics , 67 (10): 4517–4533, Бибкод : 1977JChPh..67.4517B , doi : 10.1063/1.434593 , hdl : 10338.dmlcz/104047 .
^ Стил, Леонард И.; Тодос, Джордж (1962), «Нормальные температуры кипения и критические константы насыщенных алифатических углеводородов», AIChE Journal , 8 (4): 527–529, Бибкод : 1962AIChE...8..527S , doi : 10.1002/aic. 690080421 .
^ Рувре, DH; Краффорд, Британская Колумбия (1976), «Зависимость физико-химических свойств от топологических факторов», Южноафриканский научный журнал , 72 : 47 .
^ Гутман Иван; Кёртвелиеси, Т. (1995), «Индексы Винера и молекулярные поверхности», Zeitschrift für Naturforschung , 50a (7): 669–671, Bibcode : 1995ZNatA..50..669G , doi : 10.1515/zna-1995-0707 , S2CID 96881621 .
^ Перейти обратно: ^а ^б ^с Мохар, Боян ; Писански, Томаж (1988), «Как вычислить индекс Винера графа», Журнал математической химии , 2 (3): 267–277, doi : 10.1007/BF01167206 , MR 0966088 , S2CID 15275183 .
^ Флойд, Роберт В. (июнь 1962 г.), «Алгоритм 97: Кратчайший путь», Communications of the ACM , 5 (6): 345, doi : 10.1145/367766.368168 , S2CID 2003382 .
^ Уоршалл, Стивен (январь 1962 г.), «Теорема о булевых матрицах», Журнал ACM , 9 (1): 11–12, doi : 10.1145/321105.321107 , S2CID 33763989 .
^ Джонсон, Дональд Б. (1977), «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях», Журнал ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID 207678246 .
^ Берсон, Малком (1983), «Быстрый алгоритм расчета матрицы расстояний молекулы», Journal of Computational Chemistry , 4 (1): 110–113, doi : 10.1002/jcc.540040115 , S2CID 122640545 .
^ Мюллер, ВР; Шимански, К.; Кноп, СП; Тринайстич, Н. (1987), «Алгоритм построения матрицы молекулярных расстояний», Журнал вычислительной химии , 8 (2): 170–173, doi : 10.1002/jcc.540080209 , S2CID 122278769 .
^ Кэнфилд, ER; Робинсон, RW; Рувре, Д.Х. (1985), «Определение индекса молекулярного разветвления Винера для общего дерева», Journal of Computational Chemistry , 6 (6): 598–609, doi : 10.1002/jcc.540060613 , MR 0824918 , S2CID 121861478 .
^ Кабельо, Серджио; Кнауэр, Кристиан (2009), «Алгоритмы для графов ограниченной ширины дерева посредством поиска в ортогональном диапазоне», Computational Geometry , 42 (9): 815–824, CiteSeerX 10.1.1.127.8127 , doi : 10.1016/j.comgeo.2009.02.001 , МР 2543804 .
^ Да, Ён Нан; Гутман, Иван (1994), «О сумме всех расстояний в составных графах», Discrete Mathematics , 135 (1–3): 359–365, doi : 10.1016/0012-365X(93)E0092-I , MR 1310892 .
^ Чепой, Виктор; Клавжар, Санди (1997), «Индекс Винера и индекс Сегеда бензоидных систем в линейном времени», Журнал химической информации и компьютерных наук , 37 (4): 752–755, doi : 10.1021/ci9700079 . Более ранние алгоритмы для бензооидов, основанные на их частичной кубической структуре, см. Клавжар, Санди; Гутман Иван; Мохар, Боян (1995), «Метки бензоидных систем, отражающие отношения вершин-расстояний» (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi : 10.1021/ci00025a030 .
^ Гутман Иван; Йе, Ён-Нан (1995), «Сумма всех расстояний в двудольных графах», Mathematica Slovaca , 45 (4): 327–334, MR 1387048 .
^ Вагнер, Стефан Г. (2006), «Класс деревьев и его индекс Винера», Acta Applicandae Mathematicae , 91 (2): 119–132, doi : 10.1007/s10440-006-9026-5 , MR 2249544 , S2CID 53644527 .
^ Ван, Хуа; Ю, Гуан (2006), «Все числа, кроме 49, являются индексами Винера деревьев», Acta Applicandae Mathematicae , 92 (1): 15–20, doi : 10.1007/s10440-006-9037-2 , MR 2263469 , S2CID 14425684 .

Внешние ссылки

Вайсштейн, Эрик В. «Индекс Винера» . Математический мир .

[r02-1] Рувре, Деннис Х. (2002), «Богатое наследие полувекового индекса Винера», Рувре, Деннис Х.; Кинг, Роберт Брюс (ред.), Топология в химии: дискретная математика молекул , Horwood Publishing, стр. 16–37, ISBN 9781898563761 .

[w47-2] Перейти обратно: ^а ^б Винер, Х. (1947), «Структурное определение температуры кипения парафина», Журнал Американского химического общества , 1 (69): 17–20, doi : 10.1021/ja01193a005 , PMID 20291038 .

[3] Тодескини, Роберто; Консонни, Вивиана (2000), Справочник молекулярных дескрипторов , Wiley, ISBN 3-527-29913-0 .

[4] Рувре (2002) . См., в частности, Таблицу 2 на с. 32.

[5] Харари, Фрэнк (1959), «Статус и контраст», Социометрия , 22 (1): 23–43, doi : 10.2307/2785610 , JSTOR 2785610 , MR 0134798

[ejs76-6] Перейти обратно: ^а ^б Энтрингер, RC; Джексон, Делавэр; Снайдер, Д.А. (1976), «Расстояние в графиках», Чехословацкий математический журнал , 26 (101): 283–296, doi : 10.21136/CMJ.1976.101401 , MR 0543771 .

[7] Шолтес, Любомир (1991), «Передача в графах: граница и удаление вершин», Mathematica Slovaca , 41 (1): 11–16, MR 1094978 .

[8] Как описывает Рувре (2002) , эта формула уже была дана Винером (1947) .

[9] Бончев Д.; Тринайстич, Н. (1977), «Теория информации, матрица расстояний и молекулярное разветвление», Journal of Chemical Physics , 67 (10): 4517–4533, Бибкод : 1977JChPh..67.4517B , doi : 10.1063/1.434593 , hdl : 10338.dmlcz/104047 .

[10] Стил, Леонард И.; Тодос, Джордж (1962), «Нормальные температуры кипения и критические константы насыщенных алифатических углеводородов», AIChE Journal , 8 (4): 527–529, Бибкод : 1962AIChE...8..527S , doi : 10.1002/aic. 690080421 .

[11] Рувре, DH; Краффорд, Британская Колумбия (1976), «Зависимость физико-химических свойств от топологических факторов», Южноафриканский научный журнал , 72 : 47 .

[12] Гутман Иван; Кёртвелиеси, Т. (1995), «Индексы Винера и молекулярные поверхности», Zeitschrift für Naturforschung , 50a (7): 669–671, Bibcode : 1995ZNatA..50..669G , doi : 10.1515/zna-1995-0707 , S2CID 96881621 .

[mp88-13] Перейти обратно: ^а ^б ^с Мохар, Боян ; Писански, Томаж (1988), «Как вычислить индекс Винера графа», Журнал математической химии , 2 (3): 267–277, doi : 10.1007/BF01167206 , MR 0966088 , S2CID 15275183 .

[14] Флойд, Роберт В. (июнь 1962 г.), «Алгоритм 97: Кратчайший путь», Communications of the ACM , 5 (6): 345, doi : 10.1145/367766.368168 , S2CID 2003382 .

[15] Уоршалл, Стивен (январь 1962 г.), «Теорема о булевых матрицах», Журнал ACM , 9 (1): 11–12, doi : 10.1145/321105.321107 , S2CID 33763989 .

[16] Джонсон, Дональд Б. (1977), «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях», Журнал ACM , 24 (1): 1–13, doi : 10.1145/321992.321993 , S2CID 207678246 .

[17] Берсон, Малком (1983), «Быстрый алгоритм расчета матрицы расстояний молекулы», Journal of Computational Chemistry , 4 (1): 110–113, doi : 10.1002/jcc.540040115 , S2CID 122640545 .

[18] Мюллер, ВР; Шимански, К.; Кноп, СП; Тринайстич, Н. (1987), «Алгоритм построения матрицы молекулярных расстояний», Журнал вычислительной химии , 8 (2): 170–173, doi : 10.1002/jcc.540080209 , S2CID 122278769 .

[19] Кэнфилд, ER; Робинсон, RW; Рувре, Д.Х. (1985), «Определение индекса молекулярного разветвления Винера для общего дерева», Journal of Computational Chemistry , 6 (6): 598–609, doi : 10.1002/jcc.540060613 , MR 0824918 , S2CID 121861478 .

[20] Кабельо, Серджио; Кнауэр, Кристиан (2009), «Алгоритмы для графов ограниченной ширины дерева посредством поиска в ортогональном диапазоне», Computational Geometry , 42 (9): 815–824, CiteSeerX 10.1.1.127.8127 , doi : 10.1016/j.comgeo.2009.02.001 , МР 2543804 .

[21] Да, Ён Нан; Гутман, Иван (1994), «О сумме всех расстояний в составных графах», Discrete Mathematics , 135 (1–3): 359–365, doi : 10.1016/0012-365X(93)E0092-I , MR 1310892 .

[22] Чепой, Виктор; Клавжар, Санди (1997), «Индекс Винера и индекс Сегеда бензоидных систем в линейном времени», Журнал химической информации и компьютерных наук , 37 (4): 752–755, doi : 10.1021/ci9700079 . Более ранние алгоритмы для бензооидов, основанные на их частичной кубической структуре, см. Клавжар, Санди; Гутман Иван; Мохар, Боян (1995), «Метки бензоидных систем, отражающие отношения вершин-расстояний» (PDF) , Journal of Chemical Information and Computer Sciences , 35 (3): 590–593, doi : 10.1021/ci00025a030 .

[23] Гутман Иван; Йе, Ён-Нан (1995), «Сумма всех расстояний в двудольных графах», Mathematica Slovaca , 45 (4): 327–334, MR 1387048 .

[24] Вагнер, Стефан Г. (2006), «Класс деревьев и его индекс Винера», Acta Applicandae Mathematicae , 91 (2): 119–132, doi : 10.1007/s10440-006-9026-5 , MR 2249544 , S2CID 53644527 .

[25] Ван, Хуа; Ю, Гуан (2006), «Все числа, кроме 49, являются индексами Винера деревьев», Acta Applicandae Mathematicae , 92 (1): 15–20, doi : 10.1007/s10440-006-9037-2 , MR 2263469 , S2CID 14425684 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]