les cuento, estoy haciendo una aplicación en c# donde represento un grafo a través de la matriz de adyacencia, dicha matriz la ingresa el usuario, la pregunta es como puedo hacer un método que me diga si dicha matriz es de un grafo dirigido o no. la idea es que simplemente el usuario tenga que oprimir un botón y salga un mensaje diciendo "la matriz ingresada es dirigida" o en su defecto, no lo es.
1 respuesta
Supón que tienes un grafo con los sigientes nodos:
Nodo1 <==> Nodo2
Nodo1 ==> Nodo3
Nodo3 ==> Nodo2
Entonces tu matriz de adyacencia de un modo más visual sería algo como:
Nodo1 Nodo2 Nodo3
Nodo1 . .
Nodo2 .
Nodo3 .
La forma fácil es fijarte en las simetrías.
Como hay un camino entre Nodo1
y Nodo2
y visceversa, en la matriz hallarás la simetría en base a la diagonal:
Nodo1 Nodo2
Nodo1 .
Nodo2 .
Hasta ese momentos tenemos un grafo no dirigido ya que en un grafo no dirigido es aquel en el que todas sus aristas son bidireccionales.
Esto quiere decir que si numeramos nuestra matriz bidireccional
i 0 1
j Nodo1 Nodo2
0 Nodo1 .
1 Nodo2 .
Notamos que para cada Matriz[i][j] == Matriz[j][i]
.
Ahora agregando los demás nodos
i 0 1 2
j Nodo1 Nodo2 Nodo3
0 Nodo1 . .
1 Nodo2 .
2 Nodo3 .
La regla no se cumple, por lo tanto si tenemos un grafo dirigido, a pesar de que si extraemos el subgrafo con el Nodo1 y Nodo2 este subgrafo sería un grafo no-dirigido.
Ahora en código en vez de usar un .
generalmente se usan valores binarios o pesos entre los aristas.
¿Qué pasa si tienen peso?
Bueno, hasta el momento el espacio significaba peso infinito, y el .
significaba sin peso, las mismas reglas siguen aplicando.
-
ahh vale, ya tengo mas idea, lo que tendría que hacer es recorrer las filas y columnas de mi matris y verificar que se cumpla esto, Matriz[i][j] == Matriz[j][i] ?osea ese seria mi condicional, verdad? Commented el 25 may. 2020 a las 20:36
-