индекс Винера
Топологический индекс молекулы

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

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

История

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

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

Пример

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

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

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

3 × 1 + 2 × 2 + 1 × 3 = 10. {\displaystyle 3\times 1+2\times 2+1\times 3=10.}

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

3 × 1 + 3 × 2 = 9. {\displaystyle 3\times 1+3\times 2=9.}

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

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

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

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

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

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

Для взвешенных графов вместо этого можно использовать алгоритм Флойда–Уоршелла [13] [14] [15] или алгоритм Джонсона [ 16] со временем выполнения O( n 3 ) или O( nm  +  n 2  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 (последовательность A122686 в OEIS )

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

Ссылки

  1. ^ Руврэ, Деннис Х. (2002), «Богатое наследие полувека индекса Винера», в Руврэ, Деннис Х.; Кинг, Роберт Брюс (ред.), Топология в химии: дискретная математика молекул, Horwood Publishing, стр.  16–37 , ISBN 9781898563761.
  2. ^ ab Wiener, H. (1947), "Структурное определение точек кипения парафинов", Журнал Американского химического общества , 1 (69): 17– 20, Bibcode : 1947JAChS..69...17W, doi : 10.1021/ja01193a005, PMID  20291038.
  3. ^ Тодескини, Роберто; Консонни, Вивиана (2000), Справочник молекулярных дескрипторов , Wiley, ISBN 3-527-29913-0.
  4. ^ Rouvray (2002). См. в частности Таблицу 2 на стр. 32.
  5. ^ Харари, Фрэнк (1959), «Статус и контраст», Социометрия , 22 (1): 23– 43, doi : 10.2307/2785610, JSTOR  2785610, MR  0134798
  6. ^ ab Энтрингер, 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), «Теория информации, матрица расстояний и молекулярное ветвление», Журнал химической физики , 67 (10): 4517– 4533, Bibcode : 1977JChPh..67.4517B, doi : 10.1063/1.434593, hdl : 10338.dmlcz/104047.
  10. ^ Штиль, Леонард И.; Тодос, Джордж (1962), «Нормальные точки кипения и критические константы насыщенных алифатических углеводородов», Журнал AIChE , 8 (4): 527– 529, Bibcode : 1962AIChE...8..527S, doi : 10.1002/aic.690080421.
  11. ^ Rouvray, DH; Crafford, BC (1976), «Зависимость физико-химических свойств от топологических факторов», South African Journal of Science , 72 : 47.
  12. ^ Гутман, Иван; Кёртвелиеси, Т. (1995), «Индексы Винера и молекулярные поверхности», Zeitschrift für Naturforschung , 50a (7): 669–671 , Бибкод : 1995ZNatA..50..669G, doi : 10.1515/zna-1995-0707 , S2CID  96881621.
  13. ^ abc Мохар, Боян ; Писански, Томаж (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), «Быстрый алгоритм расчета матрицы расстояний молекулы», Журнал вычислительной химии , 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. ^ Кэнфилд, Э. Р.; Робинсон, Р. В.; Руврей, Д. Х. (1985), «Определение индекса молекулярной разветвленности Винера для общего дерева», Журнал вычислительной химии , 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 , MR  2543804 .
  21. ^ Йе, Ён Нан; Гутман, Иван (1994), «О сумме всех расстояний в составных графах», Дискретная математика , 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. Более ранние алгоритмы для бензоидов, основанные на их частичной кубической структуре, см. в Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (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.
Взято с "https://en.wikipedia.org/w/index.php?title=Wiener_index&oldid=1267253640"