Мини- и макси-код матрицы смежности, получаемые путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным; макси-коду — соответственно максимальным.
Минимальное число вершин, которое необходимо удалить для получения несвязного графа.
Минимальное число ребер, которое необходимо удалить для получения несвязного графа.
Минимальное число вершин, необходимое для покрытия ребер.
Минимальное число ребер, необходимое для покрытия вершин.
Неплотность графа — число вершин максимального по включению безреберного подграфа (наибольшее количество попарно несмежных вершин). Несложно заметить, что и .
Обхват графа — число ребер в составе минимального цикла.
Плотность графа — число вершин максимальной по включению клики.
Упорядоченный по возрастанию или убыванию вектор степеней вершин — при использовании переборных алгоритмов определения изоморфизма графов в качестве предположительно-изоморфных пар вершин выбираются вершины с совпадающими степенями, что способствует снижению трудоемкость перебора. Использование данного инварианта для k-однородных графов не приводит к снижению вычислительной сложность перебора, так как степени всех вершин подобного графа совпадают: .
Упорядоченный по возрастанию или убыванию вектор собственных чиселматрицы смежности графа (спектр графа). Сама по себе матрица смежности не является инвариантом, так как при смене нумерации вершин она претерпевает перестановку строк и столбцов.
В качестве инварианта можно рассматривать не одно из приведенных выше чисел, а их кортеж (супериндекс) вида , которому, в свою очередь, может быть сопоставлен многочлен вида
суммирование ведется до последнего отличного от нуля значения . Подобным образом можно ввести ещё несколько инвариантов графа:
, где — число вершин степени i;
, где — число безреберных i-вершинных подграфов;
, где — число полных i-вершинных подграфов (i-клик);
, где — число различных стягиваний связного графа на i-клику;
, где — число компонент связности из i вершин;
, где — число i-раскрасок графа (правильных раскрасок с использованием ровно i цветов).
Системы инвариантов графа, зависящие от двух и более параметров, можно записать в виде многочленов от нескольких формальных переменных Например:
, где — число подграфов графа , которые имеют вершин и ребер;
, где — количество i-вершинных подграфов, для которых число иголок (ребер, соединяющих вершины подграфа с остальными вершинами графа) равно ;
, где — количество i-вершинных подграфов, имеющих ребер и иголок (обобщение инвариантов и );
Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений и является полным инвариантом для графа с фиксированным числом вершин .
Инварианты различаются по трудоемкости вычисления. Инварианты , , и вычисляются тривиально, в то время как вычисление инвариантов , , , , , и зависящих от них может быть достаточно вычислительно сложным. Существуют вероятностные алгоритмы определения значений приведенных «трудновычисляемых» инвариантов, однако применение подобных алгоритмов допускается не всегда.
В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.
Многие инварианты (топологические индексы) используются в компьютерной химии для решения широкого круга общих и специальных задач[2]. К этим задачам относятся: поиск веществ с заранее заданными свойствами (поиск зависимостей типа «структура-свойство», «структура-фармакологическая активность»), первичная фильтрация структурной информации для бесповторной генерации молекулярных графов заданного типа и ряд других. Часто при этом наряду с топологическими индексами (зависящими только от структуры молекулы) используется информация и о химическом составе соединения[3].
Некоторые внешние ссылки в этой статье ведут на сайты, занесённые в спам-лист Эти сайты могут нарушать авторские права, быть признаны неавторитетными источниками или по другим причинам быть запрещены в Википедии. Редакторам следует заменить такие ссылки ссылками на соответствующие правилам сайты или библиографическими ссылками на печатные источники либо удалить их (возможно, вместе с подтверждаемым ими содержимым).
.mw-parser-output .ts-Скрытый_блок{margin:0;overflow:hidden;border-collapse:collapse;box-sizing:border-box;font-size:95%}.mw-parser-output .ts-Скрытый_блок-title{text-align:center;font-weight:bold;line-height:1.6em;min-height:1.2em}.mw-parser-output .ts-Скрытый_блок .mw-collapsible-content{overflow-x:auto;overflow-y:hidden;clear:both}.mw-parser-output .ts-Скрытый_блок::before,.mw-parser-output .ts-Скрытый_блок .mw-collapsible-toggle{padding-top:.1em;width:6em;font-weight:normal;font-size:calc(90%/0.95)}.mw-parser-output .ts-Скрытый_блок-rightHideLink .mw-collapsible-toggle{float:right;text-align:right}.mw-parser-output .ts-Скрытый_блок-leftHideLink .mw-collapsible-toggle{float:left;text-align:left}.mw-parser-output .ts-Скрытый_блок-gray{padding:2px;border:1px solid var(--border-color-base,#a2a9b1)}.mw-parser-output .ts-Скрытый_блок-transparent{border:none}.mw-parser-output .ts-Скрытый_блок-gray .ts-Скрытый_блок-title{background:var(--background-color-neutral,#eaecf0);padding:.1em 6em;padding-right:0}.mw-parser-output .ts-Скрытый_блок-transparent .ts-Скрытый_блок-title{background:transparent;padding:.1em 5.5em;padding-right:0}.mw-parser-output .ts-Скрытый_блок-gray .mw-collapsible-content{padding:.25em 1em}.mw-parser-output .ts-Скрытый_блок-transparent .mw-collapsible-content{padding:.25em 0}.mw-parser-output .ts-Скрытый_блок-gray.ts-Скрытый_блок-rightHideLink .mw-collapsible-toggle{padding-right:1em}.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-rightHideLink .mw-collapsible-toggle{padding-right:0}.mw-parser-output .ts-Скрытый_блок-gray.ts-Скрытый_блок-leftHideLink .mw-collapsible-toggle{padding-left:1em}.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-leftHideLink .mw-collapsible-toggle{padding-left:0}.mw-parser-output .ts-Скрытый_блок-gray.ts-Скрытый_блок-rightHideLink .ts-Скрытый_блок-title-leftTitle{padding-left:1em}.mw-parser-output .ts-Скрытый_блок-gray.ts-Скрытый_блок-leftHideLink .ts-Скрытый_блок-title-leftTitle{padding-left:6.5em}.mw-parser-output .ts-Скрытый_блок-gray.ts-Скрытый_блок-leftHideLink .ts-Скрытый_блок-title-rightTitle{padding-right:1em}.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-rightHideLink .ts-Скрытый_блок-title-rightTitle,.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-rightHideLink .ts-Скрытый_блок-title-leftTitle{padding-left:0}.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-leftHideLink .ts-Скрытый_блок-title-rightTitle,.mw-parser-output .ts-Скрытый_блок-transparent.ts-Скрытый_блок-leftHideLink .ts-Скрытый_блок-title-leftTitle{padding-right:0}.mw-parser-output .ts-Скрытый_блок+.ts-Скрытый_блок,.mw-parser-output .ts-Скрытый_блок+link+.ts-Скрытый_блок{border-top-style:hidden}Список проблемных ссылок
www.bookshunt.ru
This browser is not supported by Wikiwand :( Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience. Please download and use one of the following browsers:
Your input will affect cover photo selection, along with input from other users.
X
Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?
Oh no, there's been an error
Please help us solve this error by emailing us at support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!