График пороговых значений

Пример порогового графика.

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

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

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

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

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

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

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

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

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

Разложение [ править ]

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

Связанные классы графиков и распознавания [ править ]

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

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

См. Также [ править ]

• График безразличия
• Последовательно-параллельный граф

Ссылки [ править ]

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

Внешние ссылки [ править ]

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