Поліційне число неорієнтованого графа — це кількість поліціянтів, необхідних для виграшу в деякій грі переслідування-ухилення на графі.
Правила
У цій грі один гравець керує положенням заданої кількості поліціянтів, а інший гравець керує положенням грабіжника. Поліціянти намагаються схопити грабіжника, пересуваючись у позицію, яку займає грабіжник, тоді як грабіжник прагне не бути схопленим. Гравці почергово роблять такі дії:
- Першим ходом гравець, який керує поліціянтами, поміщає їх на вершини графа (дозволено поміщати в одну вершину більше одного поліціянта).
- Потім гравець, який керує грабіжником, поміщає його у вершину графа.
- Кожним наступним ходом гравець, який керує поліціянтами, вибирає (можливо порожню) їх підмножину і пересуває кожного з них на суміжні вершини. Решта поліціянтів (якщо такі є) залишаються на місці.
- Грабіжник, коли настає його хід, може перейти на суміжну вершину або залишитися на місці.
Гра закінчується виграшем поліціянтів, якщо грабіжник опиняється на одній вершині з поліціянтом. Якщо таке ніколи не відбувається, виграє грабіжник.
Поліцейське число графа — мінімальне число , таке що поліціянтів можуть виграти гру на .
Приклад
На дереві поліційне число дорівнює одиниці. Поліціянт може почати грати з будь-якої вершини і кожним ходом пересувтися в єдину вершину, ближчу до грабіжника. Кожен хід поліціянта зменшує розмір піддерева, доступного грабіжнику, тому гра обов'язково завершиться.
У циклічному графі довжиною більше трьох поліційне число дорівнює двом. Якщо є один поліціянт, грабіжник може перейти в позицію за два кроки від поліціянта і завжди зберігати цю відстань. Таким чином, грабіжник уникне ризику бути схопленим. У випадку двох поліціянтів один з них може стояти в одній і тій самій вершині, а грабіжник і другий поліціянт гратимуть на частині, що залишилася. Якщо другий поліціянт дотримується стратегії для дерева, грабіжник, безумовно, програє.
Загальні результати
Будь-який граф, обхват якого більше 4, має поліційне число, не менше від його найменшого степеня. Звідси випливає, що існують графи з доволі великим поліційним числом.
Нерозв'язана проблема математики: Яким є найбільше можливе поліційне число графа з n вершинами? (більше нерозв'язаних проблем математики) |
1985 року (відомий за графами Мейнеля) припустив, що будь-який граф із вершинами має поліційне число . Графи Леві скінченних проєктивних площин мають обхват 6 та мінімальний степінь , так що, якщо гіпотеза істинна, ця межа буде найкращою з можливих. Відомо, що всі графи мають сублінійне поліційне число, але задачі отримання точної межі або спростування гіпотези Мейнеля залишаються нерозв'язаними.
Задача обчислення поліційного числа заданого графа має клас складності EXPTIME і складна в сенсі [en].
Спеціальні класи графів
— це графи з поліційним числом 1.
Поліційне число будь-якого планарного графа не перевищує 3. Загальніше, будь-який граф має поліційне число, що не перевищує числа, пропорційного його (роду). Однак найкраща відома нижня межа для поліційного числа в термінах роду приблизно дорівнює квадратному кореню з роду, що далеко від верхньої межі, коли рід великий.
Деревну ширину графа можна отримати як результат гри псевдопереслідування, але в цій грі грабіжник може рухатися за один хід уздовж довільно довгого шляху, а не на одне ребро. Ця зайва свобода означає, що поліційне число в загальному випадку менше від деревної ширини. Конкретніше, на графах із деревною шириною поліційне число не перевищує .
Посилання
- [ru], Fromme M. A game of cops and robbers // . — 1984. — Т. 8, вип. 1. — С. 1–11. — DOI:10.1016/0166-218X(84)90073-8.
- Bojan Mohar. Notes on Cops and Robber game on graphs. — 2017. — arXiv:1710.11281. — Bibcode: 2017arXiv171011281M.
- William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey // Journal of Combinatorics. — 2012. — Т. 3, вип. 2. — С. 225–238. — arXiv:1308.3385. — DOI:10.4310/JOC.2012.v3.n2.a6.
- Péter Frankl. Cops and robbers in graphs with large girth and Cayley graphs // . — 1987. — Т. 17, вип. 3. — С. 301–305. — DOI:10.1016/0166-218X(87)90033-3.
- William B. Kinnersley. Cops and robbers is EXPTIME-complete // Journal of Combinatorial Theory. — 2015. — Т. 111. — С. 201–220. — arXiv:1309.5405. — DOI:10.1016/j.jctb.2014.11.002.
- Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl. On tractability of cops and robbers game // Fifth IFIP International Conference on Theoretical Computer Science—TCS 2008. — New York : Springer, 2008. — Т. 273. — С. 171–185. — (IFIP Int. Fed. Inf. Process.). — DOI:10.1007/978-0-387-09680-3_12.
- Bernd S. W. Schroeder. The copnumber of a graph is bounded by // Categorical perspectives (Kent, OH, 1998). — Boston : Birkhäuser, 2001. — С. 243–263. — (Trends Math.).
- Nancy Elaine Blanche Clarke. Constrained cops and robber. — Canada : Dalhousie University, 2002. — (Ph.D. thesis).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Policijne chislo neoriyentovanogo grafa ce kilkist policiyantiv neobhidnih dlya vigrashu v deyakij gri peresliduvannya uhilennya na grafi PravilaU cij gri odin gravec keruye polozhennyam zadanoyi kilkosti policiyantiv a inshij gravec keruye polozhennyam grabizhnika Policiyanti namagayutsya shopiti grabizhnika peresuvayuchis u poziciyu yaku zajmaye grabizhnik todi yak grabizhnik pragne ne buti shoplenim Gravci pochergovo roblyat taki diyi Pershim hodom gravec yakij keruye policiyantami pomishaye yih na vershini grafa dozvoleno pomishati v odnu vershinu bilshe odnogo policiyanta Potim gravec yakij keruye grabizhnikom pomishaye jogo u vershinu grafa Kozhnim nastupnim hodom gravec yakij keruye policiyantami vibiraye mozhlivo porozhnyu yih pidmnozhinu i peresuvaye kozhnogo z nih na sumizhni vershini Reshta policiyantiv yaksho taki ye zalishayutsya na misci Grabizhnik koli nastaye jogo hid mozhe perejti na sumizhnu vershinu abo zalishitisya na misci Gra zakinchuyetsya vigrashem policiyantiv yaksho grabizhnik opinyayetsya na odnij vershini z policiyantom Yaksho take nikoli ne vidbuvayetsya vigraye grabizhnik Policejske chislo grafa G displaystyle G minimalne chislo k displaystyle k take sho k displaystyle k policiyantiv mozhut vigrati gru na G displaystyle G PrikladNa derevi policijne chislo dorivnyuye odinici Policiyant mozhe pochati grati z bud yakoyi vershini i kozhnim hodom peresuvtisya v yedinu vershinu blizhchu do grabizhnika Kozhen hid policiyanta zmenshuye rozmir piddereva dostupnogo grabizhniku tomu gra obov yazkovo zavershitsya Poslidovnimi hodami nazustrich odin odnomu dva policiyanti garantovano mozhut shopiti grabizhnika v cikli tut na bejsbolnomu majdanchiku U ciklichnomu grafi dovzhinoyu bilshe troh policijne chislo dorivnyuye dvom Yaksho ye odin policiyant grabizhnik mozhe perejti v poziciyu za dva kroki vid policiyanta i zavzhdi zberigati cyu vidstan Takim chinom grabizhnik unikne riziku buti shoplenim U vipadku dvoh policiyantiv odin z nih mozhe stoyati v odnij i tij samij vershini a grabizhnik i drugij policiyant gratimut na chastini sho zalishilasya Yaksho drugij policiyant dotrimuyetsya strategiyi dlya dereva grabizhnik bezumovno prograye Zagalni rezultatiBud yakij graf obhvat yakogo bilshe 4 maye policijne chislo ne menshe vid jogo najmenshogo stepenya Zvidsi viplivaye sho isnuyut grafi z dovoli velikim policijnim chislom Nerozv yazana problema matematiki Yakim ye najbilshe mozhlive policijne chislo grafa z n vershinami bilshe nerozv yazanih problem matematiki 1985 roku vidomij za grafami Mejnelya pripustiv sho bud yakij graf iz n displaystyle n vershinami maye policijne chislo O n displaystyle O sqrt n Grafi Levi skinchennih proyektivnih ploshin mayut obhvat 6 ta minimalnij stepin W n displaystyle Omega sqrt n tak sho yaksho gipoteza istinna cya mezha bude najkrashoyu z mozhlivih Vidomo sho vsi grafi mayut sublinijne policijne chislo ale zadachi otrimannya tochnoyi mezhi abo sprostuvannya gipotezi Mejnelya zalishayutsya nerozv yazanimi Zadacha obchislennya policijnogo chisla zadanogo grafa maye klas skladnosti EXPTIME i skladna v sensi en Specialni klasi grafiv ce grafi z policijnim chislom 1 Policijne chislo bud yakogo planarnogo grafa ne perevishuye 3 Zagalnishe bud yakij graf maye policijne chislo sho ne perevishuye chisla proporcijnogo jogo rodu Odnak najkrasha vidoma nizhnya mezha dlya policijnogo chisla v terminah rodu priblizno dorivnyuye kvadratnomu korenyu z rodu sho daleko vid verhnoyi mezhi koli rid velikij Derevnu shirinu grafa mozhna otrimati yak rezultat gri psevdoperesliduvannya ale v cij gri grabizhnik mozhe ruhatisya za odin hid uzdovzh dovilno dovgogo shlyahu a ne na odne rebro Cya zajva svoboda oznachaye sho policijne chislo v zagalnomu vipadku menshe vid derevnoyi shirini Konkretnishe na grafah iz derevnoyu shirinoyu w displaystyle w policijne chislo ne perevishuye w 2 1 displaystyle lfloor w 2 rfloor 1 Posilannya ru Fromme M A game of cops and robbers 1984 T 8 vip 1 S 1 11 DOI 10 1016 0166 218X 84 90073 8 Bojan Mohar Notes on Cops and Robber game on graphs 2017 arXiv 1710 11281 Bibcode 2017arXiv171011281M William Baird Anthony Bonato Meyniel s conjecture on the cop number a survey Journal of Combinatorics 2012 T 3 vip 2 S 225 238 arXiv 1308 3385 DOI 10 4310 JOC 2012 v3 n2 a6 Peter Frankl Cops and robbers in graphs with large girth and Cayley graphs 1987 T 17 vip 3 S 301 305 DOI 10 1016 0166 218X 87 90033 3 William B Kinnersley Cops and robbers is EXPTIME complete Journal of Combinatorial Theory 2015 T 111 S 201 220 arXiv 1309 5405 DOI 10 1016 j jctb 2014 11 002 Fedor V Fomin Petr A Golovach Jan Kratochvil On tractability of cops and robbers game Fifth IFIP International Conference on Theoretical Computer Science TCS 2008 New York Springer 2008 T 273 S 171 185 IFIP Int Fed Inf Process DOI 10 1007 978 0 387 09680 3 12 Bernd S W Schroeder The copnumber of a graph is bounded by 32genus G 3 displaystyle lfloor tfrac 3 2 operatorname genus G rfloor 3 Categorical perspectives Kent OH 1998 Boston Birkhauser 2001 S 243 263 Trends Math Nancy Elaine Blanche Clarke Constrained cops and robber Canada Dalhousie University 2002 Ph D thesis