Наибольшее независимое множество

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф куба имеет шесть различных наибольших независимых множества, показанных красным цветом.

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

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

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

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

Связь с другими множествами вершин[править | править вики-текст]

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

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

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

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

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

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

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

Оценки числа множеств[править | править вики-текст]

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

\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] Другие более сложные задачи можно свести к поиску клики или независимого множества специального вида. Это даёт мотивацию для поиска алгоритмов, эффективно перечисляющих все наибольшие независимые множества (или, что эквивалентно, наибольшие клики).

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

Замечания[править | править вики-текст]

  1. Эрдёш (Erdős 1966) показал, что число различных размеров наибольших независимых множеств в графе с n вершинами может достигать n - log(n) - O(log(log(n))) и никогда не больше n - log(n) .
  2. Weigt, Hartmann, 2001
  3. Information System on Graph Class Inclusions: графы с несводимыми наибольшими кликами и с наследственно несводимыми наибольшими кликами.
  4. (Byskov 2003). Для более ранних работ смотрите (Croitoru 1979) и (Eppstein 2003).
  5. (Chiba, Nishizeki 1985). Условие разреженности эквивалентно условию, что семейство графов имеет ограниченную древесность[en].
  6. (Bisdorff, Marichal 2007); (Euler 2005); (Füredi 1987).
  7. (Eppstein 2003); (Byskov 2003).
  8. (Eppstein 2003). Для границ широко используемого алгоритма Брона — Кербоша смотрите (Tomita, Tanaka, Takahashi 2006).
  9. (Bomze, Budinich, Pardalos, Pelillo 1999); (Eppstein 2005); (Jennings, Motycková 1992); (Johnson, Yannakakis, Papadimitriou 1988); (Lawler, Lenstra, Rinnooy Kan 1980); (Liang, Dhall, Lakshmivarahan 1991); (Makino, Uno 2004); (Mishra, Pitt 1997); (Stix 2004); (Tsukiyama, Ide, Ariyoshi, Shirakawa 1977); (Yu, Chen 1993).
  10. (Makino, Uno 2004); (Eppstein 2005).

Ссылки[править | править вики-текст]

  • R. Bisdorff, J.-L. Marichal Counting non-isomorphic maximal independent sets of the n-cycle graph. — 2007. — arΧiv:math.CO/0701647.
  • I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo Handbook of Combinatorial Optimization. — Kluwer Academic Publishers, 1999. — Т. 4. — С. 1–74..
  • J. M. Byskov Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2003. — С. 456–457..
  • N. Chiba, T. Nishizeki Arboricity and subgraph listing algorithms // SIAM J. on Computing. — 1985. — В. 1. — Т. 14. — С. 210–223. — DOI:10.1137/0214017.
  • C. Croitoru Proc. Third Coll. Operations Research. — Babeş-Bolyai University, Cluj-Napoca, Romania, 1979. — С. 55–60..
  • D. Eppstein Small maximal independent sets and faster exact graph coloring // Journal of Graph Algorithms and Applications. — 2003. — В. 2. — Т. 7. — С. 131–140. — arΧiv:cs.DS/cs.DS/0011009.
  • D. Eppstein Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — 2005. — С. 451–459. — arΧiv:cs.DS/0407036.
  • P. Erdős On cliques in graphs // Israel J. Math.. — 1966. — В. 4. — Т. 4. — С. 233–234. — DOI:10.1007/BF02771637.
  • R. Euler The Fibonacci number of a grid graph and a new class of integer sequences // Journal of Integer Sequences. — 2005. — В. 2. — Т. 8. — С. 05.2.6..
  • Z. Füredi The number of maximal independent sets in connected graphs // Journal of Graph Theory. — 1987. — В. 4. — Т. 11. — С. 463–470. — DOI:10.1002/jgt.3190110403.
  • E. Jennings, L. Motycková Proc. First Latin American Symposium on Theoretical Informatics. — 1992. — Т. 583. — С. 281–293.
  • D.S. Johnson, M. Yannakakis, C. H. Papadimitriou On generating all maximal independent sets // Information Processing Letters. — 1988. — В. 3. — Т. 27. — С. 119–123. — DOI:10.1016/0020-0190(88)90065-8.
  • E. L. Lawler A note on the complexity of the chromatic number problem // Information Processing Letters. — 1976. — В. 3. — Т. 5. — С. 66–67. — DOI:10.1016/0020-0190(76)90065-X.
  • E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan Generating all maximal independent sets: NP-hardness and polynomial time algorithms // SIAM Journal on Computing. — 1980. — В. 3. — Т. 9. — С. 558–565. — DOI:10.1137/0209042.
  • J. Y.-T. Leung Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs // Journal of Algorithms. — 1984. — Т. 5. — С. 22–35. — DOI:10.1016/0196-6774(84)90037-3.
  • Y. D. Liang, S. K. Dhall, S. Lakshmivarahan Proc. Symp. Applied Computing. — 1991. — С. 465–470.
  • K. Makino, T. Uno Proc. Ninth Scandinavian Workshop on Algorithm Theory. — Springer-Verlag, 2004. — Т. 3111. — С. 260–272. — (Lecture Notes in Compute Science)..
  • N. Mishra, L. Pitt Proc. Tenth Conf. Computational Learning Theory. — 1997. — С. 211–217. — ISBN 0-89791-891-6. — DOI:10.1145/267460.267500.
  • J. W. Moon, L. Moser On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3. — С. 23–28. — DOI:10.1007/BF02760024.
  • V. Stix Finding all maximal cliques in dynamic graphs // Computational Optimization Appl.. — 2004. — В. 2. — Т. 27. — С. 173–186. — DOI:10.1023/B:COAP.0000008651.28952.b6
  • E. Tomita, A. Tanaka, H. Takahashi The worst-case time complexity for generating all maximal cliques and computational experiments. — 2006. — В. 1. — Т. 363. — С. 28–42. — DOI:10.1016/j.tcs.2006.06.015.
  • S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa A new algorithm for generating all the maximal independent sets // SIAM J. on Computing. — 1977. — В. 3. — Т. 6. — С. 505–517. — DOI:10.1137/0206036.
  • Martin Weigt, Alexander K. Hartmann Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture // Phys. Rev. E. — 2001. — В. 5. — Т. 63. — С. 056127. — DOI:10.1103/PhysRevE.63.056127 — arΧiv:cond-mat/0011446.
  • C.-W. Yu, G.-H. Chen Generate all maximal independent sets in permutation graphs // Internat. J. Comput. Math.. — 1993. — Т. 47. — С. 1–8. — DOI:10.1080/00207169308804157.