29.04.2021

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


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

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

В неориентированном графе G = ( V , E ) {displaystyle G=(V,E)} множество его вершин S {displaystyle S} , где S ⊂ V {displaystyle Ssubset V} , называется независимым (или внутренне устойчивым), если любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром , или другими словами множество S {displaystyle S} порождает пустой подграф:

G ( S , E ′ ) ⊂ G     ⇒     E ′ = ∅ {displaystyle G(S,E^{prime })subset G~~Rightarrow ~~E^{prime }=varnothing }

Наибольшее число вершин в таких множествах называется вершинным числом независимости (иногда просто числом независимости) β 0 ( G ) {displaystyle eta _{0}(G)} графа G {displaystyle G} , то есть, если Q {displaystyle Q} есть семейство всех независимых множеств вершин S {displaystyle S} , то β 0 ( G ) = max { | S | : S ∈ Q } {displaystyle eta _{0}(G)=max{|S|:Sin Q}} .

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

В неориентированном графе G = ( V , E ) {displaystyle G=(V,E)} множество его ребер M {displaystyle M} , где M ⊂ E {displaystyle Msubset E} , называется независимым, если никакая пара ребер несмежна или множество M {displaystyle M} порождает пустой подграф:

G ( V ′ , M ) ⊂ G     ⇒     V ′ = ∅ {displaystyle G(V^{prime },M)subset G~~Rightarrow ~~V^{prime }=varnothing }

Наибольшее число ребер в таких множествах называется реберным числом независимости β 1 ( G ) {displaystyle eta _{1}(G)} графа G {displaystyle G} , то есть, если W {displaystyle W} есть семейство всех независимых множеств ребер M {displaystyle M} , то β 1 ( G ) = max { | M | : M ∈ W } {displaystyle eta _{1}(G)=max{|M|:Min W}} .

Множество независимых ребер также называют паросочетанием . Поэтому независимое множество M {displaystyle M} , имеющее кардинальное число β 1 {displaystyle eta _{1}} называется наибольшим паросочетанием графа G {displaystyle G} .


Похожие новости:

Матрица Кирхгофа

Матрица Кирхгофа
Матрица Кирхгофа — одно из представлений конечного графа с помощью матрицы. Матрица Кирхгофа представляет дискретный оператор Лапласа для графа. Она используется для подсчета остовных деревьев

Эпсилон-окрестность

Эпсилон-окрестность
ε {displaystyle varepsilon } -окрестность множества в функциональном анализе и смежных дисциплинах — это такое множество, каждая точка которого удалена от данного множества

Спектральная теория графов

Спектральная теория графов
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как

Размерность Хаусдорфа

Размерность Хаусдорфа
Размерность Хаусдорфа, или хаусдорфова размерность — естественный способ определить размерность подмножества в метрическом пространстве. Размерность Хаусдорфа согласуется с нашими обычными
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные новости
Перепланировка за счет объединения туалета и ванной комнаты
Перепланировка за счет объединения туалета и ванной комнаты
Обычно вопроса о том, нужно ли объединять туалет и ванную комнату не стоит в новых домах....
Особенности и плюсы каркасных домов
Особенности и плюсы каркасных домов
Кирпич – традиционный материал для строительства загородных домов, однако в последнее время его...
Зачем нужны конвекторы в частном доме
Зачем нужны конвекторы в частном доме
Частный дом - это то, что сегодня требует вложений времени и внимания. И, тут стоит понимать, что...
Все новости