Индекс Альбертсона (известный также как нерегулярность или нерегулярность Альбертсона) — это инвариант графа, измеряющий нерегулярность графа путём суммирования разбалансированности всёх его рёбер. Показатель ввёл Михаэль Альбертсон в 1997 году как параметр для определения, насколько граф «нерегулярен».
Определение
Для простого неориентированного графа разбалансировка ребра определяется как:
где и обозначает степени вершин и .
Индекс Альбертсона графа , обозначаемый как (в литературе иногда — или ), — это сумма разбалансировок всех рёбер:
Граф является регулярным тогда и только тогда, когда его индекс Альбертсона равен нулю.
Свойства и границы
Индекс Альбертсона всегда является чётным числом. Для графа с вершины, индекс ограничен .
Максимальная нерегулярность
Максимальный индекс Альбертсона по всем графам с вершинами меньше чем и эта граница точна. Экстремальные графы, приближающиеся к этой границе, имеют вид , соединение полного графа и независимого множества , где равно примерно .
Граф называется критичным, если добавление или удаление любого отдельного ребра не увеличивает индекс Альбертсона. Альбертсон доказал что граф критичен тогда и только тогда, когда он имеет вид для некоторого , что используется для вывода общей верхней границы.
Для конкретных классов графов существуют более точные границы:
Если граф является двудольным, то . Нерегулярность полного двудольного графа равна .
Если в графе нет треугольников, то .
Экстремальные деревья
Для всех деревьев с вершинами, индекс Альбертсона ограничен величиной:
Нижняя граница 2 достигается исключительно на путях , в то время как верхняя граница достигается исключительно на звёздах .
Минимальная нерегулярность
Изучалась также минимальная нерегулярность для определённых классов графов. Для связного графа с листами, нижняя граница равна .
Связанные концепции и обобщения
Общая нерегулярность
Связанный показатель общая нерегулярность ввели Абдо, Брандт и Димитров. Показатель определяется как сумма абсолютных величин разностей степеней по всем парам вершин, а не только смежных вершин:
В отличие от индекса Альбертсона общая нерегулярность зависит только от последовательности степеней графа, не от его рёберной структуры.
Обобщённый индекс Альбертсона
Обобщение ввели Лин, Чжоу, Ванг и Мяо в 2022 году. Общий индекс Альбертсона (или -индекс Альбертсона) определяется как:
где — положительное вещественное число. Показатель сводится к классическому индексу Альбертсона при . Для , квадрат показателя известен как -индекс и он связан с индексом Загреба и забытым топологическим индексом. Экстремальными деревьями для -индекса Альбертсона остаются пути (минимум) и звезды (максимум).
Приложения и связи
Индекс Альбертсона имеет приложения в математической химии для предсказания физикохимических свойств молекул в моделях QSAR/QSPR. В науке о сетях индекс обеспечивает численную меру неоднородности сети.
Эта концепция также связана с другими областями теории графов, такими как , в котором любое ребро имеет дисбаланс ровно 1, и гипотеза о разбалансировке, которая исследует, могут ли последовательности дисбалансов ребер образовывать допустимую последовательность степеней некоторого графа.
Смотрите также Инвариант графа Регулярный граф Топологический индекс
Примечания
Категория:Инварианты графов Категория:Теория графов Категория:Алгебраическая теория графов