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