Representaciones matriciales de grafos

Representaciones matriciales de grafos

Hecmanuel Taveras Baez - 1067123 Diego Aquino Aybar - 1062696 Cristian Heredia - 1067207 Josias R. Carmona Amparo - 1065648

Contenido

● Matrices

○ Terminología de la matriz

● Matrices y grafos dirigidos

○ La matriz adyacente de un grafo

○ Determinación de un grafo dirigido de una matriz

● Matrices y grafos no dirigidos

○ Determinación de la matriz de adyacencia de un grafo

○ Matrices simétricas

Contenido

● Matrices y componentes conexos

● Multiplicación de matrices

○ renglón por columna

○ Cálculo de un producto matricial

○ Asociatividad de la multiplicación de matrices para matrices 2x2

○ Una matriz identidad actúa como una identidad

○ Potencias de una matriz

● Conteo de caminos de longitud N

Matrices

Las matrices son analogías de sucesiones bidimensionales. También se les llaman arreglos bidimensionales. Una matriz A m x n (se lee “m por n”) sobre un conjunto S es un arreglo rectangular de elementos de S dispuestos en m renglones y n columnas:

Matrices

La entrada aij en el i-ésimo renglón y la j-ésima columna de A se llama la ij- ésima entrada de A. Se dice que una matriz m x n tiene tamaño m x n. Si A y B son matrices, entonces A = B si y sólo si, A y B tienen el mismo tamaño y las entradas correspondientes de A y B son todas iguales; es decir, aij bij para toda i = 1, 2,..., m y j = 1, 2, ..., n.

Matrices

Una matriz para la que los números de renglones y de columnas son iguales se llama una matriz cuadrada. Si A es una matriz cuadrada de tamaño n x n, entonces la diagonal principal de A consta de todas las entradas a11, a22, ..., ann:

Ejercicio de Matrices

La siguiente es una matriz de 3 3 en el conjunto de números enteros.

⎡ 1 0 −3⎤ 4 −1 5 ⎣−2 2 0⎦

a. ¿Cuál es la entrada en el renglón 2, columna 3?

b. ¿Cuál es la segunda columna de A?

c. ¿Cuáles son las entradas de la diagonal principal de A?

Matrices y grafos dirigidos

Ya que ambos grafos tienen tres vértices, ambas matrices de adyacencia son matrices 3x3.

Matrices y grafos dirigidos

Determinación de un grafo dirigido de una matriz

Determinación de un grafo dirigido de una matriz

Matrices y grafos no dirigidos

Sea G un grafo no dirigido con vértices ordenados v1, v2,..., vn. La matriz de adyacencia de G es la matriz n x n, A = (aij) sobre el conjunto de los enteros no negativos tales que aij = número de aristas que conectan vi con vj para todas i, j = 1, 2, ..., n.

Determinación de la matriz de adyacencia de un grafo

¿Comó encuentre la matriz de adyacencia para el grafo G que se muestra a continuación.?

Simetría de una Matriz

Una matriz cuadrada n x n, A (aij) se llama simétrica, si y sólo si, para toda i,j = 1, 2,..., n, aij x aji.

Ejercicios de Simetría de matrices

¿Cuáles de las siguientes matrices son simétricas?

Matrices y componentes conexos

- Identificación de Grafo Conexo - Identificación de Componentes Conexo - Desarrollo de Matriz dado varios Componentes Conexos - Teorema

Identificación de Grafo Conexo

Un grafo es conexo si cada par de vértices está conectado por un camino.

Por ejemplo: para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Identificación de Componentes Conexos

Grafo

Primer Componente

Segundo Componente

Los componentes se refieren a subgrafos que considerados en conjunto forman un grafo principal.

Un componente es conexo si cada par de vértices está conectado por un camino.

Considere un grafo G, como los que se muestran a continuación, que consta de varios componentes conexos.