Hoy hemos terminado el tema relacionado con la representación de grafos, y en practica, hemos empezado con el programa MAGRADA (el cual no me gusta para nada xD)
Teoria
Representación Matricial
Llamamos matriz adyacente a la matriz de orden n x n. A={aij} tal que aij es igual al número de aristas (arcos) del vértice vi al vj.
Propiedades de la matriz de adyacencia:
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értice vi.
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értice vi y la suma de los elementos de la columna j es igual al grado de entrada del vértice j.
Para un grafo con matriz de adyacencia A el elemento (i,j) de la matriz Ar, de donde r debe ser r>=1, es igual al número de cadenas de vi a vj de longitud r.
Llamamos matriz de incidencia de un grafo no dirigido a la matriz de orden n x m.
M=[mij]/mij= 0 si vi no es incidente con aj
1 si vi es incidente con aj
2 si aj es un bucle en vi
Propiedades de la matriz de incidencia:
- 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értice.
- Para un grafo no dirigido, la suma de los elementos de cada columna de la matriz de incidencia es igual a 2.
- Para un grafo dirigido sin bucles, la suma de los elementos de cada columna de la matriz de incidencia es igual a 0.
Tablas:
Para un grafo no dirigido, llamaremos tabla de aristas incidentes a una tabla que lista, para cada vértice v, todas las aristas incidentes con v.
Para un grafo dirigido, llamaremos tablas de arcos salientes a una tabla que lista, para cada vértice v, todos los arcos salientes de v. Llamaremos tabla de arcos entrantes a una tabla que lista, para cada vértice v, todos los arcos entrantes en v.
TEMA 6
Accesibilidad
Para un conjunto de vétices V, vj es alcanzable desde vi o vi alcanza a vj si existe un camino dirigidode vi a vj.
Llamaremos matriz de accesibilidad asociada al grafo G a la matriz cuadrada de orden n definida por:
R=[rij]/rij= 1 si vi alcanza a vj
0 en otro caso
Llamaremos matriz de acceso asociada al grafo G a la matriz cuadrada de orden n definifa por:
Q=[qij]/qij= 1 si vi es alcanzable desde vj
0 en otro caso
de donde Q=Rt , es decir, que la matriz de acceso de R es su traspuesta Rt
—————————-
Hasta la semana que viene compañeros!!!!!! xD
Víctor