No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Ejercicio con matrices

23/40
Recursos

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.

Aportes 29

Preguntas 4

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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

  • Matriz de adyacencia sim茅trica 鈫 grafo no dirigido
  • Matriz de adyacencia asim茅trica 鈫 grafo dirigido

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 .

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.

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.

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

En un grafico simple sabemos que los nodos se conectan por lineas simple ( sin direccion),
En un grafico dirigido, los nodos se conectan por lineas con una direccion.
Para saber si un grafico es dirigido, se debe analizar si la matriz es simetrica o asimetrica; si la matriz es simetrica quiere decir que los numeros de las columnas van en el mismo orden que las filas, por tanto, no es un grafico dirigido; pero si la matriz es asimetrica, osea que el orden de los numeros de las columnas no son igual que el de las filas es un grafico dirigido.
La direccion parte desde la fila al momento de graficar, para la comprobacion tomamos la columna y decimos que viene desde la columna hasta la fila.
Solo se manejan 1 y 0.

me gusto la clase gracias

C贸mo saber que ese orden en el que est谩n los nodos es correcto? Es decir no habr铆a otra figura posible?

Se tiene que tener cuidado con la matriz de un grafo, ya que si esta es asim猫trica, estamos hablando de un grafo dirigido. Esto debido a que no es equivalente el 1 de a hacia b, que el de b hacia a, por lo que si solo tenemos un camino de b hacia a, solo b tiene un uno, y a en la matriz tiene un 0.

MATRIZ ASIM脡TRICA O NO SIM脡TRICA = GRAFO DIRIGIDO.
MATRIZ SIM脡TRICA = GRAFO NO DIRIGIDO.

Buena representacion y ejemplo

Excelente aplicaci贸n por medio del ejemplo.

En la matriz de adyacencia asim茅trica dibujamos cada una de las conexiones
dirigidas. Si representamos anteriormente C con D, y tenemos otra conexi贸n
D con C, debemos dibujar ambas de manera dirigida.

  • Cuando la matriz es no sim茅trica decimos que es un grafo dirigido.

Excelente clase.

El grado de los v茅rtices se mide igual en un grafo dirigido?

Excelente 馃槂

Bien!

  • 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.

matriz no simetrica es diferente de una matriz asim茅trica. La matriz sim茅trica es subconjunto de la matriz no sim茅trica. Cuidado con ese detalle. La forma tmb var铆a.

Excelente clase.