У теорії графів пороговий граф — це граф, який можна побудувати з одновершинного графу послідовним виконанням таких двох операцій:
- Додавання в граф однієї ізольованої вершини
- Додавання однієї домінівної вершини в граф, тобто окремої вершини, пов'язаної з усіма іншими вершинами.
Наприклад, граф на малюнку є пороговим графом. Його можна побудувати з однієї вершини (вершина 1), додавши чорні вершини як ізольовані вершин і червоні вершини як домінівні вершини в порядку нумерації.
Порогові графи ввели Хватал і Гаммер. Розділ, присвячений цим графам, з'явився в книзі Голумбіка, а книга Махадева і Пеледа повністю присвячена пороговим графам.
Альтернативні визначення
Еквівалентне визначення таке: граф є пороговим, якщо існує дійсне число і для кожної вершини задано вагу , таку, що для будь-яких двох вершин , є ребром тоді й лише тоді, коли .
Інше еквівалентне визначення: граф є пороговим, якщо існує дійсне число і для кожної вершини задано вагу , таку, що для будь-якої множини вершин , є незалежним тоді й лише тоді, коли
Назва «пороговий граф» прийшла з визначення: S є «порогом» для властивості мати ребро, або, еквівалентно, T є порогом для множини «бути незалежним».
Розкладання
З визначення, що використовує послідовне додавання вершин, можна отримати альтернативний спосіб унікального опису порогового графу в сенсі рядка символів. завжди є першим символом рядка і означає першу вершину графу. Кожен наступний символ буде або , який означає ізольовану вершину, або , який означає додавання домінівної вершини. Наприклад, рядок подає зірку з трьома листками, а — шлях із трьох вершин. Граф на малюнку можна подати рядком .
Зв'язні класи графів і розпізнавання
Порогові графи є окремим випадком кографів, розщеплюваних графів і тривіально досконалих графів. Будь-який граф, який є одночасно кографом і розщеплюваним графом, є пороговим. Будь-який граф, який є одночасно тривіально досконалим графом і доповненням тривіально досконалого графу, є пороговим графом. Порогові графи є також окремим випадком інтервальних графів. Всі ці зв'язки можна пояснити в термінах їх характеризації забороненими породженими підграфами. Кограф — це граф з відсутністю породжених шляхів із чотирма вершинами, P4, а порогові графи — це графи без породжених підграфів P4, C4 або 2K2. C4 — це цикл із чотирьох вершин, а 2K2 — його доповнення, тобто два окремих ребра. Це також пояснює, чому порогові графи замкнуті за взяттям доповнення. P4 є самодоповнюваним, а тому, якщо граф не містить породжених підграфів P4, C4 і 2K2, його доповнення теж не буде їх мати.
[en] і ін. показали, що порогові графи можна розпізнати за лінійний час. Якщо граф не є граничним, буде вказано перешкоду у вигляді P4, C4 або 2K2.
Див. також
Примітки
- Chvátal, Hammer, 1977.
- Golumbic, 1980.
- Mahadev, Peled, 1995.
- Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 227, Следствие 50.11.
- Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 224, Следствие 50.3.
- Емеличев, Мельников, Сарванов, Тышкевич, 1990, с. 227, Следствие 50.12.
Література
- В.А.Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. Лекции по теории графов. — М. : «Наука», 1990. — . § 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..
Посилання
- Порогові графи, інформаційна система про класи графів та їх включення.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv porogovij graf ce graf yakij mozhna pobuduvati z odnovershinnogo grafu poslidovnim vikonannyam takih dvoh operacij Dodavannya v graf odniyeyi izolovanoyi vershini Dodavannya odniyeyi dominivnoyi vershini v graf tobto okremoyi vershini pov yazanoyi z usima inshimi vershinami Priklad porogovogo grafu Napriklad graf na malyunku ye porogovim grafom Jogo mozhna pobuduvati z odniyeyi vershini vershina 1 dodavshi chorni vershini yak izolovani vershin i chervoni vershini yak dominivni vershini v poryadku numeraciyi Porogovi grafi vveli Hvatal i Gammer Rozdil prisvyachenij cim grafam z yavivsya v knizi Golumbika a kniga Mahadeva i Peleda povnistyu prisvyachena porogovim grafam Alternativni viznachennyaEkvivalentne viznachennya take graf ye porogovim yaksho isnuye dijsne chislo S displaystyle S i dlya kozhnoyi vershini v displaystyle v zadano vagu w v displaystyle w v taku sho dlya bud yakih dvoh vershin v u displaystyle v u uv displaystyle uv ye rebrom todi j lishe todi koli w u w v gt S displaystyle w u w v gt S Inshe ekvivalentne viznachennya graf ye porogovim yaksho isnuye dijsne chislo T displaystyle T i dlya kozhnoyi vershini v displaystyle v zadano vagu a v displaystyle a v taku sho dlya bud yakoyi mnozhini vershin X V displaystyle X subseteq V X displaystyle X ye nezalezhnim todi j lishe todi koli v Xa v T displaystyle sum v in X a v leq T Nazva porogovij graf prijshla z viznachennya S ye porogom dlya vlastivosti mati rebro abo ekvivalentno T ye porogom dlya mnozhini buti nezalezhnim RozkladannyaZ viznachennya sho vikoristovuye poslidovne dodavannya vershin mozhna otrimati alternativnij sposib unikalnogo opisu porogovogo grafu v sensi ryadka simvoliv ϵ displaystyle epsilon zavzhdi ye pershim simvolom ryadka i oznachaye pershu vershinu grafu Kozhen nastupnij simvol bude abo u displaystyle u yakij oznachaye izolovanu vershinu abo j displaystyle j yakij oznachaye dodavannya dominivnoyi vershini Napriklad ryadok ϵuuj displaystyle epsilon uuj podaye zirku z troma listkami a ϵuj displaystyle epsilon uj shlyah iz troh vershin Graf na malyunku mozhna podati ryadkom ϵuuujuuj displaystyle epsilon uuujuuj Zv yazni klasi grafiv i rozpiznavannyaPorogovi grafi ye okremim vipadkom kografiv rozsheplyuvanih grafiv i trivialno doskonalih grafiv Bud yakij graf yakij ye odnochasno kografom i rozsheplyuvanim grafom ye porogovim Bud yakij graf yakij ye odnochasno trivialno doskonalim grafom i dopovnennyam trivialno doskonalogo grafu ye porogovim grafom Porogovi grafi ye takozh okremim vipadkom intervalnih grafiv Vsi ci zv yazki mozhna poyasniti v terminah yih harakterizaciyi zaboronenimi porodzhenimi pidgrafami Kograf ce graf z vidsutnistyu porodzhenih shlyahiv iz chotirma vershinami P4 a porogovi grafi ce grafi bez porodzhenih pidgrafiv P4 C4 abo 2K2 C4 ce cikl iz chotiroh vershin a 2K2 jogo dopovnennya tobto dva okremih rebra Ce takozh poyasnyuye chomu porogovi grafi zamknuti za vzyattyam dopovnennya P4 ye samodopovnyuvanim a tomu yaksho graf ne mistit porodzhenih pidgrafiv P4 C4 i 2K2 jogo dopovnennya tezh ne bude yih mati en i in pokazali sho porogovi grafi mozhna rozpiznati za linijnij chas Yaksho graf ne ye granichnim bude vkazano pereshkodu u viglyadi P4 C4 abo 2K2 Div takozhIndiferentnij graf Paralelno poslidovnij grafPrimitkiChvatal Hammer 1977 Golumbic 1980 Mahadev Peled 1995 Emelichev Melnikov Sarvanov Tyshkevich 1990 s 227 Sledstvie 50 11 Emelichev Melnikov Sarvanov Tyshkevich 1990 s 224 Sledstvie 50 3 Emelichev Melnikov Sarvanov Tyshkevich 1990 s 227 Sledstvie 50 12 LiteraturaV A Emelichev O I Melnikov V I Sarvanov R I Tyshkevich Lekcii po teorii grafov M Nauka 1990 ISBN 5 02 013992 0 50 Porogovye grafy Vaclav Chvatal Peter Ladislaw Hammer Studies in Integer Programming Proc Worksh Bonn 1975 P L Hammer E L Johnson B H Korte G L Nemhauser Amsterdam North Holland 1977 T 1 S 145 162 Annals of Discrete Mathematics Martin Charles Golumbic Algorithmic Graph Theory and Perfect Graphs Nyu Jork 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 PosilannyaPorogovi grafi informacijna sistema pro klasi grafiv ta yih vklyuchennya