Matemáticas - Teoría de grafos

 grafo aleatorio a un grafo que es generado por algún tipo de proceso aleatorio. La teoría de los grafos aleatorios cae en la intersección entre la teoría de grafos y la teoría de probabilidades y se fundamenta en el estudio de ciertas propiedades de los grafos aleatorios. Uno de los modelos matemáticos más aplicados en la generación de redes aleatorias es modelo Erdös–Rényi.

Los grafos aleatorios poseen estructuras típicas de los procesos aleatorios.

Ramas de estudio

Una de las ramas más estudiadas en el área de las redes aleatorias es el de la teoría de la percolación (nivel de percolación) relacionado con el estudio de la fiabilidad en las redes de comunicación.³ Un campo de estudio inicial fue el de redes sociales, estudios sobre la topología de redes evolutivas como puede ser internet, etc. Se ha visto que algunas de las redes actuales crecen según modelos predefinidos en su distribuciones de grado, como puede ser la redes libres de escala.

Concepto

La idea de los grafos aleatorios está dentro de como enlazar de forma aleatoria un conjunto de N nodos, para realizar esto se pueden seguir diversas estrategias, cada una de ellas proporciona un modelo de redes (grafos) aleatorios. Una de los campos de estudio más activo es el de los grafos aleatorios dinámicos en los que se van añadiendo nodos a medida que pasa el tiempo, estos grafos muestran ciertas propiedades de las redes reales.⁴

Teoremas

Algunos teoremas se deducen del modelo, por ejemplo, si G(n; p) es un grafo aleatorio con n vértices donde cada enlace tiene una posibilidad p de existir:

Teorema 1

Dado un G(n, p) con un valor p constante e independiente de n, entonces el grafo seguro que posee casi seguro un diámetro igual a 2.

Teorema 2

Para un grafo G(n, p) aleatorio se establece que ${\displaystyle \textstyle p=c{\frac {\log n}{n}}}$. Si c > 1 entonces casi todos los grafos no poseen vértices aislados y si c < 1 casi todos los grafos tienen al menos un vértice aislado.

grafo cociente o gráfica cociente es una gráfica construida a partir de un homomorfismo de gráficas mediante la siguiente construcción.

• Si ${\displaystyle f:G\to H}$ es un epimorfismo de gráficas y ${\displaystyle V(H)=\{v1,v_{2},\ldots ,v_{m}\}}$ es el conjunto de vértices de H, se pueden construir los conjuntos ${\displaystyle S_{i}=f^{-1}(v_{i})}$.
• La gráfica cociente ${\displaystyle G/f}$ es la gráfica cuyo conjunto de vértices está dado por ${\displaystyle \{S_{1},S_{2},\ldots ,S_{m}\}}$ y donde ${\displaystyle S_{i}S_{j}}$ es una arista de ${\displaystyle G/f}$ si y sólo si ${\displaystyle v_{i}v_{j}}$ es una arista de ${\displaystyle H}$.

• La gráfica cociente inducida por ${\displaystyle f}$ es una gráfica isomorfa a ${\displaystyle H}$.
• Cualquier ${\displaystyle k-}$coloración de ${\displaystyle G}$ corresponde a un epimorfismo de ${\displaystyle G}$ en la gráfica completa ${\displaystyle K_{k}}$.

 grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido,¹ a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.

Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos ${\displaystyle G=(V,E)}$, donde:

• ${\displaystyle V\neq \emptyset }$, un conjunto no vacío de objetos simples llamados vértices o nodos.
• ${\displaystyle E\subseteq \{(a,b)\in V\times V:a\neq b\}\,}$ es un conjunto de pares ordenados de elementos de ${\displaystyle V\,}$ denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.

A veces un digrafo es denominado digrafo simple para distinguirlo del caso general del multigrafo dirigido, donde los arcos constituyen unmulticonjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arco representa relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre los nodos), o por un atributo como por ejemplo su importancia o peso.

A menudo también se considera que un digrafo simple es aquél en el que no están permitidos los bucles. Un bucle es un arco que une un vértice consigo mismo.

Terminología básica

Un arco ${\displaystyle e=(x,y)}$ se considera dirigido desde x hacia y; y se denomina cabeza y x se denomina cola del arco.

y se denomina también un sucesor directo de x; correspondientemente, se denomina a x un predecesor directo de y.

Si existe un camino compuesto de uno o más arcos que una x con y, entonces a y se le denomina sucesor de x, al igual que a x se le denomina predecesor de y.

Al arco ${\displaystyle (y,x)}$ se le denomina arco invertido de ${\displaystyle (x,y)}$.

Un grafo dirigido G es llamado simétrico si, para cualquier arco que pertenece a G, el arco invertido correspondiente también pertenece a G. Un grafo dirigido simétrico y sin bucles es equivalente a un grafo no dirigido; basta con reemplazar cada par de arcos dirigidos por un solo arco no dirigido.

Una orientación de un grafo simple no dirigido se obtiene al asignar una orientación a cada uno de los arcos existentes. Un grafo dirigido construido de esta manera se denomina un grafo orientado. Una manera de distinguir entre un grafo simple dirigido y un grafo orientado es que si x e y son vértices, un grafo simple dirigido permite tanto ${\displaystyle (x,y)}$ como ${\displaystyle (y,x)}$ entre sus arcos, mientras que solo una de las dos posibilidades es admitida en un grafo orientado.^2 3

Un digrafo ponderado es un digrafo en el que existen pesos asociados a cada uno de los arcos, de manera análoga al grafo ponderado. Un digrafo ponderado en el contexto de la teoría de grafos es denominado una red.

La matriz de adyacencia de un digrafo (con bucles y arcos múltiples permitidos) es una matriz compuesta por valores enteros, donde los índices de columnas y filas se corresponden con las identidades de los vértices ${\displaystyle V}$. Un elemento de esta matriz, ${\displaystyle a_{ij}}$ representa el número de arcos existentes entre los nodos i y j. Un elemento en la diagonal de esta matriz, ${\displaystyle a_{ii}}$ representa el número de bucles que existen en el nodo i. La matriz de adyacencia de un digrafo es una representación única del digrafo, exceptuadas posibles permutaciones de las filas y columnas.

Otra representación común de un digrafo es la matriz de incidencia.

En el campo matemático de la teoría de grafos, un grafo distancia-transitivo es un grafo tal que, dados dos vértices cualesquiera v y w a cualquier distancia i, y otros dos vértices cualesquiera x y y a la misma distancia, existe un automorfismo del grafo que transforma v en x yw en y.

Un grafo distancia-transitivo es vértice-transitivo y simétrico así como distancia-regular.

El interés en los grafos distancia-transitivos radica en parte en que tienen un grupo de automorfismos grande. Algunos grupos finitos interesantes son los grupos de automorfismos de grafos distancia-transitivos, especialmente de aquellos cuyo diámetro es 2.

Los grafos distancia-transitivos fueron definidos por primera vez en 1971 por Norman L. Biggs y D. H. Smith, quienes mostraron que sólo hay 12 grafos distancia-transitivos cúbicos finitos. Estos son:

Nombre	Vértices	Diámetro	Cintura	Array de intersección
Grafo completo K4	4	1	3	{3;1}
Grafo bipartito completo K3,3	6	2	4	{3,2;1,3}
Grafo de Petersen	10	2	5	{3,2;1,1}
Grafo del cubo	8	3	4	{3,2,1;1,2,3}
Grafo de Heawood	14	3	6	{3,2,2;1,1,3}
Grafo de Pappus	18	4	6	{3,2,2,1;1,1,2,3}
Grafo de Coxeter	28	4	7	{3,2,2,1;1,1,1,2}
Grafo de Tutte–Coxeter	30	4	8	{3,2,2,2;1,1,1,3}
Grafo del dodecaedro	20	5	5	{3,2,1,1,1;1,1,1,2,3}
Grafo de Desargues	20	5	6	{3,2,2,1,1;1,1,2,2,3}
Grafo de Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Grafo de Foster	90	8	10	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Independientemente en 1969 un grupo ruso liderado por Georgy Adelson-Velsky mostró que existían grafos que eran distancia-regularespero no distancia-transitivos. El único grafo de este tipo de grado tres es la 12-jaula de Tutte de 126 vértices. El menor grafo distancia-regular que no es distancia-transitivo es el Grafo de Shrikhande. Se conocen listas completas de grafos distancia-transitivos para algunos grados mayores que tres, pero la clasificación de grafos distancia-transitivos de grados arbitrariamente grandes continúa abierta.

El grafo de Biggs-Smith, el mayor grafo 3-regular distancia-transitivo.