График порога

Граф, образованный путем добавления изолированных или универсальных вершин

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

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

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

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

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

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

Эквивалентное определение следующее: граф является пороговым графом, если существуют действительное число и для каждой вершины действительный вес вершины, такие, что для любых двух вершин является ребром тогда и только тогда, когда . ${\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 ₂ , то его дополнение также является самодополнительным.

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

Смотрите также

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

Ссылки

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

• Chvátal, Václav ; Hammer, Peter L. (1977), "Агрегация неравенств в целочисленном программировании", в Hammer, PL; Johnson, EL; Korte, BH; et al. (ред.), Исследования по целочисленному программированию (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, т. 1, Амстердам: North-Holland, стр. 145–162.
• Golumbic, Martin Charles (1980), Алгоритмическая теория графов и совершенные графы , Нью-Йорк: Academic Press. 2-е издание, Анналы дискретной математики, 57 , Elsevier, 2004.
• Хеггернес, Пинар ; Кратч, Дитер (2007), «Линейно-временные алгоритмы сертификационного распознавания и запрещенные индуцированные подграфы» (PDF) , Nordic Journal of Computing , 14 (1–2): 87–108 (2008), MR  2460558.
• Махадев, НВР; Пелед, Ури Н. (1995), Пороговые графики и смежные темы , Elsevier.

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

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