Лучшие вопросы
Таймлайн
Чат
Перспективы

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

граф, представляющий схему пересечений семейства множеств Из Википедии, свободной энциклопедии

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

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

Thumb

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

Remove ads

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

Суммиров вкратце
Перспектива

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

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

.
Remove ads

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

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

Remove ads

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

Суммиров вкратце
Перспектива

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

Вариации и обобщения

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

Примечания

Литература

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads