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

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

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

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

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

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

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

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

Назва «пороговий граф» прийшла з визначення: S є «порогом» для властивості мати ребро, або, еквівалентно, T є порогом для множини «бути незалежним».

Розкладання

З визначення, що використовує послідовне додавання вершин, можна отримати альтернативний спосіб унікального опису порогового графу в сенсі рядка символів. $ϵ$ завжди є першим символом рядка і означає першу вершину графу. Кожен наступний символ буде або $u$, який означає ізольовану вершину, або $j$, який означає додавання домінівної вершини. Наприклад, рядок $ϵuuj$ подає зірку з трьома листками, а $ϵuj$ — шлях із трьох вершин. Граф на малюнку можна подати рядком $ϵuuujuuj$.

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

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

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

Див. також

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

Література

• Шаблон:Книга § 50. Пороговые графы
• Шаблон:Книга.
• Шаблон:Книга. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Шаблон:Книга.

Посилання

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