Как найти независимое множество в графе

Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.

Определения[править | править код]

Множество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Другими словами, индуцированный этим множеством подграф состоит из изолированных вершин. Иногда также говорят, что каждое ребро графа инцидентно не более чем одной вершине из независимого множества. Задача распознавания (проблема разрешимости) выглядит так: существует ли в заданном графе G независимое множество размера k? Соответствующая ей оптимизационная задача, она же задача о независимом множестве, формулируется следующим образом: в заданном графе G требуется найти независимое множество максимального размера. Этот размер называют числом независимости, числом внутренней плотности или неплотностью и обозначают как ^[1][2].

Иногда эту задачу называют поиском наибольшего независимого множества. Не стоит путать это понятие с максимальным независимым множеством, или максимальным по включению независимым множеством, которое определяется как такое независимое множество вершин, что при добавлении к нему ещё одной (любой) вершины исходного графа оно перестаёт быть независимым (вообще говоря, таких множеств может быть несколько и разных размеров). Максимальное по включению независимое множество отнюдь не всегда является наибольшим. В то же время каждое наибольшее независимое множество по определению является также и максимальным по включению. Для нахождения (какого-то) максимального по включению независимого множества можно воспользоваться жадным алгоритмом, работающим за полиномиальное время, тогда как задача о наибольшем независимом множестве принадлежит к классу NP-полных задач.

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

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

Наименьшим независимым подмножеством в графе является любая вершина этого графа.

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

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

Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием. Сумма числа независимости и числа вершинного покрытия равна числу вершин графа (первое тождество Галлаи).

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

В двудольных графах, не имеющих изолированных вершин, число вершин в наибольшем независимом множестве равно числу рёбер в наименьшем рёберном покрытии (следствие из теоремы Кёнига).

Поиск независимых множеств[править | править код]

В информатике изучается несколько вычислительных задач^[en], связанных с независимыми множествами:

• В задаче о наибольшем независимом множестве входом служит неориентированный граф, а выходом — наибольшее независимое множество в этом графе. Если существует несколько таких множеств, достаточно найти одно.
• В задаче о независимом множестве максимального веса входом служит неориентированный граф с весами, заданными для вершин, а выходом — независимое множество с максимальным общим весом. Задача о максимальном по включению независимом множестве является частным случаем этой задачи с весами, равными единице.
• В задаче перечисления максимальных по включению независимых множеств входом служит неориентированный граф, а выходом — список всех максимальных по включению независимых множеств. Задачу о наибольшем независимом множестве можно решать как подзадачу данной задачи, поскольку наибольшее независимое множество является максимальным по включению и должно попасть в этот список.
• В задаче о наличии независимого множества заданного размера входом служит неориентированный граф и число k, а выходом — Да/Нет: Да, если граф содержит независимое множество размера k, и Нет в противном случае.

Первые три задачи важны в практических приложениях, последняя же важна для теории NP-полноты для задач, связанных с независимыми множествами.

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

• Задача о наличии является NP-полной, а это означает, что существование (ровно как и не существование) эффективного алгоритма её решения не доказано. Существует эффективные (аппроксимирующие^[5]) эвристические алгоритмы поиска максимального по весу независимого множества вершин в графе, примером которых может служить алгоритм Русова В.С. и Захаровой Д.А. имеющий сложность O(n³).
• Задача о наибольшем независимом множестве NP-трудна и её, кроме того, трудно аппроксимировать.

Поиск наибольшего независимого множества[править | править код]

Эту задачу иногда называют «упаковкой вершин».

Задача нахождения наибольшего независимого множества и задача о наибольшей клике полиномиально эквивалентны — можно найти наибольшее независимое множество путём поиска максимальной клики в дополнении графа, так что многие авторы особенно не заботятся о разделении этих двух задач. Обе задачи NP-полны, так что вряд ли их можно решить за полиномиальное время. Тем не менее, задача о наибольшем независимом множестве может быть решена эффективнее, чем за время O(n² 2ⁿ), которое даёт полный перебор, проверяющий все подмножества вершин, являются ли они независимыми множествами. Алгоритм Робсона^[6] решает задачу за время O(2^0.276n), используя экспоненциальное пространство. Если есть ограничение на размер (полиномиальность пространства), существует алгоритм решения за время O*(1.2127ⁿ)^[7].

Вопреки близкой связи между наибольшей кликой и наибольшим независимым множеством в произвольном графе, задачи нахождения независимого множества и клики могут существенно отличаться, когда решаются на специальном классе графов. Например, для разреженных графов (графы, в которых в любом подграфе число рёбер не больше числа вершин, умноженного на некоторую константу) наибольшая клика имеет ограниченный размер и может быть найдена точно за линейное время^[8]. Тем не менее, для тех же классов графов, или даже для случая более жёстких ограничений у класса графов с ограниченной степенью, поиск наибольшего независимого множества является MAXSNP-полной^[en], что означает, что для некоторой константы c (зависящей от степени) NP-трудно найти приближённое решение, отличающееся на множитель c от оптимального^[9]. Однако эффективные приближённые алгоритмы известны, но для них гарантированная эффективность хуже, чем этот порог. Например, жадный алгоритм создаёт максимальное по включению независимое множество, на каждом шаге выбирая вершину с минимальной степенью и удаляя её соседей. Этот алгоритм достигает гарантированной эффективности (Δ+2)/3 на графах с максимальной степенью Δ^[10].

В некоторых классах графов (включая графы без клешней^[11] и совершенные графы^[12]; к последнему классу принадлежат и деревья) наибольшее независимое множество может быть найдено за полиномиальное время. Для планарных графов задача о наибольшем независимом множестве остаётся NP-полной для точного решения, но может быть аппроксимирована с любой гарантированной эффективностью c < 1 за полиномиальное время. Похожие приближённые схемы полиномиального времени существуют в любом семействе минорно замкнутых графов^[13][14].

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

Поиск максимальных по включению независимых множеств[править | править код]

Все максимальные по включению независимые множества можно найти за время O(3^n/3).

Программное обеспечение для поиска независимых множеств[править | править код]

Название	Лицензия	Язык API	Описание
igraph	GPL	C, Python, R, Ruby	точное решение
NetworkX	BSD	Python	приближённое решение, см. процедуру maximum_independent_set
OpenOpt	BSD	Python	точные и приближённые решения, возможность указать вершины, которые следует включить / исключить. См. класс STAB для деталей и примеров

Наибольшее независимое множество в дереве[править | править код]

Если данный граф является деревом, то задача о независимом множестве эффективно решается методом динамического программирования.

Оптимальная подструктура задачи[править | править код]

Структура дерева сама подсказывает решение задачи. Именно, обозначим корнем дерева любую вершину и назовем её . Пусть обозначает размер наибольшего независимого множества вершин поддерева, корнем которого является вершина . Тогда ответом на задачу будет являться .

Нетрудно видеть, что если мы включаем вершину u в наибольшее независимое множество, то его мощность увеличивается на 1, но его детей мы брать не можем (так как они соединены ребром с вершиной u); если же мы не включаем эту вершину, то мощность наибольшего независимого множества будет равна сумме размеров независимых множеств детей этой вершины. Остается только выбрать максимум из этих двух вариантов, чтобы получить решение задачи:

где grandchild обозначает всякого «внука» вершины, а child обозначает всякого потомка вершины.

Псевдокод[править | править код]

Считаем, что в вершине u хранится :

  function get_independent_set(Node u)
  {       
      если I(u) уже посчитано, то возвратить I(u)
      // мощность множества, которое можно получить, если не брать вершину u
      children_sum = 0
      // мощность множества, которое можно получить, если взять вершину u
      grandchildren_sum = 0
      // цикл по всем детям
      for i := 1 to child_num do
         children_sum = children_sum + get_independent_set(children[i])
      // цикл по всем внукам
      for i:= 1 to grandchildren_num
         grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
      // запоминаем, чтобы не пересчитывать ещё раз
      I(u) = max(1 + grandchildren_sum, children_sum)
      возвратить I(u)
  }

Вызов get_independent_set(r) даст ответ на задачу. Время выполнения алгоритма, очевидно, O(|V| + |E|).

См. также[править | править код]

• Алгоритм Брона — Кербоша для нахождения максимальных по включению независимых множеств вершин.

Примечания[править | править код]

Литература[править | править код]

• Chris Godsil, Gordon Royle. . Algebraic Graph Theory. — New York: Springer, 2004. — ISBN 0-387-95220-9.
• Grötschel M., Lovász L., Schrijver A. . 9.4. Coloring Perfect Graphs // Geometric Algorithms and Combinatorial Optimization. — Springer, 1988. — (Algorithms and Combinatorics, vol. 2). — ISBN 0-387-13624-X. — P. 296–298.
• Karp, Richard.  Reducibility Among Combinatorial Problems // Proceedings of a Symposium on the Complexity of Computer Computations. — 1972.
• Michael R. Garey, David S. Johnson. . Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5.
• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. . Chapter 6. Dynamic Programming // Algorithms. — McGraw-Hill Science/Engineering/Math, 2006. — ISBN 0073523402. — P. 336.
• Sbihi, Najiba Sbihi.  Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile // Discrete Mathematics. — 1980. — Vol. 29, no. 1. — P. 53–76. — doi:10.1016/0012-365X(90)90287-R.

Ссылки[править | править код]

• Weisstein, Eric W. Maximal Independent Vertex Set (англ.) на сайте Wolfram MathWorld.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
• Поликарпова Н., Герасименко А.  Методы решения труднорешаемых задач
• Слайды лекции о динамическом программировании
• Видео лекции о динамическом программировании
• Русов В.С., Захарова Д.А. Эвристический алгоритм поиска максимального по весу независимого множества вершин в графе

Независимые множества

Независимое
множество вершин
– множество вершин графа G:
SV
такое, что любые две вершины в нем
несмежны, то есть никакая пара вершин
не соединена ребром.

подграф,
порожденный независимым множеством
– пустой
граф.

Максимальное
независимое множество –
не является собственным подмножеством
другого независимого множества.

Наибольшее
независимое множество – наибольшее
по мощности среди всех независимых
множеств.

Число
независимости (G)
графа G
– мощность
наибольшего независимого множества.

Например:

М

Граф
G:

аксимальные независимые множества:

S₁={X₁,
X₃};

S₂={X₂,
X₇,
X₈};

S₃={X₂,
X₅,
X₇,
X₈};

S₄={X₄,
X₆};

S₅={X₁,
X₃,
X₇};

S₆={X₂,
X₄,
X₈};

S₇={X₃,
X₆};

S₈={X₁,
X₄}.

Наибольшее
независимое множество: S₃={X₂,
X₅,
X₇,
X₈}.

Число
независимости графа G
: (G)=4.

Клика

Клика
– антипод
независимого множества. Подмножество
вершин графа G
такое, что любая пара из этого множества
является смежной.

подграф,
порожденный кликой – полный граф.

Максимальная
клика – не
является собственным подмножеством
никакой другой клики графа G.

Наибольшая
клика – наибольшая
по мощности среди всех остальных клик
графа G.

Кликовое
число или плотность (G)
графа G
–
мощность
наибольшей клики.

Н

Граф
G

апример:

клики
графа G:

S₁={a,b,с};

S₂={b,d,e};

S₃={b,c,e};

S₄={b,d,c};

S₅={c,d,e};

S₆={b,c,d,e}.

Максимальные
клики: S₁={a,b,с},
S₆={b,c,d,e}.

Наибольшая
клика: S₆={b,c,d,e}.

Кликовое
число: (G)=4

Доминирующие множества

Доминирующее (внешне устойчивое)
множество –
подмножество V’V
вершин графа такое, что каждая вершина
из VV’
смежна с некоторой вершиной из V’.
Иначе, каждая вершина графа находится
на расстоянии не более одного ребра от
данного множества.

Минимальное
доминирующее множество – нет
другого доминирующего множества,
содержащегося в данном.

Наименьшее
доминирующее множество – доминирующее
множество с наименьшей мощностью.

Число
доминирования (G)
– мощность
наименьшего доминирующего множества.

Например:

Минимальные
доминирующие множества:

S₁={X₁,
X₄}

S₂={X₃,
X₅,
X₆}

наименьшее
доминирующее множество: S₁={X₁,
X₄}.

Число
доминирования: (G)=2.

Задание к лабораторной работе

1. Используя
   алгоритм генерации варианта GV
   (приложение А), построить неориентированный
   граф G:
   GV(7,{2,3}).

2. Описать
   граф матрицей смежности и матрицей
   инцидентности.

3. Изобразить
   графически графG
   и его дополнение
   G.

4. Построить
   произвольный остовный подграф и подграф,
   порожденный вершинами {1,2,5,6,7};

5. Построить
   все помеченные 5-графы, изоморфно
   вложимые в граф G.

5.1. Определить
классы изоморфных графов.

5.2. Построив биекцию
их вершин.

5.3 Для каждого
класса изоморфных графов привести
рисунок абстрактного графа.

1. Построить
   все помеченные (5-7)-графы (до 20 штук),
   изоморфные некоторому подграфу G.

6.1. Определить
классы изоморфных графов.

6.2. Построив биекцию
их вершин.

6.3. Для каждого
класса таких графов привести рисунок
абстрактного графа.

1. Найти
   все максимальные и наибольшие независимые
   множества исходного графа, определить
   число независимости.

2. Найти
   все максимальные и наибольшие клики
   данного графа. Определить плотность
   графа G.

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

4. Найти
   полный двудольный подграф
   K_p,q,
   изоморфно вложимый в G
   с максимальным
   количеством вершин p+q
   (p≠1).
   Найти звезду K_1,n
   , изоморфно вложимую в G
   с максимальным
   n.
   

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

  16.11.2019316.42 Кб0om.doc

• #

From Wikipedia, the free encyclopedia

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph’s complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called “internally stable sets”, of which “stable set” is a shortening.^[1]

A maximal independent set is an independent set that is not a proper subset of any other independent set.

A maximum independent set is an independent set of largest possible size for a given graph . This size is called the independence number of and is usually denoted by .^[2] The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem.^[3] As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

Every maximum independent set also is maximal, but the converse implication does not necessarily hold.

Properties[edit]

Relationship to other graph parameters[edit]

A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory.

A set is independent if and only if its complement is a vertex cover.^[4] Therefore, the sum of the size of the largest independent set and the size of a minimum vertex cover is equal to the number of vertices in the graph.

A vertex coloring of a graph corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number , is at least the quotient of the number of vertices in and the independent number .

In a bipartite graph with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is Kőnig’s theorem.

Maximal independent set[edit]

An independent set that is not a proper subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3^n/3 maximal independent sets,^[5] but many graphs have far fewer.
The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence.^[6] Therefore, both numbers are proportional to powers of 1.324718…, the plastic number.

Finding independent sets[edit]

In computer science, several computational problems related to independent sets have been studied.

• In the maximum independent set problem, the input is an undirected graph, and the output is a maximum independent set in the graph. If there are multiple maximum independent sets, only one need be output. This problem is sometimes referred to as “vertex packing“.
• In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. The maximum independent set problem is the special case in which all weights are one.
• In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets.
• In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.

The first three of these problems are all important in practical applications; the independent set decision problem is not, but is necessary in order to apply the theory of NP-completeness to problems related to independent sets.

Maximum independent sets and maximum cliques[edit]

The independent set problem and the clique problem are complementary: a clique in G is an independent set in the complement graph of G and vice versa. Therefore, many computational results may be applied equally well to either problem. For example, the results related to the clique problem have the following corollaries:

• The independent set decision problem is NP-complete, and hence it is not believed that there is an efficient algorithm for solving it.
• The maximum independent set problem is NP-hard and it is also hard to approximate.

Despite the close relationship between maximum cliques and maximum independent sets in arbitrary graphs, the independent set and clique problems may be very different when restricted to special classes of graphs. For instance, for sparse graphs (graphs in which the number of edges is at most a constant times the number of vertices in any subgraph), the maximum clique has bounded size and may be found exactly in linear time;^[7] however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is MAXSNP-complete, implying that, for some constant c (depending on the degree) it is NP-hard to find an approximate solution that comes within a factor of c of the optimum.^[8]

Exact algorithms[edit]

The maximum independent set problem is NP-hard. However, it can be solved more efficiently than the O(n² 2ⁿ) time that would be given by a naive brute force algorithm that examines every vertex subset and checks whether it is an independent set.

As of 2017 it can be solved in time O(1.1996ⁿ) using polynomial space.^[9] When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836ⁿ).^[10]

For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are claw-free graphs,^[11] P₅-free graphs^[12] and perfect graphs.^[13] For chordal graphs, a maximum weight independent set can be found in linear time.^[14]

Modular decomposition is a good tool for solving the maximum weight independent set problem; the linear time algorithm on cographs is the basic example for that. Another important tool are clique separators as described by Tarjan.^[15]

Kőnig’s theorem implies that in a bipartite graph the maximum independent set can be found in polynomial time using a bipartite matching algorithm.

Approximation algorithms[edit]

In general, the maximum independent set problem cannot be approximated to a constant factor in polynomial time (unless P = NP). In fact, Max Independent Set in general is Poly-APX-complete, meaning it is as hard as any problem that can be approximated to a polynomial factor.^[16] However, there are efficient approximation algorithms for restricted classes of graphs.

In planar graphs[edit]

In planar graphs, the maximum independent set may be approximated to within any approximation ratio c < 1 in polynomial time; similar polynomial-time approximation schemes exist in any family of graphs closed under taking minors.^[17]

In bounded degree graphs[edit]

In bounded degree graphs, effective approximation algorithms are known with approximation ratios that are constant for a fixed value of the maximum degree; for instance, a greedy algorithm that forms a maximal independent set by, at each step, choosing the minimum degree vertex in the graph and removing its neighbors, achieves an approximation ratio of (Δ+2)/3 on graphs with maximum degree Δ.^[18] Approximation hardness bounds for such instances were proven in Berman & Karpinski (1999). Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is APX-complete.^[19]

In interval intersection graphs[edit]

An interval graph is a graph in which the nodes are 1-dimensional intervals (e.g. time intervals) and there is an edge between two intervals if and only if they intersect. An independent set in an interval graph is just a set of non-overlapping intervals. The problem of finding maximum independent sets in interval graphs has been studied, for example, in the context of job scheduling: given a set of jobs that has to be executed on a computer, find a maximum set of jobs that can be executed without interfering with each other. This problem can be solved exactly in polynomial time using earliest deadline first scheduling.

In geometric intersection graphs[edit]

A geometric intersection graph is a graph in which the nodes are geometric shapes and there is an edge between two shapes if and only if they intersect. An independent set in a geometric intersection graph is just a set of disjoint (non-overlapping) shapes. The problem of finding maximum independent sets in geometric intersection graphs has been studied, for example, in the context of Automatic label placement: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations.

Finding a maximum independent set in intersection graphs is still NP-complete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of Chan & Har-Peled (2012).

In d-claw-free graphs[edit]

A d-claw in a graph is a set of d+1 vertices, one of which (the “center”) is connected to the other d vertices, but the other d vertices are not connected to each other. A d-claw-free graph is a graph that does not have a d-claw subgraph. Consider the algorithm that starts with an empty set, and incrementally adds an arbitrary vertex to it as long as it is not adjacent to any existing vertex. In d-claw-free graphs, every added vertex invalidates at most d-1 vertices from the maximum independent set; therefore, this trivial algorithm attains a (d-1)-approximation algorithm for the maximum independent set. In fact, it is possible to get much better approximation ratios:

• Neuwohner^[20] presented a polynomial time algorithm that, for any constant ε>0, finds a (d/2-1/63,700,992+ε)-approximation for the maximum weight independent set in a d-claw free graph.
• Cygan^[21] presented a quasi-polynomial time algorithm that, for any ε>0, attains a (d+ε)/3 approximation.

Finding maximal independent sets[edit]

The problem of finding a maximal independent set can be solved in polynomial time by a trivial greedy algorithm.^[22] All maximal independent sets can be found in time O(3^n/3) = O(1.4423ⁿ).

Applications[edit]

The maximum independent set and its complement, the minimum vertex cover problem, is involved in proving the computational complexity of many theoretical problems.^[23] They also serve as useful models for real world optimization problems, for example maximum independent set is a useful model for discovering stable genetic components for designing engineered genetic systems.^[24]

See also[edit]

• An independent set of edges is a set of edges of which no two have a vertex in common. It is usually called a matching.
• A vertex coloring is a partition of the vertex set into independent sets.

Notes[edit]

References[edit]

External links[edit]

• Weisstein, Eric W. “Maximal Independent Vertex Set”. MathWorld.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
• Independent Set and Vertex Cover, Hanan Ayad.

Материал из Викиконспекты

Перейти к: навигация, поиск

Независимые наборы представлены в наборах, в которых

• не должно быть никаких краев, смежных друг с другом . Между двумя ребрами не должно быть общей вершины.

• не должно быть никаких вершин, смежных друг с другом . Между любыми двумя вершинами не должно быть общего ребра.

не должно быть никаких краев, смежных друг с другом . Между двумя ребрами не должно быть общей вершины.

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

Независимый набор линий

Пусть ‘G’ = (V, E) – граф. Подмножество L в E называется множеством независимых линий ‘G’, если нет двух ребер в L смежных. Такой набор называется набором независимых строк.

пример

Давайте рассмотрим следующие подмножества –

L 1 = {a,b}
L 2 = {a,b} {c,e}
L 3 = {a,d} {b,c}

В этом примере подмножества L ₂ и L ₃ явно не являются смежными ребрами в данном графе. Это независимые линейные наборы. Однако L ₁ не является независимым линейным набором, так как для создания независимого линейного набора должно быть как минимум два ребра.

Максимальный набор независимых линий

Независимый набор линий называется максимальным набором независимых линий графа «G», если никакое другое ребро «G» не может быть добавлено к «L».

пример

Давайте рассмотрим следующие подмножества –

L 1 = {a, b}
L 2 = {{b, e}, {c, f}}
L 3 = {{a, e}, {b, c}, {d, f}}
L 4 = {{a, b}, {c, f}}

L ₂ и L ₃ – максимальные независимые наборы линий / максимальное совпадение. Что касается только этих двух подмножеств, нет никакой возможности добавить любое другое ребро, которое не является смежным. Следовательно, эти два подмножества рассматриваются как максимальные независимые линейные множества.

Максимальный набор независимых линий

Максимальный набор независимых линий с максимальным числом ребер называется максимальным набором независимых линий с G.

Number of edges in a maximum independent line set of G (β 1 )
   = Line independent number of G
   = Matching number of G

пример

Давайте рассмотрим следующие подмножества –

L 1 = {a, b}
L 2 = {{b, e}, {c, f}}
L 3 = {{a, e}, {b, c}, {d, f}}
L 4 = {{a, b}, {c, f}}

L ₃ – это максимальное независимое линейное множество G с максимальными ребрами, которые не являются смежными ребрами в графе и обозначается как β ₁ = 3.

Примечание. Для любого графа G без изолированной вершины

α ₁ + β ₁ = количество вершин в графе = | V |

пример

Номер покрытия линии K _н / с _н / ш _н ,

Независимый от линии номер (соответствующий номер) = β ₁ = ⌊ n / 2 ⌋ α ₁ + β ₁ = n

Независимый набор вершин

Пусть ‘G’ = (V, E) – граф. Подмножество V называется независимым множеством G, если в S нет двух смежных вершин.

пример

Рассмотрим следующие подмножества из приведенных выше графиков –

S 1 = {e}
S 2 = {e, f}
S 3 = {a, g, c}
S 4 = {e, d}

Ясно, что S ₁ не является независимым множеством вершин, потому что для получения независимого множества вершин в графе должно быть как минимум две вершины. Но здесь это не тот случай. Подмножества S ₂ , S ₃ и S ₄ являются независимыми наборами вершин, потому что нет вершин, смежных с какой-либо одной вершиной из подмножеств.

Максимальный независимый набор вершин

Пусть ‘G’ граф, тогда независимое множество вершин из G называется максимальным, если никакая другая вершина из G не может быть добавлена ​​к ‘S’.

пример

Рассмотрим следующие подмножества из приведенных выше графиков.

S 1 = {e}
S 2 = {e, f}
S 3 = {a, g, c}
S 4 = {e, d}

S ₂ и S ₃ – максимальные независимые множества вершин группы ‘G’. В S ₁ и S ₄ мы можем добавить другие вершины; но в S ₂ и S ₃ мы не можем добавить любую другую вершину

Максимально независимый набор вершин

Максимальное независимое множество вершин из G с максимальным количеством вершин называется максимальным независимым множеством вершин.

пример

Рассмотрим следующие подмножества из приведенного выше графика –

S 1 = {e}
S 2 = {e, f}
S 3 = {a, g, c}
S 4 = {e, d}

Только S ₃ является максимальным независимым множеством вершин, поскольку оно охватывает наибольшее количество вершин. Количество вершин в максимальном независимом множестве вершин группы G называется независимым числом вершин группы G (β ₂ ).

пример

For the complete graph K n ,
      Vertex covering number = α 2 = n−1
      Vertex independent number = β 2 = 1
You have α 2 + β 2 = n
In a complete graph, each vertex is adjacent to its remaining (n − 1) vertices. Therefore, a maximum independent set of K n contains only one vertex.
Therefore,   β 2 =1
and          α 2 =|v| − β 2 = n-1

Примечание. Для любого графа «G» = (V, E)

α ₂ + β ₂ = | v |

Если ‘S’ является независимым множеством вершин ‘G’, то (V – S) является покрытием вершин G.