Graficul pragului

În teoria grafurilor, un grafic de prag este un grafic care poate fi construit dintr-un grafic cu un singur vârf prin efectuarea secvenţială a următoarelor două operaţii:

Adăugarea unui vârf izolat la grafic
Adăugarea unui vârf dominant la grafic, de ex. un singur vârf conectat la toate celelalte vârfuri.

De exemplu, graficul din figură este un grafic de prag. Poate fi construit dintr-un singur vârf (vârful 1) și adăugând vârfuri negre ca vârfuri izolate și vârfuri roșii ca vârfuri dominante în ordine numerică.

Graficele de prag au fost introduse de Chvatal și Hammer [1] . Capitolul despre grafice a apărut în cartea lui Golumbik [2] , în timp ce cartea lui Mahadev și Peled [3] este în întregime dedicată graficelor de prag.

Definiții alternative

O definiție echivalentă este următoarea: un grafic este un prag dacă există un număr real și pentru fiecare vârf este dată o pondere astfel încât pentru oricare două vârfuri , este o muchie dacă și numai dacă . $S$ $v$ $w(v)$ $v,u$ $UV$ $w(u)+w(v)>S$

O altă definiție echivalentă: un grafic este prag dacă există un număr real și pentru fiecare vârf este dată o pondere astfel încât pentru orice set de vârfuri , este independent dacă și numai dacă $T$ $v$ $a(v)$ $X\subseteq V$ $X$ $\sum _{v\in X}a(v)\leq T.$

Denumirea „graf de prag” provine din definiția: S este un „prag” pentru ca proprietatea să aibă o muchie sau, echivalent, T este un prag pentru ca o mulțime să fie independentă.

Descompunere

Din definiția folosind adăugarea secvențială a vârfurilor, se poate obține o modalitate alternativă de a descrie în mod unic graficul de prag în sensul unui șir de caractere. servește întotdeauna ca prim caracter al șirului și reprezintă primul vârf al graficului. Fiecare caracter ulterior va fi fie , ceea ce înseamnă un vârf izolat, fie , ceea ce înseamnă adăugarea unui vârf dominant. De exemplu, un șir reprezintă o stea cu trei frunze, dar reprezintă o cale de trei vârfuri. Graficul din figură poate fi reprezentat prin linie $\epsilon$ $u$ $j$ $\epsilon uuj$ $\epsilon uj$ $\epsilon uuujuuj$

Clase conectate de grafice și recunoaștere

Graficele de prag sunt un caz special de cografe , grafice divizate și grafice trivial perfecte [4] . Orice grafic care este atât un cograf, cât și un grafic divizat este un grafic de prag. Orice grafic care este atât un grafic trivial perfect, cât și complementul unui grafic trivial perfect este un grafic de prag. Graficele de prag sunt, de asemenea, un caz special de grafice de intervale . Toate aceste conexiuni pot fi explicate în ceea ce privește caracterizarea lor prin subgrafe generate interzise. Un cograf este un grafic fără căi generate cu patru vârfuri, P 4 , iar graficele de prag sunt grafice ale bazelor subgrafelor generate P 4 , C 4 sau 2K 2 [5] . C 4 este un ciclu de patru vârfuri, iar 2K 2 este complementul său, adică două muchii separate. Acest lucru explică, de asemenea, de ce graficele de prag sunt închise de complement. P 4 este autocomplementar și, prin urmare, dacă graficul nu conține subgrafele generate P 4 , C 4 și 2K 2 , nici complementul său nu le va avea [6] .

Heggernes și colab. au arătat că graficele de prag pot fi recunoscute în timp liniar. Dacă graficul nu este un prag, va fi indicat un obstacol sub forma P4 , C4 sau 2K2 .

Vezi și

Note

↑ Chvatal, Hammer, 1977 .
↑ Golumbic, 1980 .
↑ Mahadev, Peled, 1995 .
↑ Emelichev, Melnikov, Sarvanov, Tyshkevici, 1990 , p. 227, corolarul 50.11.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevici, 1990 , p. 224, corolarul 50.3.
↑ Emelichev, Melnikov, Sarvanov, Tyshkevici, 1990 , p. 227, corolarul 50.12.

Literatură

V.A. Emelichev, O.I. Melnikov, V.I. Sarvanov, R.I. Tyshkevici. Prelegeri despre teoria grafurilor. - Moscova: „Nauka”, 1990. - ISBN 5-02-013992-0 . §cincizeci. Grafice de prag
Václav Chvátal, Peter Ladislaw Hammer. Studii de programare cu numere întregi (Proc. Worksh. Bonn 1975) / PL Hammer, EL Johnson, BH Korte, GL Nemhauser. - Amsterdam: Olanda de Nord, 1977. - V. 1. - S. 145-162. — (Analele matematicii discrete). .
Martin Charles Golumbic. Teoria graficelor algoritmice și graficele perfecte. - New York: Academic Press, 1980. . Ediția a II-a, Analele matematicii discrete, 57 , Elsevier, 2004.
NVR Mahadev, Uri N. Peled. Grafice de prag și subiecte conexe. — Elsevier, 1995. .

Link -uri

Grafice de prag Arhivat la 28 martie 2016 la Wayback Machine , Sistemul de informații despre clasele de grafice și incluziunile lor.