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

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

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

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

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

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

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

Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число ${\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}$.

Зв'язні класи графів і розпізнавання

Порогові графи є окремим випадком кографів, розщеплюваних графів і тривіально досконалих графів[4]. Будь-який граф, який є одночасно кографом і розщеплюваним графом, є пороговим. Будь-який граф, який є одночасно тривіально досконалим графом і доповненням тривіально досконалого графу, є пороговим графом. Порогові графи є також окремим випадком інтервальних графів. Всі ці зв'язки можна пояснити в термінах їх характеризації забороненими породженими підграфами. Кограф — це граф з відсутністю породжених шляхів із чотирма вершинами, P_4, а порогові графи — це графи без породжених підграфів P_4, C₄ або 2K₂[5]. C₄ — це цикл із чотирьох вершин, а 2K₂ — його доповнення, тобто два окремих ребра. Це також пояснює, чому порогові графи замкнуті за взяттям доповнення. P₄ є самодоповнюваним, а тому, якщо граф не містить породжених підграфів P_4, C₄ і 2K_2, його доповнення теж не буде їх мати[6].

Геґґернес^[en] і ін. показали, що порогові графи можна розпізнати за лінійний час. Якщо граф не є граничним, буде вказано перешкоду у вигляді P_4, C₄ або 2K₂.

Див. також

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

Примітки

1. Chvátal, Hammer, 1977.
2. Golumbic, 1980.
3. Mahadev, Peled, 1995.
4. Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 227, Следствие 50.11.
5. Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 224, Следствие 50.3.
6. Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 227, Следствие 50.12.

Література

• В.А.Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. — М. : «Наука», 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..

Посилання

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