Para saber a partir de nuestra matriz si nuestro grafo es dirigido o no dirigido basta con analizar si la matriz es simétrica o asimétrica, en caso de ser simétrica entonces el grafo es no dirigido y si es asimétrica entonces el grafo es dirigido.
Para saber a partir de nuestra matriz si nuestro grafo es dirigido o no dirigido basta con analizar si la matriz es simétrica o asimétrica, en caso de ser simétrica entonces el grafo es no dirigido y si es asimétrica entonces el grafo es dirigido.
Apuntes de clase
En una matriz de adyacencia para un grafo no dirigido si cambiamos las columnas por filas o viceversa nos debe dar la misma matriz, es decir, debe ser una matriz simetrica, ya que estamos hablando de conexiones sin importar la direccion, esto en pocas palabras es como decir, si tenemos en la casilla a y b un 1, en la casilla b y a tambien debe ser 1. Por el contrario en un grafo dirigido esto no necesariamente va a ser lo mismo, por lo que nuestra matriz puede ser tanto simetrica como no simetrica, las conexiones pueden estar dirigidas solo hacia un nodo o dirigidas hacia ambos nodos.
Le falto decir que los vértices de la columna son los que reciben una arista y los vértices de la fila son de los que parte una arista .)
Basicamente, si hay una conexion a con b, pero no hay una b con a, el grafo ya es dirigido, ya que al no haber conexion en ambos lados, solo hay una direccion.
Notas
En los grafos simples, se tiene en cuenta, de que nuestro grafo cumple la ley conmutativa, mientras que el grafo dirigido no. Podrìamos asimilar un grafo simple como una suma o multiplicaciòn, dònde el orden los factores (en este caso nodos) no afecta el resultado, mientras que en un grafo dirigido es como una resta o divisiòn, dònde el orden de los factores, altera por mucho el resultado.
Recordar que en el nùmero de filas, se encuentran el nùmero de nodos, tanto en la matriz de adyacencia como en la matriz de incidencia.
Matriz Adyacencia Es la forma de presentar un grafo de n nodos mediante una matriz nxn donde cada fila y columna representa un nodo.
Pasos para asignar valores a la celda correspondiente: • Si existe una conexión entre dos nodos entonces asignamos un uno. Se suman las contribuciones de las conexiones y se asigna el resultado • Si no existe una conexión colocaremos un cero • Si el nodo tiene una conexión en bucle y el grafo es no dirigido asignamos 2. Si es dirigido le asignamos 1. Se suman las contribuciones y se asigna el resultado.
Nota: • En caso de ser el grafo no dirigido la matriz será simétrica y al sumar cada fila o columna nos dará el grado de cada vértice • En caso de ser el grafo dirigido, si sumamos las columnas obtenemos el grado de entrada y si sumamos las filas el grado de salida .
Una matriz es simétrica, cuando es cuadrada, la cual tiene la característica de ser igual en su lado opuesto y una matriz asimétrica no tiene su lado igual
