Индекс Винера

Перейти к навигации Перейти к поиску

Индекс Винера (англ. Wiener index; число Винера, Wiener number) — топологический индекс неориентированного графа $G=\left\langle A,V\right\rangle$ , определяемый как сумма длин кратчайших путей $d(v_{i},v_{j})$ между вершинами графа:

W(G)=\sum _{\forall i,j}d(v_{i},v_{j})

Может быть вычислен с использованием алгоритма Флойда — Уоршелла за время порядка $O(n^{3})$ .

Предложен Харри Винером (англ. Harry Wiener) в 1947 году^[1], является первым из известных графовых топологических индексов^[2]. Часто используется в математической химии и хемоинформатике при построении количественных корреляций «структура-свойство» для графов органических молекул, рассматриваемых без атомов водорода.

В 1988 году Бояном Мохаром (словен. Bojan Mohar) и Томашем Писански (словен. Tomaž Pisanski) был предложен эффективный алгоритм вычисления индекса Винера для деревьев^[3]^[4]^[5]^[6]^[7]^[8]^[9].

Известны также различные модификации индекса, например, расширенный индекс Винера^[10].

Примечания

↑ Wiener H. Structural determination of paraffin boiling points // J. Am. Chem. Soc. — 1947. — № 69 (1). — С. 17—20.
↑ Todeschini R., Consonni V. Handbook of Molecular Descriptors. — Wiley-VCH^[англ.]^*, 2000. — ISBN 3-52-729913-0.
↑ Mohar B., Pisanski T. How to compute the Wiener index of a graph // J. Math. Chemistry. — 1988. — № 2. — С. 267—277.
↑ Добрынин А. А., Гутман И. Индекс Винера для деревьев и графов гексагональных систем // Дискретный анализ и исследование операций. Серия 2. — 1998. — Т. 5, № 2. — С. 34—60. — ISSN 1560-7542.
↑ Dobrynin A. A., Entringer R., Gutman I. Wiener index for trees: theory and applications // Acta Appl. Math. — 2001. — Т. 66, № 3. — С. 211—249. — ISSN 0167-8019. Архивировано 27 июля 2021 года.
↑ Dobrynin A. A., Gutman I., Klavžar S., Žigert P. Wiener index of hexagonal systems // Acta Appl. Math. — 2002. — Т. 72, № 3. — С. 247—294. — ISSN 0167-8019. Архивировано 28 июня 2021 года.
↑ Dobrynin A. A., Mel'nikov L. S. Wiener index of line graphs // Distance in molecular graphs - Theory, Editors I. Gutman, B. Furtula, Mathematical chemistry monographs 12. — 2012. — С. 85—121. Архивировано 31 марта 2022 года.
↑ Knor M., Škrekovski R. Wiener index of line graphs // Quantitative graph theory: mathematical foundations and applications, Editors M. Dehmer, F. Emmert-Streib, Discrete Mathematics and Its Applications, Chapman and Hall/CRC. — 2014. — С. 279—301. Архивировано 18 октября 2019 года.
↑ Knor M., Škrekovski R., Tepeh A. Mathematical aspects of Wiener index // Ars Mathematica Contemporanea. — 2016. — Т. 11, № 2. — С. 327–352. — ISSN 1855-3966. Архивировано 1 июля 2021 года.
↑ Tratch S. S., Stankevitch M. I., Zefirov N. S. // J. Comp. Chem. — 1990. — № 11. — С. 899.

См. также

Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети.

Похожие исследовательские статьи

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

(Топологический) индекс Хосойи, известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.

<span class="mw-page-title-main">Регулярный граф</span> граф, степени всех вершин которого равны

Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается $\text{[math]}$ . Для нерегулярных графов $\text{[math]}$ не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

Теорема Фа́ри — теоретико-графовое утверждение о возможности выпрямить рёбра любого планарного графа. Иными словами, разрешение рисовать рёбра не в виде отрезков, а в виде кривых, не расширяет класс планарных графов.

Двойственный граф $\text{[math]}$ к планарному графу $\text{[math]}$ — это граф, в котором вершины соответствуют граням графа $\text{[math]}$ ; две вершины соединены ребром если и только если соответствующие им грани графа $\text{[math]}$ имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.

<span class="mw-page-title-main">Тороидальный граф</span> граф, который можно уложить на тор

Тороида́льный граф — граф, который можно нарисовать на торе так, что его рёбра пересекаются только по общим вершинам.

<span class="mw-page-title-main">Алгебраическая связность</span>

Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.

В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.

В теории графов части́чный куб — это подграф гиперкуба, сохраняющий расстояния — расстояние между любыми двумя вершинами подграфа то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в гиперкуб.

Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.

Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.

Проблема Заранке́вича — задача теории графов, связанная с нахождением минимального числа пересечений при изображении на плоскости полного двудольного графа.

Резистивное расстояние между двумя вершинами простого связного графа G равно сопротивлению между двумя эквивалентными точками электрической цепи, построенной путём замены каждого ребра графа на сопротивление в 1 ом. Резистивные расстояния являются метрикой на графах.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.