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

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

Независимое множество из 9 голубых вершин

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

В неориентированном графе множество его вершин , где , называется независимым (или внутренне устойчивым), если любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром [1] [2] [3], или другими словами множество порождает пустой подграф:

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

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

В неориентированном графе множество его рёбер , где , называется независимым, если никакая пара ребер несмежна [1] [3] или множество порождает пустой подграф:

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

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

Примечания

Литература

  • Chartran G., Zhang P. Chromatic Graph Theory (англ.) / Series Editor Kenneth H. Rosen. — Baca Ration, London, New York: Chapman & Hall/CRC, 2009. — P. 483. — (Discrete Mathematics and Its Applications). — ISBN 978-1-58488-800-0.
  • Кристофидес Н. Теория графов. Алгоритмический подход.. М.: Мир, 1978. — 432 с.
  • Харари Ф. Теория графов.. М.: Мир, 1973. — 300 с.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.