Grafic trivial de perfect
Un graf trivial perfect este un graf cu proprietatea că în fiecare dintre subgrafele sale generate mărimea mulțimii independente maxime (în mărime) este egală cu numărul de clicuri maxime [1] [2] . Graficele trivial perfecte au fost studiate pentru prima dată de Volk [3] [4] , dar numele a fost dat de Golumbik [2] . Golumbik a scris că „acest nume a fost ales având în vedere trivialitatea de a demonstra că astfel de grafice sunt perfecte ”. Graficele trivial perfecte sunt cunoscute și sub denumirea de grafice de comparabilitate a arborilor [3] [4] , grafice de comparabilitate a arborilor [5] și grafice de cvasiprag[6] .
Descrieri echivalente
Graficele trivial perfecte au câteva alte descrieri echivalente:
- Sunt grafice de comparabilitate ale arborilor din teoria ordinii . Adică, fie T o ordine parțială astfel încât pentru orice t ∈ T mulțimea { s ∈ T : s < t } este bine ordonată cu relația < și T are cel mai mic element r . Atunci graficul de comparabilitate de ordinul T este trivial perfect și orice grafic trivial perfect poate fi format în acest fel [7] [8] .
- Sunt grafice care nu conțin o cale P 4 sau un ciclu C 4 ca subgrafe generate [7] [9] [10]
- Ele sunt grafice în care fiecare subgraf generat conectat conține un vârf universal [11] .
- Sunt grafice care pot fi considerate grafice cu intervale ale unui set de intervale imbricate . Un set de goluri are proprietatea de imbricare dacă pentru oricare două goluri din mulțime fie nu se intersectează, fie unul dintre ele este conținut în celălalt [12] .
- Sunt grafuri care sunt atât grafuri cordale, cât și cografe [13] [14] . Aceasta rezultă din descrierea graficelor de acorduri ca grafice fără cicluri generate cu lungimea de patru sau mai mult și a cografelor ca grafice fără căi generate cu patru vârfuri ( P4 ).
- Sunt grafice care sunt atât cografe, cât și grafice cu intervale [13] [14] .
- Sunt grafuri care pot fi formate pornind de la grafuri cu un singur vârf, folosind două operații - o unire disjunctă a două grafuri trivial perfecte mai mici și adăugarea unui nou vârf adiacent tuturor vârfurilor grafului trivial perfect mai mic [6] [15] . Aceste operațiuni corespund formării unei păduri noi prin unirea disjunctă a două păduri mai mici și formării unui arbore prin unirea unei noi rădăcini la rădăcinile tuturor copacilor din pădure.
- Sunt grafice în care, pentru orice muchie uv , sunt imbricate vecinătățile vârfurilor u și v (inclusiv u și v înșiși ) — o vecinătate trebuie să fie o vecinătate a celeilalte [14] .
- Sunt grafice de permutări definite din permutări sortate pe stiva [16] .
- Sunt grafice cu proprietatea că în fiecare dintre subgrafele sale generate , numărul de acoperire a clicurilor este egal cu numărul de clicuri maxime [17] .
- Sunt grafice cu proprietatea că în fiecare dintre subgrafele sale generate , numărul clicei este egal cu pseudonumărul Grandi [17] .
- Sunt grafice cu proprietatea că numărul cromatic al fiecăruia dintre subgrafele sale generate este egal cu pseudo-numărul Grandi [17] .
Clase de grafice înrudite
Din descrierile echivalente ale grafurilor trivial perfecte rezultă că orice graf trivial perfect este, de asemenea, un graf cograf , acord , ptolemeic , interval și graf perfect .
Graficele de prag sunt exact acele grafice care sunt ambele trivial perfecte și sunt complementul unor grafice trivially perfecte (cographe trivially perfecte) [18] [19] .
Morile sunt trivial de perfecte.
Recunoaștere
Chu [20] descrie un algoritm de timp liniar simplu pentru recunoașterea graficelor trivial perfecte pe baza căutării lexicografice pe lățimea întâi . Când algoritmul LexBFS elimină v din primul set din coadă, algoritmul verifică dacă toți vecinii rămași ai lui v sunt în același set. Dacă nu, unul dintre subgrafele interzise generate poate fi construit din v . Dacă verificarea reușește pentru toate v , atunci graficul este trivial perfect. Algoritmul poate fi modificat pentru a testa în timp liniar dacă un grafic este complementul unui grafic trivial perfect.
Determinarea dacă un graf general după eliminarea k muchii devine un graf trivial perfect este o problemă NP-complet [21] , rezolvabilă cu parametri fix [22] , și poate fi rezolvată în timp O(2,45 k (m+n) ) [ 23] .
Note
- ↑ Brandstädt, Le, Spinrad, 1999 , p. 34 definiție 2.6.2.
- ↑ 1 2 Golumbic, 1978 .
- ↑ 12 Wolk , 1962 .
- ↑ 12 Wolk , 1965 .
- ^ Donnelly, Isaac, 1999 .
- ↑ 12 Yan , Chen, Chang, 1996 .
- ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 99 Teorema 6.6.1.
- ↑ Golumbic, 1978 , p. corolarul 4.
- ↑ Golumbic, 1978 , p. teorema 2.
- ↑ Wolk 1962 a demonstrat acest lucru pentru graficele de comparabilitate a pădurilor înrădăcinate .
- ↑ Brandstädt, Le, Spinrad, 1999 , p. 51.
- ↑ 1 2 Brandstädt, Le, Spinrad, 1999 , p. 248.
- ↑ 1 2 3 Yan, Chen, Chang, 1996 , p. teorema 3.
- ↑ Gurski, 2006 .
- ↑ Rotem, 1981 .
- ↑ Brandstädt, Le, Spinrad, 1999 , p. 100 Teorema 6.6.3.
- ↑ Golumbic, 1978 , p. corolarul 5.
- ↑ Chu, 2008 .
- ↑ Nastos, Gao, 2010 .
Literatură
- Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Clasele grafice: un sondaj. - Monografii SIAM despre matematică discretă și aplicații, 1999. - ISBN 0-89871-432-X .
- Cai L. Tratabilitatea cu parametri fixe a problemelor de modificare a graficului pentru proprietăți ereditare // Litere de procesare a informațiilor . - 1996. - T. 58 , nr. 4 . — S. 171–176 . - doi : 10.1016/0020-0190(96)00050-6 .
- Frank Pok Man Chu. Un algoritm bazat pe LBFS de certificare a timpului liniar simplu pentru recunoașterea graficelor trivial perfecte și a complementelor lor // Litere de procesare a informațiilor . - 2008. - T. 107 , nr. 1 . — pp. 7–12 . - doi : 10.1016/j.ipl.2007.12.009 .
- Sam Donnelly, Garth Isaac. Puterile hamiltoniene în grafice de comparabilitate de prag și arborescent // Matematică discretă . - 1999. - T. 202 , nr. 1-3 . — p. 33–44 . - doi : 10.1016/S0012-365X(98)00346-X .
- Martin Charles Golumbic. Grafice trivial de perfecte // Matematică discretă . - 1978. - T. 24 , nr. 1 . — S. 105–107 . - doi : 10.1016/0012-365X(78)90178-4 .
- Frank Gurski. Caracterizări pentru co-grafe definite prin operații cu lățime NLC sau clic pe lățime restricționată // Matematică discretă . - 2006. - T. 306 , nr. 2 . — S. 271–277 . - doi : 10.1016/j.disc.2005.11.014 .
- James Nastos, Yong Gao. O nouă strategie de ramificare pentru problemele de modificare a graficelor parametrizate // Note de curs în informatică. - 2010. - T. 6509 . — S. 332–346 .
- Rotem D. Stack sortable permutations // Matematică discretă . - 1981. - T. 33 , nr. 2 . — S. 185–196 . - doi : 10.1016/0012-365X(81)90165-5 .
- Rubio-Montiel C. O nouă caracterizare a graficelor trivial perfecte // Electronic Journal of Graph Theory and Applications. - 2015. - Vol. 3 , nr. 1 . — S. 22–26 . - doi : 10.5614/ejgta.2015.3.1.3 .
- Roded Sharan. Probleme de modificare a graficelor și aplicațiile lor în cercetarea genomică // Teză de doctorat, Universitatea din Tel Aviv. — 2002.
- Wolk ES Graficul de comparabilitate al unui arbore // Proceedings of the American Mathematical Society . - 1962. - T. 13 , nr. 5 . — S. 789–795 . - doi : 10.1090/S0002-9939-1962-0172273-0 .
- Wolk ES O notă despre graficul de comparabilitate al unui arbore // Proceedings of the American Mathematical Society . - 1965. - T. 16 . — S. 17–20 . - doi : 10.1090/S0002-9939-1965-0172274-5 .
- Jing-Ho Yan, Jer-Jeong Chen, Gerard J. Chang. Grafice cvasi-prag // Matematică aplicată discretă . - 1996. - T. 69 , nr. 3 . — S. 247–255 . - doi : 10.1016/0166-218X(96)00094-7 .
Link -uri