Una llamada gráfica de $G = \{V,E\}$ en teléfono de metadatos tiene un vértice $v \in V$ para cada número de teléfono y una ventaja $\{v,w\} \in E$ si ha habido una llamada de teléfono entre el$v$$w$. Uno puede monitorear las llamadas de un conjunto $S \subseteq V$ autorizados de semillas. También puede investigar los vértices a distancia $3$ o menos a partir de una semilla(en otras palabras, en menos de tres saltos de distancia). Suponga $|S| = 300$ y cada teléfono ha tenido contacto con exactamente $100$ otros. Bajo estos supuestos dar un estricto límite superior en el número de números de teléfono sobre el que sin órdenes por consultas están permitidos.
Respuesta
¿Demasiados anuncios?
Newb
Puntos
10494
El conjunto de semillas, $S$, contiene $300$ vértices. La absoluta límite superior en el número de números de teléfono en la que podemos realizar un sin órdenes de consulta es $300 + (300 \cdot 100) + (300 \cdot 100 \cdot 99) + (300 \cdot 100 \cdot 99 \cdot 99) = 297030300$.
Razonamiento:
Podemos tomar nuestras semillas $S$. Asumir ninguna de las semillas están conectados. Luego tenemos a $300$ vértices que pueden consultar. Supongamos ahora que cada una de las $s \in S$ está conectado a $100$ distintos vértices. Esto le da otra $300 \cdot 100$ vértices podemos consultar en: llame a este conjunto de $P$.
Ahora tome cada uno de estos vértices en $P$. También están todos conectados a otros 100 vértices. En cada caso, sin embargo, que se conectará a un vértice entre nuestros original $300$ semillas. Así que a partir de cada uno de nuestros actuales vértices en $P$, sólo podemos consulta de otro $99$ nuevos vértices. Así que añadimos $300 \cdot 100 \cdot 99$ vértices.
El paso por el último salto es idéntica a la descrita en el párrafo anterior.
