Numărul de polițiști câștigători

Graficul câștigător al polițistului este un grafic nedirecționat pe care urmăritorul (polițistul) poate câștiga jocul de urmărire-evaziune în care îl urmărește pe tâlhar, iar jucătorii se mișcă pe rând de-a lungul marginilor graficului sau stau nemișcați până când polițistul ia vârful unde tâlharul este [ 1] . Graficele poliției câștigătoare finite mai sunt numite și grafice analizabile sau grafice construite , deoarece pot fi analizate prin eliminarea unui vârf dominat din nou și din nou (un vârf a cărui vecinătate închisă este un subset al vecinătății altui vârf) sau construite prin adăugarea în mod repetat a unui astfel de vârf. Graficele cop câștigătoare pot fi recunoscute în timp polinomial printr-un algoritm lacom care generează o ordine de sortare. Această clasă include grafice de acorduri și grafice care conțin un vârf universal .

Definiție

Urmărire evazivă

Graficele câștigătoare ale polițistului (și clasa complementară de grafice, graficele câștigătoare ale tâlharului) au fost introduse de Nowakowski și Winkler [2] în contextul următorului joc de urmărire-evaziune, pe care îl atribuie lui G. Gabor și A. Kiyo. Doi jucători, un polițist și un tâlhar, sunt localizați la vârfuri inițiale diferite ale unui grafic dat. Se joacă pe rând. În timpul rândului său, jucătorul poate fie să se deplaseze la un vârf adiacent, fie să rămână pe loc. Jocul se termină și polițistul câștigă dacă polițistul își poate încheia rândul la același vârf ca tâlharul. Tâlharul câștigă dacă îl poate eschiva pe polițist la nesfârșit. Un grafic de polițist câștigător este un grafic cu proprietatea că, indiferent unde cei doi jucători încep jocul, polițistul poate câștiga întotdeauna [3] .

Dezasamblare

O vecinătate închisă N [ v ] a unui vârf v al unui graf dat este mulțimea de vârfuri constând din vârful v însuși și toate celelalte vârfuri adiacente lui v . Se spune că un vârf v este dominat de un alt vârf w dacă . Adică v și w sunt adiacente și orice vecin al lui v este vecin al lui w [4] . Nowakowski și Winkler [2] numesc un vârf care este dominat de un alt vârf un vârf ireductibil [3] .

Ordinea dezasamblarii sau ordinea eliminării vârfurilor dominate ale unui graf dat corespunde unei ordini de vârfuri astfel încât dacă vârfurile sunt îndepărtate unul câte unul în acea ordine, fiecare vârf (cu excepția ultimului) este dominat. Graficul este analizat dacă și numai dacă are o ordine de analiză [3] [4] .

Proprietăți de închidere

Familia de grafice de polițiști câștigători este închisă sub produsul puternic al graficelor . Polițistul poate câștiga în produsul strict al graficelor câștigătoare ale polițistului jucând pe unul dintre multiplicatorii produsului și apoi făcând același lucru pe ceilalți multiplicatori, rămânând pe același vârf ca tâlharul în multiplicatorii deja câștigați [3] . De exemplu, graficul de mișcare al regelui , produsul puternic al două căi , este graficul unui polițist câștigător [5] .

Nu este adevărat că un subgraf arbitrar generat de grafice de polițiști câștigătoare este câștigător. Cu toate acestea, unele subgrafe speciale generate rămân câștigătoare. Nowakowski și Winkler [2] definesc contracția unui grafic G într-unul dintre subgrafele sale generate H ca o mapare de la vârfurile lui G la vârfurile lui H care mapează fiecare vârf al lui H în sine și mapează fiecare două vârfuri adiacente ale lui G fie același vârf sau la o pereche de vârfuri adiacente în H . Apoi, după cum se spune, familia de grafice de polițiști câștigători este închisă. Pentru a câștiga la H , se poate simula un joc la G. Dacă strategia câștigătoare în G pentru polițist este să stea nemișcat sau să se deplaseze de-a lungul unui arc ale cărui ambele vârfuri se mapează la același vârf în H , polițistul stă nemișcat în H . În toate celelalte cazuri, polițistul se deplasează de-a lungul muchiei în H , care este imaginea muchiei câștigătoare în G sub contracție [3] .

Echivalența și analizabilitatea poliției

Orice grafic analizat este unul câștigător pentru polițist. Strategia câștigătoare pentru polițist este să găsească un vârf v dominat și să urmeze (prin inducție) strategia optimă pe graficul format prin ștergerea v , presupunând că tâlharul se află pe un vârf care domină vârful v . Acest lucru are ca rezultat fie că polițistul îl apucă pe tâlhar, fie că se află într-o poziție în care atacatorul se află la vârful v și polițistul este la vârful dominant, din care polițistul poate câștiga făcând o mișcare suplimentară [3] . Această strategie poate fi folosită pentru a demonstra prin inducție că într-un grafic cu n vârfuri un polițist poate fi forțat să câștige în cel mult n − 4 mișcări [6] [7] .

În schimb, orice grafic de polițist câștigător are un vârf dominat. Dacă tâlharul joacă optim cu scopul de a târî jocul și ultima poziție din joc înainte ca polițistul să apuce tâlharul de la nodul c și hoțul de la nodul r , atunci c trebuie să domine r , altfel tâlharul ar putea prelungi jocul cu măcar o mișcare. O funcție care mapează r la c și lasă restul vârfurilor pe loc este o contracție, deci graficul format prin eliminarea unui vârf dominat trebuie să fie în continuare câștigător pentru polițist. Prin inducție, obținem că orice grafic de poliție câștigător poate fi analizat [3] . Aceleași argumente arată că într-un grafic fără vârfuri dominate, tâlharul nu pierde niciodată — există întotdeauna o mutare către un vârf care nu este adiacent polițistului. Într-un grafic arbitrar care nu este câștigător pentru polițist, tâlharul poate câștiga eliminând toate vârfurile dominate și jucând pe subgraful rămas, care nu trebuie să fie gol, altfel graficul va fi analizabil.

Algoritmi de recunoaștere și o familie a tuturor comenzilor de dezasamblare

Dacă un vârf dintr-un grafic cop câștigător este dominat, atunci (când alte vârfuri dominate sunt eliminate) acesta rămâne dominat până când este el însuși îndepărtat sau rămâne vârful final al ordinii de analiză. Prin urmare, setul de ordine corecte de parsare are structura unui antimatroid , iar ordinea de parsare poate fi găsită printr-un algoritm simplu lacom care elimină vârfurile dominate pas cu pas. Procesul reușește dacă și numai dacă graficul este câștigător pentru polițist, deci oferind un algoritm pentru găsirea ordinii de analiză, această metodă oferă un algoritm pentru a verifica dacă un anumit grafic este câștigător pentru polițist.

O modalitate de a găsi următorul vârf de eliminat este să urmați următorii pași:

Într-un grafic cu n vârfuri, m muchii și degenerare d , acest proces poate fi finalizat în O ( dm ) timp [8] .


Un algoritm alternativ, dar mai complicat al lui Spinrad [9] folosește un număr, pe care el îl numește deficit , pentru fiecare pereche adiacentă de vârfuri ( x , y ) și acest număr conține numărul de vecini ai lui x care nu sunt vecini ai lui y . Algoritmul construiește și menține un set deficitar (vecini ai lui x care nu sunt vecini ai lui y ) numai atunci când deficitul este mic. Pentru a accelera calculele, algoritmul folosește arbori de decizie care clasifică nodurile în funcție de adiacența lor cu blocuri mici cu vârfuri. Algoritmul efectuează următorii pași:

Timpul de rulare al acestei proceduri este [10] .

Familii înrudite de grafice

Orice graf cordal finit este parsabil, iar orice ordine de excludere a grafului cordal (ordinea vârfurilor în care vecinii finiți ai fiecărui vârf formează o clică ) este o ordine de parsare validă. Cu toate acestea, există infinite grafuri cordale care nu sunt câștigătoare pentru polițist [11] .

Orice grafic care are un vârf universal este analizat deoarece toate celelalte vârfuri sunt dominate de vârful universal și orice ordonare a vârfurilor care plasează vârful universal pe ultimul loc este ordinea corectă de analizare. În schimb, aproape toate graficele analizate au un vârf universal în sensul că dintre toate graficele analizate cu n vârfuri, proporția graficelor cu un vârf universal tinde spre unu, în timp ce n tinde spre infinit [12] .

Graficele câștigătoare ereditar ale polițistului sunt grafice în care fiecare subgraf izometric este câștigător pentru polițist. Acest lucru nu este valabil pentru toate graficele polițiștilor câștigătoare. De exemplu, o roată cu cinci vârfuri este câștigătoare pentru polițist, dar conține un ciclu izometric de 4 care nu este câștigător, deci graficul este câștigător ereditar. Graficele cop câștigătoare ereditar sunt la fel ca și graficele punte, în care orice ciclu de lungime patru sau mai mult are o cale de tăiere, o pereche de vârfuri care sunt mai apropiate în grafic decât în ​​ciclu [13] . Graficul câștigător al unui polițist este câștigător ereditar pentru un polițist dacă și numai dacă nu are nici un ciclu de 4, nici un ciclu de 5 ca ciclu generat. Pentru un grafic de poliție câștigător ereditar, inversarea oricărei traversări pe lățimea întâi este o ordine de sortare adecvată, ceea ce implică faptul că orice vârf poate fi ales ca ultimul vârf al ordinii de sortare [14] .

Un joc similar cu mai mulți polițiști poate fi folosit pentru a determina numărul de polițiști din grafic, cel mai mic număr de polițiști necesar pentru a câștiga jocul. Graficele polițiști câștigătoare sunt exact graficele pentru care numărul de polițiști este egal cu unu [15] .

Note

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski și Winkler, 1983 , p. 235–239.
  4. ↑ 1 2 Chepoi, 1998 , p. 414–436.
  5. ↑ Despre faptul că un produs de cale strictă este un grafic câștigător, vezi articolul lui Nowakowski și Winkler ( Nowakowski, Winkler 1983 ). Pentru faptul că numărul regelui este un produs strict, vezi Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , p. 5588–5595.
  7. ↑ Gavenciak, 2010 , p. 1557–1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , p. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , p. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , p. 27–41.
  12. ↑ Bonato, Kemkes, Prałat, 2012 , p. 1652–1657
  13. ↑ Anstee, Farber, 1988 , p. 22–28.
  14. ↑ Chepoi, 1997 , p. 97–100.
  15. ↑ Aigner, Fromme, 1984 , p. 1–11.

Literatură

Link -uri