Билет 12. Независимость и покрытия

  • ID: 32766 
  • 11 страниц

Фрагмент работы:

Сибирский государственный университет телекоммуникаций и информатики

Дистанционное обучение

«Автоматизированное проектирование телекоммуникационных сетей». Экзамен

Билет № 12

Независимость и покрытия.

(или ) вершин графа называется такое множество вершин, что никакие две вершины из этого множества не смежны. Иными словами, если множество вершин независимо, то подграф, порожденный этим множеством, пустой.

множеством вершин называется такое независимое множество, которое не является собственным подмножеством другого независимого множества.

множеством вершин называется независимое множество наибольшей мощности.

Заметим сразу, что не всякое максимальное независимое множество будет являться наибольшим независимым.

() графа называется число вершин наибольшего независимого множества и обозначается

Теорема об оценке снизу числа независимости произвольного графа.

Для любого графа верно неравенство:

Алгоритм построения независимого множества.

Опишем простой алгоритм построения независимого множества такого, что

[image]

Каждый раз в графе выбирается вершина минимальной степени и заносится в множество . Затем эта вершина и все смежные с ней удаляются из графа и процесс продолжается. Множество , полученное таким способом, иногда принимают в качестве приближенного решения задачи отыскания наибольшего независимого множества в графе.

Независимое множество вершин графа имеет простую матричную интерпретацию. Пусть - независимое множество вершин графа - матрица смежности. Множеству в матрице соответствует подматрица, элементы которой, расположенные в строках и столбцах, соответствующих элементам множества , равны нулю. Такое представление позволяет получить верхнюю оценку числа с помощью характеристических чисел матрицы

Обозначим черези число положительных, отрицательных и нулевых собственных значений матрицы смежности графа соответственно.

Теорема о верхней оценке числа независимости произвольного графа.

Для всякого графа справедливо неравенство

[image]

Независимые множества вершин графа имеют самые разнообразные применения. Рассмотрим одно из применений независимости в теории информации. Возникающую здесь ситуацию можно упрощенно описать следующим образом.