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

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

Теорема о графах пересечений.Для любого графасуществует такое семейство множеств F, что .