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

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

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

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

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

Графики порогов были впервые введены Chvátal & Hammer (1977). Глава о пороговых графиках появляется в Голумбик (1980), и книга Махадев и Пелед (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 Xsubseteq V}$ , ${displaystyle X}$ является независимый если и только если ${displaystyle sum _ {vin X} a (v) leq T.}$

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

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

Разложение

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

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

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

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

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

внешняя ссылка

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