Пороговый график

В теории графов — пороговый граф это граф, который можно построить из графа с одной вершиной путем повторного применения следующих двух операций:

Добавление в граф единственной изолированной вершины.
Добавление в граф одной доминирующей вершины , т. е. одной вершины, соединенной со всеми остальными вершинами.

Например, график фигуры является пороговым графиком. Его можно построить, начав с одновершинного графа (вершина 1), а затем добавив черные вершины в качестве изолированных вершин и красные вершины в качестве доминирующих вершин в том порядке, в котором они пронумерованы.

Пороговые графики были впервые представлены Хваталом и Хаммером (1977) . Глава о пороговых графах появляется в работе Golumbic (1980) книга Mahadev & Peled (1995) , им посвящена .

Альтернативные определения

Эквивалентное определение следующее: граф является пороговым графом, если существуют действительные числа. $S$ и для каждой вершины $v$ реальный вес вершины $w(v)$ такая, что для любых двух вершин $v,u$ , $uv$ является ребром тогда и только тогда, когда $w(u)+w(v)>S$ .

Другое эквивалентное определение таково: график является пороговым, если существуют действительные числа. $T$ и для каждой вершины $v$ реальный вес вершины $a(v)$ такая, что для любого множества вершин $X\subseteq V$ , $X$ независим когда тогда и только тогда, $\sum _{v\in X}a(v)\leq T.$

Название «пороговый граф» происходит от следующих определений: S — это «порог» свойства быть ребром, или, что эквивалентно, T — это порог независимости.

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

Разложение

Из определения, в котором используется повторное добавление вершин, можно получить альтернативный способ однозначного описания порогового графа с помощью строки символов. $\epsilon$ всегда является первым символом строки и представляет первую вершину графа. Каждый последующий символ либо $u$ , что означает добавление изолированной вершины (или вершины объединения ), или $j$ , что означает добавление доминирующей вершины (или вершины соединения ). Например, строка $\epsilon uuj$ представляет собой звездный граф с тремя листьями, а $\epsilon uj$ представляет собой путь по трем вершинам. График фигуры можно представить в виде $\epsilon uuujuuj$

Родственные классы графов и распознавание

Пороговые графы являются частным случаем кографов , расщепляемых графов и тривиально совершенных графов . Граф является пороговым тогда и только тогда, когда он является одновременно кографом и расщепленным графом. Каждый граф, который является одновременно тривиально совершенным графом и дополнительным графом тривиально совершенного графа, является пороговым графом. Пороговые графики также являются частным случаем интервальных графов . Все эти отношения можно объяснить с точки зрения их характеристики запрещенными индуцированными подграфами. Кограф — это граф без индуцированных путей в четырех вершинах P ₄ , а пороговый граф — это граф без индуцированных P ₄ , C ₄ и 2K ₂ . C ₄ — цикл из четырех вершин, а 2K ₂ — его дополнение, т. е. два непересекающихся ребра. Это также объясняет, почему пороговые графы замкнуты при принятии дополнений; P ₄ является самодополнительным, следовательно, если граф является P ₄ -, C ₄ - и 2K ₂ -свободным, его дополнение также является свободным.

Хеггернес и Крач (2007) показали, что графики порогов можно распознать в линейном времени; препятствие (одно из P ₄ , C ₄ или 2K ₂ если график не является пороговым, будет выведено ).

См. также

Ссылки

^ Райтерман, Ян; Рёдль, Войтех; Шиняйова, Эдита; Тума, Мирослав (1 апреля 1985 г.). «Пороговые гиперграфы» . Дискретная математика . 54 (2): 193–200. дои : 10.1016/0012-365X(85)90080-9 . ISSN 0012-365X .

Хватал, Вацлав ; Хаммер, Питер Л. (1977), «Агрегация неравенств в целочисленном программировании», в Хаммере, Польша; Джонсон, Эл.; Корте, БХ; и др. (ред.), Исследования по целочисленному программированию (Proc. Worksh. Bonn, 1975) , Annals of Discrete Mathematics, vol. 1, Амстердам: Северная Голландия, стр. 145–162 .
Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы , Нью-Йорк: Academic Press . 2-е издание, Анналы дискретной математики, 57 , Elsevier, 2004.
Heggernes, Пинар ; Кратч, Дитер (2007), «Алгоритмы распознавания, сертифицирующие линейное время, и запрещенные индуцированные подграфы» (PDF) , Nordic Journal of Computing , 14 (1–2): 87–108 (2008), MR 2460558 .
Махадев, NVR; Пелед, Ури Н. (1995), Пороговые графики и смежные темы , Elsevier .

Внешние ссылки

Пороговые графы , Информационная система по классам графов и их включениям.

[1] Райтерман, Ян; Рёдль, Войтех; Шиняйова, Эдита; Тума, Мирослав (1 апреля 1985 г.). «Пороговые гиперграфы» . Дискретная математика . 54 (2): 193–200. дои : 10.1016/0012-365X(85)90080-9 . ISSN 0012-365X .

[1]