Кластерный график

Граф, созданный из несвязного объединения полных графов

Кластерный граф с кластерами (полными подграфами) размеров 1, 2, 3, 4, 4, 5 и 6

В теории графов , разделе математики , граф кластера — это граф, образованный из несвязного объединения полных графов . Эквивалентно, граф является графом кластера тогда и только тогда, когда он не имеет трехвершинного индуцированного пути ; по этой причине графы кластера также называются графами без P ₃ . Они являются дополнительными графами полных многодольных графов ^[1] и степеней 2-листа . ^[2] Графы кластера транзитивно замкнуты , и каждый транзитивно замкнутый неориентированный граф является графом кластера. ^[3]

Кластерные графы — это графы, для которых смежность является отношением эквивалентности , а их связные компоненты — классами эквивалентности для этого отношения.

Связанные классы графов

Каждый кластерный граф является блочным графом , кографом и графом без клешней . ^[1] Каждое максимальное независимое множество в кластерном графе выбирает одну вершину из каждого кластера, поэтому размер такого множества всегда равен количеству кластеров; поскольку все максимальные независимые множества имеют одинаковый размер, кластерные графы хорошо покрыты . Графы Турана являются дополнительными графами кластерных графов, со всеми полными подграфами равного или почти равного размера. Локально кластеризованный граф (графы, в которых каждая окрестность является кластерным графом) являются ромбовидными графами , другим семейством графов, которое содержит кластерные графы.

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

Вычислительные проблемы

Подраскраска графа — это разбиение его вершин на индуцированные кластерные графы. Таким образом, кластерные графы — это в точности графы субхроматического числа 1. ^[6]

Вычислительная задача поиска небольшого набора ребер для добавления или удаления из графа для преобразования его в кластерный граф называется кластерным редактированием. Она является NP-полной ^[7], но поддается обработке с фиксированными параметрами . ^[8]

При наличии полного графа со стоимостью ребер (положительной и отрицательной) задача разбиения клик требует подграфа, который является графом кластера, таким образом, что сумма стоимостей ребер графа кластера минимальна. ^[9] Эта задача тесно связана с задачей корреляционной кластеризации .

Ссылки

1. Кластерные графы, Информационная система по классам графов и их включениям, дата обращения 26.06.2016.
2. Нишимура, Н.; Рагде, П.; Тиликос, Д.М. (2002), «О степенях графов для деревьев с метками листьев», Журнал алгоритмов , 42 : 69–108, doi :10.1006/jagm.2001.1195.
3. Макколл, У. Ф.; Ношита, К. (1986), «О числе ребер в транзитивном замыкании графа», Дискретная прикладная математика , 15 (1): 67–73, doi : 10.1016/0166-218X(86)90020-X , MR  0856101
4. Гардинер, А. (1976), «Однородные графы», Журнал комбинаторной теории , Серия B, 20 (1): 94–102, doi : 10.1016/0095-8956(76)90072-1 , MR  0419293.
5. Лаклан, AH; Вудро, Роберт Э. (1980), «Счетные ультраоднородные неориентированные графы», Труды Американского математического общества , 262 (1): 51–94, doi : 10.2307/1999974 , MR  0583847.
6. Альбертсон, МО; Джеймисон, Р. Э.; Хедетниеми, С. Т.; Локк, С. К. (1989), «Субхроматическое число графа», Дискретная математика , 74 (1–2): 33–49, doi : 10.1016/0012-365X(89)90196-9.
7. Шамир, Рон; Шаран, Родед; Цур, Декель (2004), «Проблемы модификации кластерных графов», Дискретная прикладная математика , 144 (1–2): 173–182, doi : 10.1016/j.dam.2004.01.007 , MR  2095392.
8. Бёккер, Себастьян; Баумбах, Ян (2013), «Редактирование кластера», Природа вычислений , Lecture Notes in Comput. Sci., т. 7921, Springer, Гейдельберг, стр. 33–44, doi :10.1007/978-3-642-39053-1_5, MR  3102002.
9. Грётшель, Мартин; Вакабаяши, Ёсико (1989), Алгоритм отсекающей плоскости для задачи кластеризации , Математическое программирование, т. 45, Springer, стр. 59–96, doi :10.1007/BF01589097.