Граф пересечений

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф пересечений (Intersection graph) — граф \Omega(F), определенный для покрытия F = (S_{1}, S_{2}, \ldots , S_{n}) непустого множества S непустыми несовпадающими подмножествами; вершины графа \Omega(F) суть подмножества S_{i} и две вершины S_{i} и S_{j} смежны, если S_{i} \cap S_{j} \neq \emptyset.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Харари Ф. Теория графов. — М.: Мир, 1973.