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

Эта статья посвящена непересекающимся объединениям полных графов. Для графов с кластеризованными вершинами см. кластерная планарность. Для визуализации кластеризации см. диаграмма кластера.
Граф кластеров с кластерами (полными подграфами) размеров 1, 2, 3, 4, 4, 5 и 6

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

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

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

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

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

А подкрашивание графа - это разбиение его вершин на индуцированный кластерные графы. Таким образом, кластерные графы - это в точности графы субхроматического числа 1.[5]

Вычислительная задача поиска небольшого набора ребер, которые нужно добавить или удалить из графа, чтобы преобразовать его в кластерный граф, называется редактирование кластера. это НП-полный[6] но управляемый с фиксированными параметрами.[7]

Рекомендации

  1. ^ а б Кластерные графики, Информационная система по классам графов и их включениям, доступ 2016-06-26.
  2. ^ Nishimura, N .; Ragde, P .; Тиликос, Д. (2002), "О степенях графа для деревьев с листами", Журнал алгоритмов, 42: 69–108, Дои:10.1006 / jagm.2001.1195.
  3. ^ Гардинер, А. (1976), "Однородные графы", Журнал комбинаторной теории, Серия B, 20 (1): 94–102, Дои:10.1016/0095-8956(76)90072-1, МИСТЕР  0419293.
  4. ^ Lachlan, A.H .; Вудро, Роберт Э. (1980), "Счетные сверходнородные неориентированные графы", Труды Американского математического общества, 262 (1): 51–94, Дои:10.2307/1999974, МИСТЕР  0583847.
  5. ^ Albertson, M.O .; Jamison, R.E .; Hedetniemi, S.T .; Локк, С. К. (1989), "Субхроматическое число графа", Дискретная математика, 74 (1–2): 33–49, Дои:10.1016 / 0012-365X (89) 90196-9.
  6. ^ Шамир, Рон; Шаран, Родед; Цур, Декель (2004), "Проблемы модификации кластерного графа", Дискретная прикладная математика, 144 (1–2): 173–182, Дои:10.1016 / j.dam.2004.01.007, МИСТЕР  2095392.
  7. ^ Бёкер, Себастьян; Баумбах, январь (2013), «Кластерное редактирование», Природа вычислений, Конспект лекций по вычисл. Наук, 7921, Springer, Heidelberg, стр. 33–44, Дои:10.1007/978-3-642-39053-1_5, МИСТЕР  3102002.