Индифферентный граф

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

Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицуШаблон:Sfn. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения (никакой интервал не содержит какой-либо другой). Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными интервальными графами. Индифферентные графы образуют подкласс интервальных графов.

Эквивалентные описания

Запрещённые порождённые подграфы для индифферентных графов — клешня, «солнце», «сеть» и циклы длиной четыре и более (внизу)

Конечные индифферентные графы можно эквивалентно описать как

• Графы пересечений единичных отрезковШаблон:Sfn
• Графы пересечений множеств интервалов, никакие два из которых не вложены друг в другаШаблон:SfnШаблон:Sfn
• Интервальные графы без клешнейШаблон:SfnШаблон:Sfn
• Графы, не содержащие порождённых подграфов, изоморфных клешне K_1,3, «сети» (треугольника с тремя дополнительными вершинами, присоединёнными к каждой вершине треугольника), «солнцу» (треугольнику с тремя присоединёнными треугольниками, имеющими общие рёбра с центральным треугольником), или «дыры» (циклы длины четыре и более)Шаблон:Sfn
• Графы несравнимости Шаблон:Не переведено 5Шаблон:Sfn
• Неориентированные графы, которые имеют линейный порядок, такой, что для каждого пути из трёх вершин $uvw$, вершины которого упорядочены $u$–$v$–$w$, конечные вершины $u$ и $w$ смежны Шаблон:Sfn
• Графы, не имеющие астральных троек, трёх вершин, соединённых попарно путями, не проходящими через третью вершину, а также не содержащие двух смежных вершин, одновременно смежных вершине из окрестности третьей вершины Шаблон:Sfn.
• Графы, в которых каждая компонента содержит путь, в котором каждая клика компоненты образует непрерывный подпутьШаблон:Sfn
• Графы, вершины которых могут быть пронумерованы таким образом, что любой кратчайший путь образует монотонную последовательностьШаблон:Sfn
• Графы, матрицы смежности которых могут быть упорядочены так, что в каждой строке и каждом столбце ненулевые элементы образуют непрерывные интервалы, смежные диагонали матрицыШаблон:Sfn
• Порождённые подграфы степеней безхордовых путейШаблон:Sfn
• Шаблон:Не переведено 5, имеющие Шаблон:Не переведено 5 в виде гусеницыШаблон:Sfn

Для бесконечных графов некоторые из этих определений могут дать различные графы.

Свойства

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

В модели Эрдёша — Реньи случайных графов граф с $n$ вершины, число рёбер которого существенно меньше $n^{2/3}$, будет с большой вероятностью индифферентным графом, в то время как графы с числом рёбер, существенно большим $n^{2/3}$, с большой вероятностью не будет индифферентным графомШаблон:Sfn.

Шаблон:Не переведено 5 произвольного графа $G$ на единицу меньше размера наибольшей клики в индифферентном графе, который содержит $G$ в качестве подграфа и выбран для минимизации размера наибольшей кликиШаблон:Sfn. Это свойство образует параллели, подобные связи между путевой шириной и интервальными графами, а также между древесной шириной и хордальными графами. Более слабое понятие ширины, кликовая ширина, может быть произвольно большой на индифферентных графахШаблон:Sfn. Однако любой собственный подкласс индифферентных графов, не замкнутый относительно порождённых подграфов, имеет ограниченную кликовую ширинуШаблон:Sfn.

Любой связный индифферентный граф содержит гамильтонов путьШаблон:Sfn. Индифферентный граф имеет гамильтонов цикл тогда и только тогда, когда он двусвязенШаблон:Sfn.

Индифферентные графы удовлетворяет Шаблон:Не переведено 5 — они единственным образом определяются их подграфами с удалённой вершинойШаблон:Sfn.

Алгоритмы

Как и с многомерными графами единичных дисков, можно преобразовать множество точек в их индифферентный граф или множество единичных отрезков в их граф единичных отрезков за линейное время, если измерять в терминах размера выходного графа. Алгоритм округляет точки (или центры интервалов) к ближайшему меньшему целому числу, использует хеш-таблицу для нахождения всех пар точек, чьи округлённые значения отличаются не более чем на единицу (задача поиска ближайшего соседа с фиксированным радиусом), и отбирает в полученном списке пары, неокруглённые значения которых находятся не далее чем на единицу друг от другаШаблон:Sfn.

Можно проверить, является ли данный граф индифферентным за линейное время с помощью PQ-деревьев для построения интервальных представлений графа и затем проверки, удовлетворяет ли упорядочение вершин, производное от этого представления, свойствам индифферентного графаШаблон:Sfn. Можно также основать алгоритм распознавания для индифферентных графов на алгоритмах распознавания для хордального графаШаблон:Sfn. Некоторые альтернативные алгоритмы распознавания за линейное время основываются на поиске в ширину или на лексикографическом поиске в ширину, а не на связи между индифферентными графами и интервальными графамиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

Как только вершины отсортированы по их числовым значениям, которые описывают индифферентный граф (или по последовательности единичных отрезков в интервальном представлении), тот же самый порядок можно использовать для поиска оптимальной раскраски этих графов, чтобы решить задачу о кратчайшем пути, построения гамильтоновых путей и наибольших паросочетаний за линейное времяШаблон:Sfn. Гамильтонов цикл можно найти из правильного интервального графа представления за время $O(n\log n)$Шаблон:Sfn, но если граф является входным для задачи, та же задача может быть решена за линейное время, что может быть обобщено на интервальные графыШаблон:SfnШаблон:Sfn.

Предписанная раскраска остаётся NP-полной, даже когда она ограничена индифферентными графамиШаблон:Sfn. Однако она является Шаблон:Не переведено 5, если параметризовать по общему числу цветов на входеШаблон:Sfn.

Приложения

В математической психологии индифферентные графы возникают из функций полезности путём масштабирования функции так, что одна единица представляет разность в полезности достаточно малой, так что для личности единица может рассматриваться как несущественная. В этом приложении пары элементов, полезности которых достаточно велики, могут быть частично упорядочены по относительному порядку полезности, что даёт Шаблон:Не переведено 5 Шаблон:SfnШаблон:Sfn.

В биоинформатике задача добавления раскрашенного графа к правильно раскрашенному графу единичных отрезков может быть использована для моделирования обнаружения ложноотрицательных сборок генома ДНК из фрагментовШаблон:Sfn.

См.также

• Пороговый граф, a graph whose edges are determined by sums of vertex labels rather than differences of labels
• Тривиально совершенный граф, интервальные графы for which every pair of intervals is nested or disjoint rather than properly intersecting

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга. Как процитировано в Шаблон:Harnb
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Information System on Graph Class Inclusions: unit interval graph