Индекс Винера - Wiener index

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

История

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

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

Пример

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

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

  • н-бутан

  • Изобутан

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

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

Эти числа являются экземплярами формул для частных случаев индекса Винера: это для любого -вершинный граф путей, такой как граф п-бутан,[8] и для любого -вертекс звезда например график изобутана.[9]

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

Отношение к химическим свойствам

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

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

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

Для взвешенных графиков вместо этого можно использовать Алгоритм Флойда-Уоршолла[13][14][15] или же Алгоритм Джонсона,[16] с временем работы O (п3) или O (нм + п2 бревноп) соответственно. Альтернативные, но менее эффективные алгоритмы, основанные на повторяющихся матричное умножение также были разработаны в литературе по химической информатике.[17][18]

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

Когда базовый график является дерево (как это верно, например, для алканов, первоначально изученных Винером), индекс Винера может быть рассчитан более эффективно. Если граф разделен на два поддерева путем удаления единственного ребра е, то его индекс Винера представляет собой сумму индексов Винера двух поддеревьев вместе с третьим членом, представляющим пути, которые проходят через е. Этот третий член может быть вычислен за линейное время путем вычисления суммы расстояний всех вершин от е внутри каждого поддерева и умножение двух сумм.[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. ^ Rouvray, Деннис Х. (2002), «Богатое наследие полувекового индекса Винера», в Rouvray, Dennis H .; Кинг, Роберт Брюс (ред.), Топология в химии: дискретная математика молекул, Horwood Publishing, стр. 16–37..
  2. ^ а б Винер, Х. (1947), "Структурное определение точек кипения парафина", Журнал Американского химического общества, 1 (69): 17–20, Дои:10.1021 / ja01193a005.
  3. ^ Тодескини, Роберто; Консонни, Вивиана (2000), Справочник молекулярных дескрипторов, Wiley, ISBN  3-527-29913-0.
  4. ^ Рувре (2002). См., В частности, Таблицу 2 на стр. 32.
  5. ^ Харари, Фрэнк (1959), «Статус и контраст», Социометрия, 22: 23–43, Дои:10.2307/2785610, МИСТЕР  0134798
  6. ^ а б Entringer, R.C .; Джексон, Д. Э .; Снайдер, Д. А. (1976), «Расстояние в графах», Чехословацкий математический журнал, 26 (101): 283–296, МИСТЕР  0543771.
  7. ^ Шолтес, Любомир (1991), «Передача в графах: ограничение и удаление вершин», Mathematica Slovaca, 41 (1): 11–16, МИСТЕР  1094978.
  8. ^ В качестве Рувре (2002) описывает, эта формула уже была дана Винер (1947).
  9. ^ Бончев, Д .; Тринайстич, Н. (1977), "Теория информации, матрица расстояний и молекулярное ветвление", Журнал химической физики, 67 (10): 4517–4533, Bibcode:1977ЖЧФ..67.4517Б, Дои:10.1063/1.434593, HDL:10338.dmlcz / 104047.
  10. ^ Stiel, Леонард I .; Тодос, Джордж (1962), "Нормальные точки кипения и критические константы насыщенных алифатических углеводородов", Журнал Айше, 8 (4): 527–529, Дои:10.1002 / aic.690080421.
  11. ^ Rouvray, D. H .; Краффорд, Б. С. (1976), "Зависимость физико-химических свойств от топологических факторов", Южноафриканский научный журнал, 72: 47.
  12. ^ Гутман, Иван; Körtvélyesi, T. (1995), "Индексы Винера и молекулярные поверхности", Zeitschrift für Naturforschung, 50а: 669–671.
  13. ^ а б c Мохар, Боян; Писанский, Томаж (1988), «Как вычислить индекс Винера графа», Журнал математической химии, 2 (3): 267–277, Дои:10.1007 / BF01167206, МИСТЕР  0966088.
  14. ^ Флойд, Роберт В. (Июнь 1962 г.), «Алгоритм 97: кратчайший путь», Коммуникации ACM, 5 (6): 345, Дои:10.1145/367766.368168.
  15. ^ Уоршалл, Стивен (январь 1962 г.), "Теорема о булевых матрицах", Журнал ACM, 9 (1): 11–12, Дои:10.1145/321105.321107.
  16. ^ Джонсон, Дональд Б. (1977), "Эффективные алгоритмы поиска кратчайших путей в разреженных сетях", Журнал ACM, 24 (1): 1–13, Дои:10.1145/321992.321993.
  17. ^ Берсон, Малком (1983), "Быстрый алгоритм для вычисления матрицы расстояний молекулы", Журнал вычислительной химии, 4 (1): 110–113, Дои:10.1002 / jcc.540040115.
  18. ^ Müller, W. R .; Szymanski, K .; Knop, J. V .; Тринайстич, Н. (1987), "Алгоритм построения матрицы молекулярных расстояний", Журнал вычислительной химии, 8 (2): 170–173, Дои:10.1002 / jcc.540080209.
  19. ^ Canfield, E. R .; Робинсон, Р. У .; Rouvray, Д. Х. (1985), "Определение индекса ветвления молекул Винера для общего дерева", Журнал вычислительной химии, 6 (6): 598–609, Дои:10.1002 / jcc.540060613, МИСТЕР  0824918.
  20. ^ Кабельо, Серджио; Knauer, Christian (2009), "Алгоритмы для графов ограниченной ширины дерева с помощью поиска по ортогональному диапазону", Вычислительная геометрия, 42 (9): 815–824, Дои:10.1016 / j.comgeo.2009.02.001, МИСТЕР  2543804.
  21. ^ Йе, Ён Нан; Гутман, Иван (1994), "О сумме всех расстояний в составных графах", Дискретная математика, 135 (1–3): 359–365, Дои:10.1016 / 0012-365X (93) E0092-I, МИСТЕР  1310892.
  22. ^ Чепой, Виктор; Клавжар, Санди (1997), "Индекс Винера и индекс Сегеда бензоидных систем в линейном времени", Журнал химической информации и компьютерных наук, 37 (4): 752–755, Дои:10.1021 / ci9700079. Для более ранних алгоритмов для бензоидов, основанных на их частичный куб структура, см. Клавжар, Санди; Гутман, Иван; Мохар, Боян (1995), «Маркировка бензоидных систем, отражающая отношения вершинного расстояния» (PDF), Журнал химической информации и компьютерных наук, 35 (3): 590–593, Дои:10.1021 / ci00025a030.
  23. ^ Гутман, Иван; Yeh, Yeong-Nan (1995), "Сумма всех расстояний в двудольных графах", Mathematica Slovaca, 45 (4): 327–334, МИСТЕР  1387048.
  24. ^ Вагнер, Стефан Г. (2006), "Класс деревьев и его индекс Винера", Acta Applicandae Mathematicae, 91 (2): 119–132, Дои:10.1007 / s10440-006-9026-5, МИСТЕР  2249544.
  25. ^ Ван, Хуа; Ю, Гуан (2006), «Все числа, кроме 49, являются индексами Винера деревьев», Acta Applicandae Mathematicae, 92 (1): 15–20, Дои:10.1007 / s10440-006-9037-2, МИСТЕР  2263469.

внешняя ссылка