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

Intersection graph.gif

В теории графов графом пересечений называется граф, представляющий[en] схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.

Обзор теории графов пересечений и важных специальных классов графов пересечений смотрите в книге МакКи и МакМорриса[1].

Формальное определениеПравить

Граф пересечений — это неориентированный граф, образованный из семейства множеств

 

путём создания вершины   для каждого множества   и соединения двух вершин   и   ребром, если соответствующие два множества имеют непустое пересечение, то есть

 .

Все графы являются графами пересеченийПравить

Любой неориентированный граф G можно представить как граф пересечений — для любой вершины   графа G образуем множество  , состоящее из рёбер, инцидентных  . Два таких множества имеют непустое пересечение тогда и только тогда, когда соответствующие вершины принадлежат одному ребру. Эрдёш, Гудман и Поза[2] показали более эффективное построение (которое требует меньше элементов во всех множествах  ), в котором общее число элементов в множествах не превосходит  , где n — число вершин в графе. По их утверждению, что все графы являются графами пересечений, заметил Марчевский[3], но также рекомендовали посмотреть работы Чулика[4]. Число пересечений графа — это минимальное число элементов в представлениях графа, как графа пересечений.

Классы графов пересеченийПравить

Много важных семейств графов можно описать как графы пересечений ограниченных типов множеств, например, множеств, полученных из некоторых геометрических конфигураций:

Вариации и обобщенияПравить

  • Теоретическими аналогами порядка графов пересечений служат порядки вложенности[en]. Точно таким же образом, каким представление графа пересечений помечает каждую вершину множеством инцидентных ей рёбер, имеющих непустое пересечение, представление порядка вложенности f частично упорядоченного множества помечает каждый элемент таким множеством, что для любого x и y в нём   тогда и только тогда, когда  .
  • Нерв покрытия

ПримечанияПравить

ЛитератураПравить

СсылкиПравить