En esta sesi\u00f3n continuamos con el tema de grafos<\/p>\n
- \n
- \n
REPRESENTACI\u00d3N MATRICIAL<\/h2>\n<\/li>\n<\/ul>\n
-Matriz de adyacencia<\/strong><\/p>\n
Sea G un grafo con n v\u00e9rtices {vi<\/sub>}. Llamamos matriz de adyacentes a la matriz de orden (nxn) (una matriz cuadrada, mismo n\u00famero de filas y columnas) A=[ai,j<\/sub>] tal que ai,j <\/sub>es igual al n\u00famero de aristas (arcos) <\/sub>del v\u00e9rtice <\/sub>vi <\/sub>al vj<\/sub>. Para los grafos no dirigidos los bucles se cuentan 2 veces.<\/p>\n
La matriz de adyacencia define completamente el grafo.<\/p>\n
EJEMPLO<\/p>\n
Grafo no dirigido<\/strong><\/p>\n
<\/a>
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-1-300x263.jpg\")
<\/a>![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-3.jpg\")
<\/a>
\n<\/a><\/p>\nComo se puede apreciar se trara de una matriz sim\u00e9trica, los elementos de la diagonal inferior coinciden con los de la diagonal superior, ai,j=<\/sub>aj,i<\/sub>.<\/p>\n
-Para un grafo no dirigido con matriz de adyacencia A, la suma de los elementos de la fila i (o columna i) es igual al grado del v\u00e9rtice vi.<\/p>\n
Grafo dirigido<\/strong> <\/strong> <\/strong><\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-41-300x268.jpg\")
<\/a>![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-5.jpg\")
<\/a><\/p>\nLa fila representa el v\u00e9rtice origen y la columna el v\u00e9rtice destino.<\/p>\n
-Para un grafo dirigido con matriz de adyacencia A, la suma de los elementos de la fila i es igual al grado de salida del v\u00e9rtice vi y la suma de los elementos de la columna j es igual al grado de entrada del v\u00e9rtice j.<\/p>\n
-Sea G un grafo con matriz de adyacencia A. Entonces, el elemento (i, j) de la matriz Ar<\/sup>, r>= 1, es igual al n\u00famero de cadenas ri <\/sub>a rj<\/sub> de longitud r. <\/strong><\/p>\n
-Matriz de incidencia<\/strong><\/p>\n
Sea G = {V, A} un grafo no dirigido con n v\u00e9rtices y m aristas siendo V = {vi<\/sub>} y A\u00a0 = {ai<\/sub>}. Llamamos matriz de incidencia de G a la matriz de orden n x m.<\/p>\n
Tenemos una matriz con \u201cj\u201d columnas que ser\u00e1n los arcos o aristas e \u201ci\u201d filas que ser\u00e1n los v\u00e9rtices, pero seg\u00fan sea un grafo dirigido o no dirigido tendremos una nomenclatura u otra.<\/p>\n
–<\/strong>Grafo no dirigido:<\/p>\n
M= [mij<\/sub>]\/mij <\/sub><\/p>\n
->0 si vi <\/sub>no es incidente con aj<\/sub><\/p>\n
->1 si vi <\/sub>es incidente con aj<\/sub><\/p>\n
->2 si\u00a0aj<\/sub> <\/sub>es un bucle en vi<\/sub><\/p>\n
Todas las columnas sumar\u00e1n 2 porque una arista une 2 v\u00e9rtices. Es una forma de comprobar si hicimos bien la matriz incidente.<\/p>\n
EJEMPLO<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-21-300x277.jpg\")
<\/a>![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-32-300x117.jpg\")
<\/a><\/p>\n-Grafo dirigido:<\/p>\n
B= [bij<\/sub>]\/bij <\/sub><\/p>\n
->0 si vi <\/sub>no es incidente con aj<\/sub><\/p>\n
->1 si vi <\/sub>es v\u00e9rtice inicial de aj<\/sub><\/p>\n
->-1 si vi <\/sub>es v\u00e9rtice final de aj<\/sub><\/p>\n
->2 si\u00a0aj<\/sub> <\/sub>es un bucle en vi<\/sub><\/p>\n
La suma de columnas de un grafo dirigido sin bucles da 0 porque tendremos un 1 por el arco saliente y un -1 por el entrante.<\/p>\n
EJEMPLO<\/p>\n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-411.jpg\")
<\/a>![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-51-300x146.jpg\")
<\/a><\/p>\nPropiedades de la matriz de incidencia:<\/p>\n
- \n
- Para un grafo no dirigido, la suma de los elementos de cada fila de la matriz de incidencia es igual al grado del correspondiente v\u00e9rtice.<\/li>\n
- Para un grafo no dirigido, la suma de los elementos de cada columna de la matriz de incidencia es igual a 2.<\/li>\n
- Para un grafo dirigido sin bucles, la suma de los elementos de cada columna de la matriz de incidencia es igual a 0.<\/li>\n<\/ul>\n
Tabla de aristas incidentes<\/strong><\/p>\n
Para un grafo no dirigido, llamaremos tabla de aristas incidentes <\/strong> a una tabla que lista, para cada v\u00e9rtice v, todas las aristas incidentes con v.<\/p>\n
Tabla de arcos salientes<\/strong><\/p>\n
Para un grafo dirigido, llamaremos tablas de arcos salientes <\/strong>a una tabla que lista, para cada v\u00e9rtice v, todos los arcos salientes de v. Llamaremos tablas de arcos entrantes <\/strong> a una tabla que lista, para cada v\u00e9rtice v, todos los arcos entrantes en v.<\/p>\n
- \n
- \n
ACCESIBILIDAD Y CONECTIVIDAD<\/h2>\n<\/li>\n<\/ul>\n
Sea\u00a0 G = (V, A) un grafo dirigido.<\/p>\n
1. Sean xi <\/sub>, xj <\/sub>\u03b5 V, diremos que xj <\/sub>es alcanzable desde xi <\/sub>o que xi<\/sub> alcanza a xj <\/sub>si existe un camino dirigido de xi <\/sub>a xj <\/sub>.<\/p>\n
2. Sea V = {xi<\/sub>}. Llamaremos matriz de accesibilidad asociada al grafo G a la matriz cuadrada de orden n definida por<\/p>\n
R=[rij<\/sub>] \/rij <\/sub><\/p>\n
->1 si xi <\/sub>alcanza a xj.<\/sub><\/p>\n
->0 en otro caso<\/p>\n
- \n
![\"\"](\"https:\/\/blogs.ua.es\/dar15\/files\/2010\/12\/Sin-t\u00edtulo-1.jpg\")
<\/a>![\"\"](\"..\/..\/romulo\/2010\/11\/30\/files\/2010\/11\/Sin-t%C3%ADtulo-3.jpg\")
<\/a>