У теорії графів пороговий граф — це граф, який можна побудувати з одновершинного графу послідовним виконанням таких двох операцій:
Додавання в граф однієї ізольованої вершини Додавання однієї домінівної вершини в граф, тобто окремої вершини, пов'язаної з усіма іншими вершинами.
Наприклад, граф на малюнку є пороговим графом. Його можна побудувати з однієї вершини (вершина 1), додавши чорні вершини як ізольовані вершин і червоні вершини як домінівні вершини в порядку нумерації.
Порогові графи ввели Хватал і Гаммер. Розділ, присвячений цим графам, з'явився в книзі Голумбіка, а книга Махадева і Пеледа повністю присвячена пороговим графам.
Альтернативні визначення Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число і для кожної вершини задано вагу , таку, що для будь-яких двох вершин , є ребром тоді й лише тоді, коли .
Інше еквівалентне визначення: граф є пороговим, якщо існує дійсне число і для кожної вершини задано вагу , таку, що для будь-якої множини вершин , є незалежним тоді й лише тоді, коли
Назва «пороговий граф» прийшла з визначення: S є «порогом» для властивості мати ребро, або, еквівалентно, T є порогом для множини «бути незалежним».
Розкладання З визначення, що використовує послідовне додавання вершин, можна отримати альтернативний спосіб унікального опису порогового графу в сенсі рядка символів. завжди є першим символом рядка і означає першу вершину графу. Кожен наступний символ буде або , який означає ізольовану вершину, або , який означає додавання домінівної вершини. Наприклад, рядок подає зірку з трьома листками, а — шлях із трьох вершин. Граф на малюнку можна подати рядком .
Зв'язні класи графів і розпізнавання Порогові графи є окремим випадком кографів, розщеплюваних графів і тривіально досконалих графів. Будь-який граф, який є одночасно кографом і розщеплюваним графом, є пороговим. Будь-який граф, який є одночасно тривіально досконалим графом і доповненням тривіально досконалого графу, є пороговим графом. Порогові графи є також окремим випадком інтервальних графів. Всі ці зв'язки можна пояснити в термінах їх характеризації забороненими породженими підграфами. Кограф — це граф з відсутністю породжених шляхів із чотирма вершинами, P4, а порогові графи — це графи без породжених підграфів P4, C4 або 2K2. C4 — це цикл із чотирьох вершин, а 2K2 — його доповнення, тобто два окремих ребра. Це також пояснює, чому порогові графи замкнуті за взяттям доповнення. P4 є самодоповнюваним, а тому, якщо граф не містить породжених підграфів P4, C4 і 2K2, його доповнення теж не буде їх мати.
і ін. показали, що порогові графи можна розпізнати за лінійний час. Якщо граф не є граничним, буде вказано перешкоду у вигляді P4, C4 або 2K2.
Див. також Індиферентний граф Паралельно-послідовний граф
Примітки
Література § 50. Пороговые графы . . 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004. .
Посилання Порогові графи, інформаційна система про класи графів та їх включення.