Граф пересечений: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Граф пересечений''' (''Intersection graph'') - граф <math>\Omega(F)</math>, определенный для пок...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
'''Граф пересечений''' (''Intersection graph'') -
'''Граф пересечений''' (''[[Intersection graph]]'') — [[граф]] <math>\Omega(F)</math>, определенный для покрытия <math>F = (S_{1}, S_{2}, \ldots , S_{n})</math> непустого множества <math>S</math> непустыми несовпадающими подмножествами; [[вершина|вершины]] графа <math>\Omega(F)</math> суть подмножества <math>S_{i}</math> и две вершины <math>S_{i}</math> и <math>S_{j}</math> [[смежные вершины|смежны]], если <math>S_{i} \cap S_{j} \neq \emptyset</math>.
граф <math>\Omega(F)</math>, определенный для покрытия <math>F = (S_{1}, S_{2},
\ldots , S_{n})</math>непустого множества <math>S</math> непустыми несовпадающими
подмножествами; вершины графа <math>\Omega(F)</math> суть подмножества
<math>S_{i}</math>и две вершины <math>S_{i}</math>и <math>S_{j}</math>смежны, если <math>S_{i} \cap
S_{j} \neq \emptyset</math>.
==Литература==
==Литература==
[Харари],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.


[Лекции]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия от 16:26, 1 февраля 2011

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