¿Cuántos cables hay que cortar para apagar internet?

¿Cuántos 'cables' habrá que cortar, por ejemplo,  para aislar a un conjunto de usuarios de una red o evitar el avance de una epidemia? Por increíble que parezca, ciertos fenómenos que aparecen en todas estas situaciones se pueden modelar mediante una misma teoría: la teoría de la percolación.

Aunque la percolación se estudia en física, química y diversas ingenierías, hoy nos vamos a centrar en los modelos combinatorios, es decir, los que trabajan con grafos. Por si no es usted un visitante habitual de esta casa, le diré que un grafo está formado por un conjunto de puntos (que llamamos vértices) y algunas líneas (que llamamos aristas) uniendo a determinadas parejas de vértices. En la figura siguiente tenemos un grafo:

Supongamos que en el grafo de la figura anterior los vértices (puntos) representan a las familias de los alumnos de una clase de primaria y hemos dibujado una arista entre aquellas familias que se conocen entre sí. Como es un grafo pequeño, es fácil ver que, en este ejemplo,  cualquier vértice (familia) puede hacer llegar un mensaje a cualquiera de las otras o bien directamente, o bien a través de otros. Si la familia señalada en la siguiente figura con A quiere hacer llegar un mensaje a la familia B, está claro que una posibilidad es utilizar como intermediarios a los vértices señalados en rojo.

También está claro que de romperse alguna amistad, podría ocurrir que fuese imposible para A comunicarse con B. Por ejemplo, si se rompe la amistad señalada por la arista en rojo en la siguiente figura:

Mientras que otras rupturas sentimentales no afectarían a la comunicación entre A y B porque tendrían otras opciones. Por ejemplo, la que señalamos en rojo en la siguiente ilustración:

También se ve sin dificultad que si el grafo de las relaciones personales de las familias de los alumnos de una clase es el siguiente, hay vértices que nunca se podrán comunicar con otros, porque están separados en tres grupos que no están conectados entre sí:

Pues bien, en pocas palabras, de eso trata la teoría de la percolación en grafos, de estudiar cuando una información puede llegar de un vértice del grafo a cualquier otro. De la misma manera que el agua traspasa el filtro de una cafetera americana o las paredes de un botijo. ¿En qué condiciones puede fluir la información de un lado a otro del sistema?

Vamos a verlo con otro ejemplo. Supongamos que tenemos una  malla, por ejemplo tenemos un tablero de damas muy, muy grande; para cada escaque, con una cierta probabilidad p, colocamos una ficha (luego con probabilidad 1 -p no la colocamos). Si deciden esto lanzando una moneda al aire p sería ½. Y 1-p también, claro.

La pregunta es: si comenzamos en uno de los laterales del tablero, ¿podemos llegar hasta el opuesto con movimientos del rey de ajedrez y sin pisar nunca un escaque ocupado? ¿Para qué valores de p podemos garantizar que casi siempre va a ser posible? Dicho de otra manera, imaginen que quieren fluir de un lateral al otro del tablero y que las fichas son obstáculos para usted o que el rey (el del ajedrez no don Felipe) es una molécula de agua que está atravesando un medio poroso  y nos preguntamos cuándo será posible que dicha molécula atraviese completamente la pared porosa.

En la siguiente figura, tenemos una simulación hecha con un tablero para distintos valores de p. Observen que cuánto mayor es el valor de p, más escaques están ocupados (en negro) y más complicado es percolar (fluir)  de izquierda a derecha, por ejemplo.

Fuente: www.altoona.psu.edu

Y bien, ¿para qué valores de p podemos asegurar que el rey encuentra un camino para llegar de un lado a otro del tablero? Efectivamente, estaba segura de que sabrían calcularlo: nuestro rey tendrá casi asegurado su camino desde una banda hasta la opuesta siempre y cuando coloquemos fichas con una probabilidad p menor que 0.67680165. Estaba claro desde un principio, ¿no?

Ahora en serio, el estudio de este tipo de problemas de percolación en grafos, que no son nada fáciles, tiene aplicaciones  al estudio de redes complejas interconectadas (telefónicas, ordenadores, etc.) para conocer, por ejemplo,  cómo de frágiles son ante las caídas aleatorias de ciertos nodos (si se cortan algunos de los cables de dichas redes, por ejemplo). Si quieren leer sobre cómo modelan los grafos las redes sociales ya hablamos aquí y sobre el modelado de epidemias aquí.

Así que, ya saben, antes de cortar un cable o una amistad, asegúrense de que no se están desconectando de algo a alguien que les interese mucho.