Recuento aleatorio

Gráfico aleatorio es un término general para la distribución de probabilidad de gráficos . Los gráficos aleatorios se pueden describir simplemente mediante una distribución de probabilidad o un proceso aleatorio que crea estos gráficos [1] . La teoría de grafos aleatorios se encuentra en la intersección de la teoría de grafos y la teoría de la probabilidad . Desde un punto de vista matemático, los gráficos aleatorios son necesarios para responder a la pregunta sobre las propiedades de los gráficos típicos . Los gráficos aleatorios han encontrado aplicaciones prácticas en todas las áreas donde es necesario modelar redes complejas : se conoce una gran cantidad de modelos de gráficos aleatorios que reflejan varios tipos de redes complejas en varios campos. En un contexto matemático, el términográfico aleatorio casi siempre significa el modelo de gráfico aleatorio de Erdős-Rényi . En otros contextos, cualquier modelo de gráfico significa un gráfico aleatorio .

Modelos de grafos aleatorios

Se obtiene un grafo aleatorio a partir de un conjunto de n vértices aislados mediante la suma aleatoria sucesiva de aristas que conectan los vértices. El propósito de modelar gráficos aleatorios es determinar en qué etapa aparece una determinada propiedad del gráfico [2] . Diferentes modelos de gráficos aleatorios dan diferentes distribuciones de probabilidad en el gráfico.

La más estudiada es la distribución propuesta por Hilbert y denotada por , en la que cualquier arista posible aparece independientemente con probabilidad . La probabilidad de obtener un gráfico con m aristas es donde [3] . ${\ estilo de visualización G (n, p)}$ $0<p<1$ ${\tbinom {N}{m))$ ${\displaystyle p^{m}(1-p)^{Nm))$ $N={\tbinom{n}{2}}$

El modelo de Erdős-Rényi , que está cerca de él , denotado por , da la misma probabilidad a todos los gráficos que tienen exactamente M aristas. Si se denota con , entonces contendrá elementos y cualquier elemento desaparecerá con probabilidad [2] . Este modelo se puede considerar como una instantánea para algún punto en el tiempo ( M ) de un proceso aleatorio en un gráfico que parte de n vértices sin aristas y en cada paso se agrega una nueva arista, elegida uniformemente del conjunto de aristas faltantes. ${\ estilo de visualización G (n, M)}$ $N={n \elegir 2},$ ${\ estilo de visualización 0 \ leq M \ leq N}$ ${\ estilo de visualización G (n, p)}$ ${\tbinom {N}{M))$ ${\tbinom{N}{M}}^{-1}$ ${\tilde {G}}_{n}$

Si, por el contrario, partimos de un conjunto infinito de vértices y elegimos cada arista posible de forma independiente con probabilidad 0 < p < 1, obtenemos un objeto G llamado grafo aleatorio infinito . Excepto en los casos triviales en los que p es 0 o 1, tal G casi con seguridad tiene las siguientes propiedades:

Dados n + m elementos , hay un vértice c en V que es adyacente a cada vértice y no está conectado a ninguno de ellos . $a_{1},\ldots,a_{n},b_{1},\ldots,b_{m}\in V$ ${\displaystyle a_{1},\ldots,a_{n))$ ${\displaystyle b_{1},\ldots,b_{m))$

Resulta que si el conjunto de vértices es numerable , entonces existe, hasta isomorfismo , el único grafo con tales propiedades, a saber, el grafo de Rado . Por lo tanto, cualquier gráfico infinito contable es casi con seguridad un gráfico de Rado, que por esta razón a veces se denomina simplemente gráfico aleatorio . Sin embargo, un resultado similar no es cierto para gráficos incontables, para los cuales hay muchos gráficos (no isomorfos) que satisfacen la condición anterior.

Otro modelo que generaliza el modelo gráfico aleatorio de Hilbert es el modelo de producto escalar aleatorio . El gráfico de producto escalar aleatorio asocia un vector real con cada vértice . La probabilidad de una arista uv entre cualquier vértice u y v es una función del producto escalar u • v de sus respectivos vectores.

Las matrices de probabilidad de red modelan gráficos aleatorios en términos de probabilidades de bordede tal manera que un borde dadoexiste en un período de tiempo específico. Este modelo se puede extender a grafos dirigidos y no dirigidos, ponderados y no ponderados, estáticos y dinámicos. $p_{i,j}$ $e_{{i,j}}$

Para M ≃ pN , donde N es el máximo número posible de aristas, los modelos más utilizados son G ( n , M ) y G ( n , p ), casi siempre intercambiables [4] .

Un gráfico regular aleatorio forma un caso especial que tiene propiedades que, en general, pueden diferir de los gráficos aleatorios.

Si tenemos un modelo de gráfico aleatorio, cualquier función en los gráficos se convierte en una variable aleatoria . La tarea de estudiar este modelo es determinar, o al menos estimar, la probabilidad de ocurrencia de una propiedad [3] .

Terminología

El término "casi cierto" en el contexto de gráficos aleatorios se refiere a una secuencia de espacios y probabilidades tal que la probabilidad de error tiende a cero [3] .

Propiedades de grafos aleatorios

La teoría de grafos aleatorios estudia las propiedades típicas de los grafos aleatorios que se cumplen con un alto grado de probabilidad para los gráficos obtenidos para una determinada distribución. Por ejemplo, podemos preguntar, para valores dados de n y p , cuál es la probabilidad de que G ( n , p ) sea conexo . Al estudiar tales preguntas, los investigadores a menudo se enfocan en el comportamiento asintótico de los gráficos aleatorios: los valores a los que tienden varias probabilidades a medida que n crece . La teoría de la percolación describe la conectividad de grafos aleatorios, especialmente aquellos infinitamente grandes.

La percolación está relacionada con la estabilidad de un gráfico (también llamado red). Sea un grafo aleatorio de n vértices y grado medio . Quitemos una parte aleatoria de los bordes y dejemos una parte. Hay un umbral de filtración crítico , por debajo del cual la red se fragmenta, mientras que por encima hay enormes componentes de conectividad [1] [5] [4] [6] [7] [8] . ${\ estilo de visualización \ langle k \ rangle}$ $1 p$ $pags$ $p_{c}={\tfrac {1}{\langle k\rangle ))$ $p_{c}$

Los grafos aleatorios son muy utilizados en el método probabilístico cuando se trata de probar la existencia de grafos con ciertas propiedades. La existencia de una propiedad en grafos aleatorios a menudo puede tener como consecuencia, según el lema de regularidad de Szémerédy , la existencia de esta propiedad para casi todos los grafos.

Para gráficos regulares aleatorios , G ( n , r -reg) es el conjunto de gráficos regulares r con r = r ( n ) tal que n y m son números enteros positivos , 3 ≤ r < n y rn = 2 m incluso [2] .

La secuencia de grados de un grafo G en G n depende únicamente del número de aristas en los conjuntos [2]

V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cpuntos,n.

Si el conjunto de aristas M en un grafo aleatorio G M es lo suficientemente grande como para que casi todos los G M tengan un grado mínimo de al menos 1, entonces casi todos los G M son conexos y, incluso para n , casi todos los G M contienen un perfecto coincidencia _ En particular, en el momento en que desaparece el último vértice aislado, en casi todos los gráficos aleatorios, el gráfico se vuelve conectado [2] .

Casi cualquier proceso de construcción de un grafo con un número par de vértices cuando alcanza un grado mínimo de 1 o un grafo aleatorio cuando alcanza un poco más de ( n /4)log( n ) aristas con una probabilidad cercana a 1 asegura la existencia de una coincidencia completa, excepto quizás un pico.

Para alguna constante c , casi todos los gráficos etiquetados con n vértices y al menos cn log( n ) aristas son hamiltonianos . Con una probabilidad que tiende a 1, agregar una arista que eleve el grado mínimo de un gráfico a 2 lo convierte en hamiltoniano.

Colorear gráficos aleatorios

Dado un grafo aleatorio G de orden n con vértices V ( G ) = {1, …, n }, se puede obtener el color usando un algoritmo voraz (el vértice 1 se pinta con el color 1, el vértice 2 obtiene el color 1 si no es adyacente a 1, de lo contrario obtiene el color 2, y así sucesivamente) [2] .

Árboles aleatorios

Un árbol aleatorio es un árbol o árbol dirigido formado por un proceso aleatorio . En una amplia gama de gráficos aleatorios de orden n y tamaño M ( n ), la distribución del número de árboles de orden k está asintóticamente sujeta a la ley de Poisson . Los tipos de árboles aleatorios incluyen árboles de expansión uniformes , árboles de expansión mínimos aleatorios , árboles binarios aleatorios , árboles cartesianos, árboles aleatorios de búsqueda rápida , árboles brownianos y bosques aleatorios .

Historia

Los gráficos aleatorios fueron definidos por primera vez por Erdős y Rényi en su libro de 1959 "On Random Graphs" [8] e independientemente por Hilbert en su artículo "Random graphs" [5] .

Véase también

Notas

↑ 1 2 Béla Bollobás Gráficos aleatorios. — Prensa de la Universidad de Cambridge, 2001.
↑ 1 2 3 4 5 6 Béla Bollobás Gráficos aleatorios. — Londres: Academic Press Inc, 1985.
↑ 1 2 3 Béla Bollobás Combinatoria probabilística y sus aplicaciones. — Providencia: Sociedad Matemática Estadounidense, 1991.
↑ 1 2 Resultados matemáticos en gráficos aleatorios sin escala. Manual de Grafos y Redes / S. Bornholdt, HG Schuster. — Weinheim: Wiley VCH, 2003.
↑ 1 2 E. N. Gilbert. Gráficos aleatorios. — Anales de Estadística Matemática. - 1959. - T. 30. - S. 1141-1144. -doi : 10.1214 / aoms/1177706098 .
↑ MEJ Newman. Redes: una introducción. —Oxford, 2010.
↑ Reuven Cohen, Shlomo Havlin . Redes Complejas: Estructura, Robustez y Función . — Prensa de la Universidad de Cambridge, 2010.
↑ 1 2 P. Erdős , A Rényi . Sobre grafos aleatorios I. — Publ. Matemáticas. - 1959. - T. 6. - S. 290-297.

Literatura

SOY. Raygorodsky . Modelos de grafos aleatorios. — M .: MTsNMO , 2011. — 136 p. - ISBN 978-5-94057-840-6 .

diccionarios y enciclopedias	gran chino gran ruso
En catálogos bibliográficos	BNF : 12288320t J9U : 987007563131005171 LCCN : sh85111348 NKC : ph664004