Numarul politiei

Numărul de poliție al unui grafic nedirecționat este numărul de polițiști necesari pentru a câștiga un joc de urmărire-evaziune pe grafic.

Reguli

În acest joc, un jucător controlează pozițiile unui anumit număr de ofițeri de poliție, iar celălalt jucător controlează poziția unui tâlhar. Polițiștii încearcă să-l prindă pe tâlhar trecând în poziția ocupată de tâlhar, în timp ce tâlharul încearcă să nu fie prins. Jucătorii fac următoarele acțiuni pe rând [1] :

Jocul se termină cu polițiștii câștigând dacă tâlharul se află pe același vârf cu polițistul. Dacă acest lucru nu se întâmplă niciodată, tâlharul câștigă.

Numărul de poliție al contelui este numărul minim astfel încât polițiștii să poată câștiga jocul pe . [unu]

Exemplu

Pe copac , numărul poliției este unul. Polițistul poate începe să joace de la orice vârf și fiecare mișcare se mută la singurul vârf care este mai aproape de tâlhar. Fiecare mișcare a polițistului reduce dimensiunea arborelui secundar disponibil pentru hoț, așa că jocul se va termina cu siguranță.

Într -un grafic ciclic mai lung de trei, numărul poliției este doi. Dacă există un singur polițist, tâlharul se poate deplasa într-o poziție la doi pași de polițist și păstrează întotdeauna această distanță. Astfel, tâlharul poate evita riscul de a fi prins. În cazul a doi polițiști, unul dintre ei poate sta în același vârf, iar tâlharul și al doilea polițist vor juca pe partea rămasă. Dacă al doilea polițist urmează strategia pentru copac, tâlharul va pierde cu siguranță.

Rezultate generale

Orice grafic a cărui circumferință este mai mare de patru are un număr de poliție nu mai mic decât gradul său minim [2] . Acest lucru implică faptul că există grafice cu un număr de poliție arbitrar mare.

Probleme nerezolvate la matematică : Care este cel mai mare număr de poliție posibil pentru un grafic cu vârfuri?

Henry Meinel (cunoscut pentru graficele Meinel ) a propus în 1985 ca orice graf cu vârfuri să aibă un număr de poliție . Graficele Levi ale planurilor proiective finite au circumferința 6 și gradul minim , deci dacă presupunerea este adevărată, această limită va fi cea mai bună posibilă [3] . Se știe că toate graficele au un număr de poliție subliniar [4] , dar problemele obținerii unei limite exacte sau respingerii ipotezei Meinel rămân nerezolvate [3] .

Sarcina de calcul al numărului de poliție al unui grafic dat are clasa de complexitate EXPTIME [5] și este dificilă în sensul complexității parametrizate [6] .

Clase speciale de grafice

Graficele polițiști câștigătoare sunt grafice cu numărul unu de poliție [1] .

Orice grafic plan are un număr de poliție care nu depășește trei [1] . Mai general, orice grafic are un număr de poliție care nu depășește un număr proporțional cu genul său [7] . Cu toate acestea, cea mai cunoscută limită inferioară pentru numărul de poliție în termeni de gen este aproximativ egală cu rădăcina pătrată a genului, care este departe de limita superioară atunci când genul este mare [2] .

Lățimea arborelui grafic poate fi obținută și ca rezultat al unui joc de pseudo urmărire, dar în acest joc tâlharul se poate deplasa într-o singură mișcare pe o cale arbitrar lungă, mai degrabă decât pe o margine. Această libertate suplimentară înseamnă că numărul poliției este în general mai mic decât lățimea arborelui. Mai precis, pe graficele cu lățimea arborelui , numărul poliției nu depășește [8] .

Link -uri

  1. 1 2 3 4 Aigner M. , Fromme M. Un joc de polițiști și tâlhari // Matematică aplicată discretă . - 1984. - T. 8 , nr. 1 . — S. 1–11 . - doi : 10.1016/0166-218X(84)90073-8 .
  2. 1 2 Bojan Mohar. Note despre jocul de polițiști și tâlhari pe grafice. - 2017. - . - arXiv : 1710.11281 .
  3. 1 2 William Baird, Anthony Bonato. Conjectura lui Meyniel cu privire la numărul polițistului: un sondaj // Journal of Combinatorics. - 2012. - Vol. 3 , nr. 2 . — S. 225–238 . - doi : 10.4310/JOC.2012.v3.n2.a6 . - arXiv : 1308.3385 .
  4. Peter Frankl. Polițiști și tâlhari în grafice cu circumferință mare și grafice Cayley  // Matematică aplicată discretă . - 1987. - T. 17 , nr. 3 . — S. 301–305 . - doi : 10.1016/0166-218X(87)90033-3 .
  5. William B. Kinnersley. Polițiști și tâlhari este EXPTIME-complet // Journal of Combinatorial Theory. - 2015. - T. 111 . — S. 201–220 . - doi : 10.1016/j.jctb.2014.11.002 . - arXiv : 1309,5405 .
  6. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl. Despre jocul polițiștilor și tâlharilor // A cincea conferință internațională IFIP privind știința teoretică a computerelor—TCS 2008. New York: Springer, 2008. Vol. 273. P. 171–185. - (Procesul IFIP Int. Fed. Inf.). - doi : 10.1007/978-0-387-09680-3_12 .
  7. Bernd SW Schroeder. Copnumărul unui grafic este mărginit de // Perspective categoriale (Kent, OH, 1998). - Boston: Birkhäuser, 2001. - S. 243-263. - (Trends Math.).
  8. Nancy Elaine Blanche Clarke. Polițiști și tâlhari constrânși . - Canada: Universitatea Dalhousie, 2002. - (teză de doctorat).