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

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

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

Пороговые графы были введены Хваталом и Хаммером . Глава, посвящённая графам, появилась в книге Голумбика , а книга Махадева и Пеледа полностью посвящена пороговым графам.

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

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

Другое эквивалентное определение: граф является пороговым, если существует вещественное число ${\displaystyle T}$ и для каждой вершины ${\displaystyle v}$ задан вес ${\displaystyle a(v)}$ , такой, что для любого множества вершин ${\displaystyle X\subseteq 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}$

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

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

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

См. также

• Индифферентный граф
• Параллельно-последовательный граф

Примечания

Литература

• В.А.Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. — Москва: «Наука», 1990. — ISBN 5-02-013992-0 . §50. Пороговые графы
• Václav Chvátal, Peter Ladislaw Hammer. Studies in Integer Programming (Proc. Worksh. Bonn 1975) / P. L. Hammer, E. L. Johnson, B. H. Korte, G. L. Nemhauser. — Amsterdam: North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics). .
• Martin Charles Golumbic. . — New York: Academic Press, 1980. . 2nd edition, Annals of Discrete Mathematics, 57 , Elsevier, 2004.
• N. V. R. Mahadev, Uri N. Peled. Threshold Graphs and Related Topics. — Elsevier, 1995. .

Ссылки

• от 28 марта 2016 на Wayback Machine , Information System on Graph Classes and their Inclusions.