PDF de programación - Ejemplos de construcción de matrices de Laplace de algunos grafos no dirigidos en el lenguaje de MATLAB

Ejemplos de construcción de matrices de Laplace

de algunos grafos en el lenguaje de MATLAB

Estos ejercicios forman una parte de trabajo conjunto de Mario Guzmán Silverio, Egor
Maximenko, Rogelio Rocha Hernández y Eliseo Sarmiento Rosales.

Objetivos. Practicar técnicas del lenguaje de MATLAB construyendo matrices laplacia-
nas de varios grafos simples (se consideran solamente grafos no dirigidos sin bucles).

Requisitos. Comandos de MATLAB para construir matrices especiales, programación
de funciones en el lenguaje de MATLAB.

1. Análogos libres de MATLAB. En los ejemplos escritos abajo se usa el dialecto de
GNU Octave. Otras buenas opciones son Scilab y FreeMat.

2. Ejemplo de la matriz laplaciana de un grafo.

 .

0
0
0
0
3 −1
0
2 −1
0 −1
1

0 −1
1 −1
0 −1
0

1
0
−1 −1
0
0


 3 −1 −1 −1

 .

−1
−1 −1
−1

2 −1
0 −1

0
3 −1
2

3

4

5

1

2

3. Un ejemplo más.

4

1

3

2

4. Descripción de la tarea. En cada uno de los ejercicios escritos a continuación se
describe una clase simple de grafos y se propone escribir una función en el lenguaje de
MATLAB que construya la matriz laplaciana para grafos de este tipo. Los programas de-
ben estar escritos sin ciclos y aprovechar los comandos y técnicos especiales del lenguaje
de MATLAB. Como una opción, se puede usar la sintaxis especial de MATLAB para
crear matrices dispersas.

Ejemplos de construir matrices laplacianas en el lenguaje de MATLAB, página 1 de 4

5. Camino. El parámetro de la función es el tamaño del grafo. El dibujo corresponde al
parámetro n = 5.

1

2

3

4

5

Una realización posible es la siguiente:

function A = LaplaceMatrixOfPathGraph(n),

if n > 1,

A = 2 * eye(n) - diag(ones(n - 1, 1), 1) - diag(ones(n - 1, 1), -1);
A(1, 1) = 1;
A(n, n) = 1;

else,

A = 0;

endif

endfunction

Otra solución que produce una matriz dispersa:

function A = LaplaceMatrixOfPathGraph(n),

if n > 1,

A = 2 * speye(n);
A(1, 1) = 1; A(n, n) = 1;
A = spdiags(-ones(n, 2), [-1, 1], A);

else,

A = 0;

endif

endfunction

Después de programar la función, hay que probarla ejecutando en el intérprete el siguiente
comando:

LaplaceMatrixOfPathGraph(5)

 .

La respuesta debe ser la siguiente matriz:
1 −1
−1
0 −1
0
0

0
0
0
2 −1
0
0
2 −1
0
2 −1
0 −1
0 −1
1
0



Si la matriz se regresa en el formato comprimido (Compressed Column Sparse), entonces
uno puede convertirla al formato completo usando la función full:

full(LaplaceMatrixOfPathGraph(5))

Ejemplos de construir matrices laplacianas en el lenguaje de MATLAB, página 2 de 4

6. Grafo circular. El parámetro de la función es el tamaño del grafo. El dibujo corres-
ponde al parámetro n = 5.

1

2

5

3

4

7. Grafo completo. El parámetro de la función es el tamaño del grafo. El dibujo corres-
ponde al parámetro n = 5.

1

2

5

3

4

8. Estrella. El parámetro de la función es el tamaño del grafo. El dibujo corresponde al
parámetro n = 6.

2

1

3

6

4

5

9. Rueda. El parámetro de la función es el tamaño del grafo. El dibujo corresponde al
parámetro n = 6.

2

1

3

6

4

5

Ejemplos de construir matrices laplacianas en el lenguaje de MATLAB, página 3 de 4

10. Árbol polar. El grafo consiste de m ramos de longitudes L1, . . . , Lm que empiezan
desde un vértice. El parámetro de la función es la m-tupla (L1, . . . , Lm) dada como un
arreglo L. Por ejemplo, si el parámetro de la función es el arreglo [4; 6; 5], entonces el
grafo correspondiente es

2

5

3

6

4

7

8

9

1

10

11

12

13

11. Rosa. El grafo consiste de m ciclos (pétalos) de longitudes L1, . . . , Lm unidos en
un vértice. El parámetro de la función es la m-tupla (L1, . . . , Lm) dada como un arreglo
L. Por ejemplo, si el parámetro de la función es el arreglo [6; 3], entonces el grafo
correspondiente es

2

3

4

5

6

1

7

8

12. Tema para meditar. Las matrices laplacianas de grafos surgen de manera natural
al estudiar varios problemas sobre grafos, por ejemplo, los problemas de difusión o los
problemas de propagación de ondas. El análisis espectral de matrices laplacianas de grafos
se conoce también como el análisis armónico sobre grafos.

Ejemplos de construir matrices laplacianas en el lenguaje de MATLAB, página 4 de 4