Numero di cop

di

Ogni grafico la cui circonferenza è maggiore di quattro ha un numero di cop almeno uguale al suo grado minimo. Ne segue che esistono grafi di numero di cop arbitrariamente alto.

Problema irrisolto in matematica:

Qual è il più grande numero di cop possibile di un n {displaystyle n}

n

grafico a vertici?

Henri Meyniel (noto anche per i grafi di Meyniel) ha congetturato nel 1985 che ogni n {\displaystyle n} connesso

n

-vertex graph ha un numero di cop O ( n ) {\displaystyle O({\sqrt {n}})}

O({\sqrt n})

. I grafi di Levi (o grafi di incidenza) dei piani proiettivi finiti hanno circonferenza sei e grado minimo Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})}

Omega ({\sqrt n})

, quindi se fosse vero questo limite sarebbe il migliore possibile.

Tutti i grafi hanno un numero di cop sublineare. Un modo per dimostrarlo è usare sottografi che sono sorvegliabili da un singolo poliziotto: il poliziotto può muoversi per seguire il rapinatore in modo tale che, se il rapinatore si muove nel sottografo, il poliziotto può immediatamente catturare il rapinatore. Due tipi di sottografi che sono sorvegliabili sono il quartiere chiuso di un singolo vertice e un percorso più breve tra due vertici qualsiasi. Il limite di Moore nel problema del diametro di grado implica che almeno uno di questi due tipi di insiemi sorvegliabili ha dimensione Ω ( log n / log log n ) {\displaystyle \Omega (\log n/\log \log n)}

<Omega(\log n/\log\log n)

. Usando un cop per sorvegliare questo insieme e ricorrendone le componenti connesse dei restanti vertici del grafico, si vede che il numero di cop è al massimo O ( n log log n / log n ) {\displaystyle O(n\log \log n/\log n)}

{displaystyle O(n\log \log n/\log n)}

.

Un limite superiore più fortemente sublineare sul numero di cop,

n 2 ( 1 – o ( 1 ) ) log n , {\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}

{\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}

è noto. Tuttavia i problemi di ottenere un limite stretto, e di provare o confutare la congettura di Meyniel, rimangono irrisolti. Non si sa nemmeno se la congettura morbida di Meyniel, che esiste una costante c < 1 {\displaystyle c<1}

{displaystyle c1}

per cui il numero di cop è sempre O ( n c ) {displaystyle O(n^{c})}

O(n^{c})

, è vero.

Computare il numero di cop di un dato grafico è EXPTIME-hard, e difficile per la complessità parametrica.

Lascia un commento