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