Независимые наборы представлены в наборах, в которых
-
не должно быть никаких краев, смежных друг с другом . Между двумя ребрами не должно быть общей вершины.
-
не должно быть никаких вершин, смежных друг с другом . Между любыми двумя вершинами не должно быть общего ребра.
не должно быть никаких краев, смежных друг с другом . Между двумя ребрами не должно быть общей вершины.
не должно быть никаких вершин, смежных друг с другом . Между любыми двумя вершинами не должно быть общего ребра.
Независимый набор линий
Пусть ‘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.