Modelado y Simulación de Sistemas Complejos.

 Modelado y Simulación de Sistemas Complejos

Máster en Ingeniería Matemática UC3M Curso 2012 Lino Gustavo Garza Gaona Problemas Sesión 6

1. [Teórico].

De un ejemplo de un grafo en el cual cada nodo es pivote para al menos un par de nodos. Explique su respuesta.

Solución

En el siguiente grafo

[pic 1]

cada nodo es pivote para al menos un par de nodos. Tenemos que

• A es pivote de B y E.
• B es pivote de A y C.
• C es pivote de D y B.
• D es pivote de E y C.
• E es pivote de D y A.

De un ejemplo de un grafo en el cual cada nodo es pivote para al menos dos diferentes pares de nodos. Explique su respuesta.

Solución

En el siguiente grafo cada nodo es pivote de dos pares de nodos. Por ejemplo A es pivote de B y G, pero tambiŽn de C y G.

[pic 2]

De un ejemplo de un grafo de al menos 4 nodos en el cual haya un s—lo nodo X que es pivote para cada par de nodos (sin contar los pares que incluyan a X). Explique su respuesta.

Solución

En el siguiente grafo

[pic 3]

el nodo X es pivote para cada par de nodos, ya que cada par de nodos est‡n conectados s—lo atra vŽs de X.

2. [Analítico]. Considere la siguiente construcci—n jer‡rquica: Se inicia por un par de nodos conectados. En cada generaci—n se agrega a cada nodo i, de grado ki, ki nuevos enlaces que van a un nuevo nodo de grado 1.

ÀCu‡l es el nœmero de nodos despuŽs de n generaciones.

Construimos la red para las primeras generaciones y obtenemos {2, 4, 10, 28, 82} entonces observa mos la relaci—n conforme n (nœmero de generaciones) crece y obtenemos que para un n cualquiera el nœmero de nodos ser‡

3n

#nodos N =+ 1, n = {0, 1, 2, 3,... }.

ÀCu‡l es la distribuci—n de grado l’mite?

Se puede ver que para la generaci—n N tenemos 2 nodos de grado 2N, 2 nodos de grado 2N−1,6 de grado 2N−2 y as’ sucesivamente (la diferencia entre cantidades de nodos consecutivas), hasta llegar a 2 ∗ 3N−1 nodos de grado 1 y recordemos que tenemos N = 3N + 1 nodos en total. Llamemos Pk a la probabilidad de que un nodo tenga grado k = 2N, entonces cuando N →∞, tenemos

2 ∗ 3N−12

P1 = l«ım = ,

N→∞ 3N + 13

2 ∗ 3N−22

P2 = l«ım =

32 ,

N→∞ 3N + 1

.

.

. =

2

Pk−1 =

3N 2

Pk =

3N .

5. [Analítico]. Encuentre los autovalores de la martiz de adyacencia y el espectro del Laplaciano para

El grafo completo con N nodos.

Solución

La matriz de adyacencia es A = J − I, donde J es la matriz con todas las entradas iguales a 1 e I es la matriz identidad. Como J tiene espectro n1 , 0n−1 e I tiene espectro 1n y se cumple que IJ = JI, entonces el espectro de A es (n − 1)1 , (−1)n−1, donde el exponente denota la multiplicidad.

Para la matriz del Laplaciano tenemos que viene dada por L = NI − J. Entonces, por las mismas razones que para la matriz de adyacencia tenemos que los autovalores de L son (0)1 y (N)N−1 , donde el exponenete denota la multiplicidad.

Una red de estrella que contenga un nodo central de grado N − 1 conectado a N − 1 de grado 1.

Solución

La matriz de adyacencia tiene la forma

⎡⎤

01 ... 1

10 ... 0 A = .. .,

.

.. . .

.

.. .

[pic 4]

[pic 5]

⎣⎦

10 ... 0

como no es invertible, tiene al autovalor λ = 0. Al hacer el sistema Ax = 0 tenemos las siguientes ecuaciones

...