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

Приклад порогового графу

У теорії графів пороговий граф — це граф, який можна побудувати з одновершинного графу послідовним виконанням таких двох операцій:

1. Додавання в граф однієї ізольованої вершини
2. Додавання однієї домінівної вершини в граф, тобто окремої вершини, пов'язаної з усіма іншими вершинами.

Наприклад, граф на малюнку є пороговим графом. Його можна побудувати з однієї вершини (вершина 1), додавши чорні вершини як ізольовані вершин і червоні вершини як домінівні вершини в порядку нумерації.

Порогові графи ввели Хватал і Гаммер. Розділ, присвячений цим графам, з'явився в книзі Голумбіка, а книга Махадева і Пеледа повністю присвячена пороговим графам.

Альтернативні визначення

Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число $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_4, а порогові графи — це графи без породжених підграфів P_4, C₄ або 2K₂. C₄ — це цикл із чотирьох вершин, а 2K₂ — його доповнення, тобто два окремих ребра. Це також пояснює, чому порогові графи замкнуті за взяттям доповнення. P₄ є самодоповнюваним, а тому, якщо граф не містить породжених підграфів P_4, C₄ і 2K_2, його доповнення теж не буде їх мати.

Геґґернес і ін. показали, що порогові графи можна розпізнати за лінійний час. Якщо граф не є граничним, буде вказано перешкоду у вигляді P_4, 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. — Амстердам : North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics).
• Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Нью-Йорк : 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..

Посилання

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