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

поняття в теорії графів

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

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

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

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

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

Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число   і для кожної вершини   задано вагу  , таку, що для будь-яких двох вершин  ,   є ребром тоді й лише тоді, коли   .

Інше еквівалентне визначення: граф є пороговим, якщо існує дійсне число   і для кожної вершини   задано вагу  , таку, що для будь-якої множини вершин  ,   є незалежним тоді й лише тоді, коли  

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

Розкладання ред.

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

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

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

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

Див. також ред.

Примітки ред.

Література ред.

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

Посилання ред.