Теория графов - независимые множества

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

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

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

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

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

пример

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

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

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

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

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

Независимый набор линий называется максимальным набором независимых линий графа «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 2 и L 3 являются максимальными независимыми наборами линий / максимальным соответствием. Что касается только этих двух подмножеств, нет никакой возможности добавить любое другое ребро, которое не является смежным. Следовательно, эти два подмножества рассматриваются как максимальные независимые линейные множества.

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

Максимальный набор независимых линий с максимальным числом ребер называется максимальным набором независимых линий с 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 3 - это максимальное независимое линейное множество G с максимальными ребрами, которые не являются смежными ребрами в графе и обозначается как β 1 = 3.

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

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

пример

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

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

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

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

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

пример

Пример независимого набора вершин

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

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

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

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

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

пример

Пример максимального независимого набора вершин

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

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

S 2 и S 3 - максимальные независимые множества вершин группы 'G'. В S 1 и S 4 мы можем добавить другие вершины; но в S 2 и S 3 мы не можем добавить любую другую вершину

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

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

пример

Пример максимального независимого набора вершин

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

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

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

пример

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)

  • α 2 + β 2 = | v |

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