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

Материал из WEGA
Версия от 16:26, 1 февраля 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

Литература

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