WikiSort.ru - Не сортированное

В теории графов наибольшим независимым множеством, наибольшим устойчивым множеством, или наибольшим стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Наибольшее независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть наибольшим независимым, поэтому наибольшие независимые множества также называют независимыми доминирующими множествами. Граф может иметь много наибольших независимых множеств в широком диапазоне размеров.^[1]

Самое большое по размеру наибольшее независимое множество называется максимальным независимым множеством.

Например, в графе P₃, пути с тремя вершинами a, b и c и двумя рёбрами ab и bc, множества {b} и {a,c} оба являются наибольшими независимыми. Множество {a} независимо, но не наибольшее, поскольку является подмножеством {a,c}. В этом же графе максимальными кликами являются множества {a,b} и {b,c}.

Словосочетание «наибольшее независимое множество» употребляется также для описания наибольших подмножеств независимых элементов в математических структурах, отличных от графов, в частности, в векторных пространствах и матроидах.

Связь с другими множествами вершин

Если S — наибольшее независимое множество в некотором графе, то оно является наибольшей кликой в дополнении графа. Наибольшая клика — это множество вершин, которые порождают полный подграф, и оно не содержится в большем полном подграфе. Таким образом, это множество вершин S, таких, что любая пара вершин в S соединена ребром, а для любой вершины не из S отсутствует ребро, соединяющее её с хотя бы одной вершиной в S. Граф может иметь несколько наибольших клик различного размера. Поиск наибольшей клики максимального размера — это задача о максимальной клике.

Некоторые авторы в определении требуют, чтобы клика была наибольшей, и употребляют термин клика вместо наибольшая клика.

Дополнение наибольшего независимого множества, то есть вершины, не принадлежащие независимому множеству, образуют минимальное покрытие вершин. То есть дополнение — это вершинное покрытие, множество вершин, содержащих по меньшей мере одну конечную вершину любого ребра, и минимальное в том смысле, что ни одну из вершин нельзя удалить, не нарушив покрытия. Минимальное покрытие вершин изучается в статистической механике в модели газовой решётки на жёстких сферах, математической абстракции перехода из жидкости в твёрдое состояние.^[2]

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

Использование в характеристиках семейств графов

Некоторые семейства графов можно описать в терминах их наибольших клик или наибольших независимых множеств. Примеры включают графы с несводимыми наибольшими кликами и графы с наследственно несводимыми наибольшими кликами. Говорят, что граф имеет несводимые наибольшие клики, если любая наибольшая клика содержит ребро, которое не принадлежит никакой другой наибольшей клике, и наследственно несводимые наибольшие клики, если это свойство верно для любого подграфа.^[3] Графы с наследственно несводимыми наибольшими кликами включают графы без треугольников, двудольные графы и интервальные графы.

Кографы можно описать как графы, в которых любая наибольшая клика пересекается с любым наибольшим независимым множеством, и в которых это свойство верно для всех порождённых подграфов.

Оценки числа множеств

Мун и Мозер (Moon, Moser 1965) показали, что любой граф с n вершинами имеет не более 3^n/3 наибольших клик. Также граф с n вершинами имеет не более 3^n/3 наибольших независимых множеств. Граф, имеющий ровно 3^n/3 наибольших независимых множеств, легко построить, просто взяв несвязный набор n/3 треугольных графов. Любое наибольшее независимое множество в этом графе образуется выбором одной вершины из каждого треугольника. Дополнительный граф с 3^n/3 наибольшими кликами — это графы Турана специального вида. Ввиду связи этого графа с границей Муна и Мозера эти графы иногда называют графами Муна-Мозера. Более сильные границы возможны, если ограничен размер наибольших независимых множеств — число наибольших независимых множеств размера k в любом графе с n вершинами не превосходит

${\displaystyle \lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}$

Графы, достигающие этой границы — это снова графы Турана.^[4]

Некоторые семейства графов могут, однако, иметь существенно более сильные границы на число наибольших независимых множеств или наибольших клик. Например, если графы в семействе имеют O(n) рёбер, и семейство замкнуто относительно подграфов, то все наибольшие клики имеют постоянный размер и число наибольших клик почти линейно.^[5]

Ясно, что любой граф с несводимыми наибольшими кликами имеет наибольших клик не больше, чем рёбер. Более сильная граница возможна для интервальных графов и хордальных графов — в этих графах не может быть более n наибольших клик.

Число наибольших независимых множеств в циклах с n вершинами задаётся числами Перрина, а число наибольших независимых множеств в пути с n вершинами задаётся последовательностью Падована.^[6] Таким образом, обе эти последовательности пропорциональны степени 1.324718 (то есть пластического числа).

Алгоритмы перечисления множеств

Алгоритм для перечисления всех наибольших независимых множеств или наибольших клик в графе может быть использован как подпрограмма для решения многих NP-полных задач теории графов. Самые очевидные задачи — это задача о максимальном независимом множестве, задача о максимальной клике и минимальном независимом доминирующем множестве. Все они должны быть наибольшими независимыми множествами или наибольшими кликами и могут быть найдены с помощью алгоритма, который перечисляет все такие множества и выбирает множество максимального или минимального размера. Таким же образом минимальное вершинное покрытие можно найти как дополнение одного из наибольших независимых множеств. Лоулер (Lawler 1976) заметил, что перечисление наибольших независимых множеств можно использовать также для поиска раскраски графа в 3 цвета — граф можно раскрасить в три цвета тогда и только тогда, когда дополнение одного из наибольших независимых множеств является двудольным. Он использовал этот подход не только для раскрашивания в 3 цвета, но и как часть более общего алгоритма раскраски графов, и похожий подход для раскраски графа был использован другими авторами.^[7] Другие более сложные задачи можно свести к поиску клики или независимого множества специального вида. Это даёт мотивацию для поиска алгоритмов, эффективно перечисляющих все наибольшие независимые множества (или, что эквивалентно, наибольшие клики).

Возможно напрямую превратить доказательство Муна и Мозера границы 3^n/3 числа наибольших независимых множеств в алгоритм, который перечисляет все такие множества за время O(3^n/3).^[8] Для графов, имеющих максимально возможное число наибольших независимых множеств, этот алгоритм даёт постоянное время на одно найденное множество. Однако алгоритм с этой временной границей может быть крайне неэффективен для графов с более ограниченными количествами независимых множеств. По этой причине многие исследоватили ищут алгоритмы перечисления всех наибольших независимых множеств с полиномиальным временем на одно найденное множество.^[9] Время нахождения одного наибольшего независимого множества пропорционально времени умножения матриц в плотных графах или быстрее в различных классах разреженных графов.^[10]

Замечания

Ссылки

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