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

Материал из WEGA
Версия от 15:29, 8 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Граф пересечений''' (''Intersection graph'') - граф <math>\Omega(F)</math>, определенный для пок...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Граф пересечений (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].

Литература

[Харари],

[Лекции]